# Lazy recursive list comprehensions

Joel Reymont <>
Fri Jan 13 12:21:19 CET 2006

```The following works thanks to Vlad and matches the Prolog version at
http://web.engr.oregonstate.edu/~erwig/zurg/ almost word for word.
This is very encouraging to me!

The code builds a search space of 108 items in a list but the same
approach to a different problem could produce a search space that is
much larger. Is there a way to redesign the code to use "lazy list
comprehensions" while keeping the elegance?

Thanks, Joel

P.S. The working code:

-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, []}) ->
[{[], 0}];

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/

```