Recursive list comprehension

[Peter-Henry Mander]

Hi Joel,

I'm reading http://web.engr.oregonstate.edu/~erwig/papers/Zurg_JFP04.pdf

I haven't read all of the paper but it probably gives good guidance in
avoiding re-implementing backtracking in Erlang. Have you looked there?

Since Erlang was derived from Prolog a long time ago, I think Dr. Joe &
colleagues omitted backtracking because of rampant memory consumption
and the possibly iffy use of red/green cut that I for one never properly
understood. Erlang gains clarity without backtracking methinks.

Pete.

On Fri, 2006-01-13 at 09:38 +0000, Joel Reymont wrote:
> On Jan 13, 2006, at 7:26 AM, Peter-Henry Mander wrote:
> 
> > Without more context, it's hard for me to see how this code  
> > terminates.
> > What is the termination clause in this recursive function?
> >
> > And I doubt very much that it is tail recursive. It looks as if this
> > function will consume vast amounts of memory if the calculation is  
> > long.
> 
> My issue is that this comprehension just returns []. Period. I'm not  
> looking for tail recursion, just a working list comprehension.
> 
> I'm trying to translate the following from Prolog: http:// 
> web.engr.oregonstate.edu/~erwig/zurg/zurg.pl. The original paper is  
> at http://web.engr.oregonstate.edu/~erwig/zurg/
> 
> The code I came up with is below. Note the 1st clause of trans,  
> that's the fun that I'm having trouble with. It terminates when there  
> are no toys on the left side of the bridge and they have the  
> flashlight with them (on the right).
> 
> Ideally, this code should use lazy lists but I haven't gotten that  
> far, I'm just trying to make the dumb backtracking work.
> 
> -module(zurg).
> 
> -compile([export_all]).
> 
> time(buzz) -> 5;
> time(woody) -> 10;
> time(rex) -> 20;
> time(hamm) -> 25.
> 
> toys() -> [buzz, hamm, rex, woody].
> 
> cost([]) -> 0;
> cost([H|T]) -> max(cost(H), cost(T));
> cost(X) -> time(X).
> 
> split(L)
>    when is_list(L) ->
>      [{[X, Y], L -- [X, Y]} || X <- L, Y <- L, X < Y].
> 
> %%% Generate new state, move and cost of that move
> 
> move({st, l, L1})
>    when is_list(L1) ->
>      [{{st, r, L2}, {r, M}, cost(M)} || {M, L2} <- split(L1)];
> 
> move({st, r, L1})
>    when is_list(L1) ->
>      T = toys(),
>      R = T -- L1, % these guys are on the left
>      [{{st, l, lists:umerge([X], L1)}, {l, X}, cost(X)} || X <- R];
> 
> move(X) ->
>      erlang:error(invalid_move, X).
> 
> trans([{st, r, []}]) ->
>      none;
> 
> trans(S) ->
>      [{[M1] ++ M2, C1 + C2} || {S1, M1, C1} <- move(S), {M2, C2} <-  
> trans(S1)].
> 
> cross(D) ->
>      T = toys(),
>      [M || {M, D0} <- trans({st, l, T}), D0 =< D].
> 
> solution() -> cross(60).
> 
> max(A, B)
>    when is_number(A),
>         is_number(B) ->
>      if
> 	A > B ->
> 	    A;
> 	true ->
> 	    B
>      end.
> 
> --
> http://wagerlabs.com/
> 
> 
> 
> 
> 
>