Erlang un-zip-flatten

Question

I have a list of items that I would like to "un-zip-flatten". Basically what that means is that if I have a list of items:

[a, b, c, d, e, f, g]

I want to turn it into a list of lists like the following:

[[a, d, g], [b, e], [c, f]]

So far my solution looks like this:

unzipflatten(NumberOfLists, List) ->
    lists:map(fun(Start) ->
                      lists:map(fun(N) ->
                                        lists:nth(N, List)
                                end,
                                lists:seq(Start, length(List), NumberOfLists))
              end,
              lists:seq(1, NumberOfLists)).

I'm pretty new to Erlang so I'm wondering if I've missed some standard library function that would do what I want, or if there's a more "Erlangish" way to do this, or if the performance of my above solution will stink.

Answer 1

I think this would be a more "Erlangish" method to do this. Basically you would create the list of lists that will be your result, and use two lists to manage those lists like a queue. The "Heads" list contains the lists that you will prepend to next, and the "Tails" list are the ones most recently prepended to. When Heads is empty you simply reverse Tails and use that as the new Heads. Before returning the result you will need to reverse all of the lists inside Tails and Heads and then append Heads as-is to the reversed Tails. Excuse the confusing variable names, I think coming up with several good names for breaking up lists in an Erlang program is the hardest part ;)

unzipflatten(NumberOfLists, List) when NumberOfLists > 0 ->
    unzipflatten(List, lists:duplicate(NumberOfLists, []), []).

unzipflatten([], Heads, Tails) ->
    [lists:reverse(L) || L <- lists:reverse(Tails, Heads)];
unzipflatten(L, [], Tails) ->
    unzipflatten(L, lists:reverse(Tails), []);
unzipflatten([Elem | Rest], [Head | Tail], Tails) ->
    unzipflatten(Rest, Tail, [[Elem | Head] | Tails]).

It's also possible to do the "unzip" phase in a non tail-recursive way to avoid the lists:reverse step, but that is a more complicated solution. Something like this:

unzipflatten(NumberOfLists, List) when NumberOfLists > 0 ->
    unzipflatten({List, lists:duplicate(NumberOfLists, [])}).

unzipflatten({[], Heads}) ->
    [lists:reverse(L) || L <- Heads];
unzipflatten({L, Heads}) ->
    unzipflatten(unzipper({L, Heads})).

unzipper({[], Heads}) ->
    {[], Heads};
unzipper({L, []}) ->
    {L, []};
unzipper({[H | T], [Head | Tail]}) ->
    {T1, Tail1} = unzipper({T, Tail}),
    {T1, [[H | Head] | Tail1]}.

Answer 2

Yes, performance will stink (basic advice for using lists:nth: never call it several times with growing N!). Something like this should be better (not tested):

unzipflatten(NumberOfLists, List) -> 
  unzipflatten(NumberOfLists, List, array:new(NumberOfLists, {default, []}), 0).

unzipflatten(_, [], Lists, _) -> 
  lists:map(fun lists:reverse/1, array:to_list(Lists));
unzipflatten(NumberOfLists, [H | T], Lists, CurrentIndex) ->
  NewLists = array:set(CurrentIndex, [H | array:get(CurrentIndex, Lists)], Lists),
  unzipflatten(NumberOfLists, T, NewLists, (CurrentIndex + 1) rem NumberOfLists).