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/








More information about the erlang-questions mailing list