# [erlang-questions] Lazy lists

Richard O'Keefe ok@REDACTED
Tue Dec 8 01:37:02 CET 2009

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

```