[erlang-questions] Lazy lists

[Andrey]

Erlang documentation gives the following definition for lazy
(infinite) list:

ints_from(N) ->
fun() ->
[N | ints_from(N+1)]
end.

I tried to implement basic operations like map, filter and fold using
this function, and it was quite hard. On one the forums I found
another definition (by Joe Armstrong, I believe):

ints_from(K) -> [K | fun() -> ints_from(K+1) end].

With that one it's much easier to implement the functions above (at
least for me). I'm wondering if anybody uses the first definition, and
how map/filter/fold should look like then? What benefits does the
first definition give us in comparison to the second one?

Thanks,
Andrey

________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org

[Richard O'Keefe]

I never really expected to mention coinductive data types in the
Erlang mailing list...

To support "lazy (infinite) list"s, you need a data type C(E)
[C = container E = element] and a function
view :: C(E) -> 0 + (E x C(E))

which we might express in Erlang as

view(CE) ---> []
or view(CE) ---> [E | CE']

The representation from the Erlang documentation is

C(E) = fun(() -> [] | [E | C(E)])
view(CE) = CE()

The other representation is

C(E) = [] | [E | fun(() -> C(E))]
view(CE) = case CE of [] -> [] ; [X|F] -> [X|F()] end

which has the down-side of evaluating one more element than you
actually need.

With the first representation,

map(F, CE) ->
fun (()) ->
case CE()
of [] -> []
; [X|Xs] -> [F(X) | map(F, Xs)]
end
end.

compared with

map(F, L) ->
case L
of [] -> []
; [X|Xs] -> [F(X) | map(F, Xs)]
end.

for an ordinary list.

filter(P, CE) ->
fun (()) ->
case CE()
of [] -> []
; [X|Xs] -> case P(X)
of true -> [X | filter(P, Xs)]
; false -> (filter(P, Xs))()
end
end
end.

compared with

filter(P, L) ->
case L
of [] ->
; [X|Xs] -> case P(X)
of true -> [X | filter(P, Xs)]
; false -> filter(P, Xs)
end
end.

for an ordinary list.

foldl(F, A, CE) ->
case CE()
of [] -> A
; [X|Xs] -> foldl(F, F(A,X), Xs)
end.

compared with

foldl(F, A, L) ->
case L
of [] -> []
; [X|Xs] -> foldl(F, F(A,X), Xs)
end.

for an ordinary list.

Step 0: rewrite pattern matching to use case.
Step 1: replace case L of [] -> E0 ; [X|Xs] -> E1 end
with case view(L) of [] -> E0 ; [X|Xs] -> E1 end
Step 2: if you have g(...), known to return a lazy list,
in a context where a non-lazy result is required,
replace it by view(g(...)).
Step 3: if the result is a list,
replace f(...) -> E.
with f(...) -> fun () -> E end.

[Andrey]

Wow! Thanks a lot for such a quick and thorough response.