Infinite Choices

[Filip Konvička]

Chris Rathman (9.3.2006 13:29):
> I appreciate the help I've gotten and hope not to wear out my welcome, 
> but I'm stuck again.  This is probably not the sort of problem for a Oz 
> newbie like myself to tackle, but it's the one in my path at the 
> moment.  Not sure I can clearly state the problem, but here goes....
> 
> If I have an unbound variable (Z) in the last position of a list like say:
> 
>  X|Y|Z
> 
> Then the structure of the variable Z in the tail could theoretically be 
> any of the following possibilities along an infinite choice of 
> possibilities:
> 
>  A|B|C|Z = _|_|_|nil         %% Z = nil
>  A|B|C|Z = _|_|_|_|nil       %% Z = _|nil
>  A|B|C|Z = _|_|_|_|_|nil     %% Z = _|_|nil
>  ....                        %% Z = _|_|...|nil
> 
> And so on.  What I'd like is to have a function that generates the 
> possible choices of the infinite variety of structures that are possible 
> when an unbound variable is in the last position of the list.   Some 
> example inputs and choice lists follow:
> 
>  Example Input: A|B|C|Z
>     choice
>        A|B|C|nil
>     [] A|B|C|_<optimized>|nil
>     [] A|B|C|_<optimized>|_<optimized>|nil
>     [] A|B|C|_<optimized>|_<optimized>|_<optimized>|nil
>        ....
>     end
> 
>  Another Example Input: 1|Z
>     choice
>        1|nil
>     [] 1|_<optimized>|nil
>     [] 1|_<optimized>|_<optimized>|nil
>     [] 1|_<optimized>|_<optimized>|_<optimized>|nil
>        ....
>     end
>  On the other hand, if the root tail of the list is nil, then the 
> function just needs to return the list as the function value
> 
>  Example Input: nil
>  Output:   nil
>    Example Input: 1|nil
>  Output:   1|nil   Example Input: 1|2|nil
>  Output:   1|2|nil       and so on....
> 
> As a background, this is basically what the Listo function does in 
> mini-Kanren.  Unfortunately, all my feeble attempts to build a recursive 
> choice list along these lines results in going into a wait state, as the 
> act of testing the structure seems to bind it at that juncture.  What 
> I'd like is something along the lines of:
> 
> fun {Listo L} H T in
>  if {IsBound L} then
>     case L
>     of nil then nil
>     [] H|T then H|{Listo T}
>     end
>  else
>     choice
>        L
>     [] L = H|T
>        H|{Listo T}
>     end
>  end
> end
> 
> But of course this is pseudo code, so it don't get me very far.  I'm not 
> aware of a IsBound type function in Oz to test whether I'm at the last 
> position of the list and it's an unbound variable.  (And while I'm at 
> it, is there a name for this last position in the list?  Base?  Root?)
> 
> Thanks,
> Chris Rathman
> 

Hi,

try this in the OPI:

local
    fun {FindTail L}
       if {IsDet L}==false then
          nil#_
       else
          case L
          of nil then
             nil#nil
          [] H|T then
             H2#T2={FindTail T}
          in
             (H|H2)#T2
          end
       end
    end
    fun {GenerateTail}
       choice
          nil
       []
          _|{GenerateTail}
       end
    end
    fun {GenLists L}
       proc {$ Root}
          H#T={FindTail L}
       in
          if {IsDet T} then
             Root=L
          else
             Root=H|{GenerateTail}
          end
       end
    end
    Solutions
    K
in
    Solutions=thread
                 {Search.all {GenLists a|b|c|_} 1 K}
              end
    {Inspect Solutions}
    {Delay 1000}
    {K} %% Kill the search! :-)
end

Why do you need this?

Cheers,
Filip