[erlang-questions] Compiler list comprehension optimizations

[Richard A. O'Keefe]

On 5/07/2013, at 2:09 AM, Peer Stritzinger wrote:

> On 2013-06-15 12:21:25 +0000, ok@REDACTED said:
>> We have seen [... where I = 0 then I+1 while I < 100]
>> proposed, but that's not actually as general as a functional
>> language should be.  What's needed is a general 'unfold'
>> proposal, and we've had that for a while too.
> 
> Somehow I have difficulty to find the "unfold" proposal, in the EEPS I only found tuple comprehensions EEP12 and  multigenerators EEP19.

I didn't say that there was an unfold EEP,
I said that a certain syntax had been proposed (by me,
in this mailing list) and that there had been an
unfold proposal (also by me, also in this mailing list).

The unfold approach I described used

	your_unfold(Your_State) -> [] or [Next|Your_State']

However, Haskell has led the way.  What we really want is
something closer to streams.

A "stream" function maps a state to one of
	done
	{skip,New_State}
	{next,New_State,Item}

to_list(Unfolder, State) ->
    case Unfolder(State)
      of done                  -> []
       ; {skip,New_State}      -> to_list(Unfolder, New_State)
       ; {next,New_State,Item} -> [Item | to_list(Unfolder, New_State)]
    end.

The nice thing about streams is that they can handle mapping and
filtering.

s_map(F, Unfolder) ->
    fun (State) ->
        case R = Unfolder(State)
          of done               -> R
           ; {skip,State1}      -> R
           ; {next,State1,Item} -> {next,State1,F(Item)}
        end
    end.

s_filter(P, Unfolder) ->
    fun (State) ->
        case R = Unfolder(State)
          of done               -> R
           ; {skip,State1}      -> R
           ; {next,State1,Item} ->
             case P(Item)
               of false         -> {skip,State1}
                ; true          -> R
             end
        end
    end.

They can also handle a 'while':

s_while(P, Unfolder) ->
    fun (State) ->
        case R = Unfolder(State)
          of done               -> R
           ; {skip,State1}      -> R
           ; {next,State1,Item} ->
             case P(Item)
               of false         -> done
                ; true          -> R
             end
        end
    end.

So we can compose any chain of "map", "filter", and
"takeWhile" steps into a single unfolder->unfolder
function, which can then be applied to anything we
can convert to a stream, which includes lists,
integer ranges, tuples, and other things.

With a little ingenuity, we can squeeze in "expanding
the state" so that we can include "dropWhile", every Nth,
and other wrinkles into our chains.