Recursive list comprehension

Joel Reymont < >
Fri Jan 13 10:38:19 CET 2006

```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/

```