[erlang-questions] List to proplist?

[Richard O'Keefe]

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.

>