[erlang-questions] List to proplist?
Richard O'Keefe
<>
Wed Oct 22 04:38:08 CEST 2008
On 22 Oct 2008, at 3:41 am, Dave Smith wrote:
>
> This also my first introduction to unfold. I will definitely be
> looking for application of this pattern in the future.
It comes from the Haskell world, a strange place where
people talk about "coinduction" and the like. The idea
is actually quite simple.
Given some kind of data structure, you ask
"Could I view this as a list?"
and the answer is yes if you can
1. classify it as empty (map it to [])
2. or non-empty, with an identified
2a. first element X and
2b. residue R, the same kind of data structure you
started with.
Step 2 gives you [X|R].
What's really interesting here is that an implementation
strategy for list comprehensions somewhat different from
the one we now have could fit unfolds in beautifully.
Let's just consider a simple comprehension
[E(X) || X <- L, F(X)]
where E(X) is some expression whose value we want
to collect and F(X) is some filter.
This could be implemented as (quasi-Erlang pseudocode):
( %R := [],
%L := L,
loop
case %L
of [] -> break lists:reverse(%R)
; [H|T] ->
%L := T,
case H
of X ->
case F(X)
of true -> %R := [E(X)|%R], continue
; false -> continue
end
; _ ->
continue
end
end
end
)
Now consider
[E(X) || X <- unfold(State, Splitter), F(X)]
This could be implemented as (quasi-Erlang pseudocode):
( %R := [],
* %L := State,
loop
* case Splitter(%L)
of [] -> break lists:reverse(%R)
; [H|T] ->
%L := T,
case H
of X ->
case F(X)
of true -> %R := [E(X)|%R], continue
; false -> continue
end
; _ ->
continue
end
end
end
)
where the two lines I've starred are the only changes.
It's even clearer once you realise that if L is a list,
L = unfold(L, fun (X) -> X end).
If the compiler were aware that
lists:seq(From, To) =
if is_integer(From), is_integer(To) ->
unfold(From, fun (X) when X > To -> []
; (X) -> [X|X+1]
end)
end
then list comprehensions with numeric ranges would
not actually require the generation of a real list.
>
More information about the erlang-questions
mailing list