[erlang-questions] Lazy lists

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