lists:zip / zip_with / unzip etc

Thomas Arts <>
Mon Jul 8 09:12:48 CEST 2002


Heinz Eriksson wrote:

> Would this be ok to you then:
> 
> ziph([H1|L1],[H2|L2], Z) ->
>     [{H1,H2}|ziph(L1,L2,Z)];
> ziph([],[], Z) ->
>     Z.
> 
> zip(A,B) ->
>     ziph(A,B,[]).
> 
> ?
> Is that tail recursive?
> Or how shall it be done.

No, this makes no sense. You don't use the last argument!
It is not tail recursive if you just add a last argument,
you need to really use it.

ziph([H1|L1],[H2|L2], Z) ->
    ziph(L1,L2,[{H1,H2}|Z]);
ziph([],[], Z) ->
    Z.
 
zip(A,B) ->
    ziph(A,B,[]).

and this solution accepts only lists of equal length,
which is perfectly fine with me.

See tail recursion as "not using the callstack". In your
version of ziph you push the value {H1,H2} on the stack,
call ziph recusively and when the answer returns, you add the
value on the stack on top of it. In the tail-recursive
example above, you construct the value and call the ziph
function with empty callstack, but growing argument.
Problem is, of course, that your new list is reversed. This need
not be a problem, but is not very nice.

ziph([H1|L1],[H2|L2], Z) ->
    ziph(L1,L2,Z++[{H1,H2}]);
ziph([],[], Z) ->
    Z.

would give you the right order, but this version has a
higher complexity. Appending to the end of the list becomes
more expesive every time you increase the length of the 
list. Thus the number of "list traversels" is 1+2+...+N, instead
of the N times you need in the non tail recursive case.
Note that it is even faster to build a reversed list and
use the reverse function afterward (viz. 2*N) instead of
doing the above.

Unless the lists are expected to be really, really long, I
would advocate for the simple solution:

zip([],[]) -> 
  [];
zip([H1|T1],[H2|T2]) ->
  [{H1,H2}|zip(T1,T2)].

In case your lists are expected to be really long, think
about another data structure, like balanced trees.

/Thomas



More information about the erlang-questions mailing list