Recursive list comprehension

[Joel Reymont]

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/