e r l a n g : c o o k b o o k

This Web

All Webs

Erlang Links

Erlang Web Ring

Traversing Multiple Lists

Problem

You want to traverse multiple source lists in a nested fashion, but do not want to define nested functions.

For example, given two lists [a,b,c] and [1,2], you want to apply a function to each of [a,1], [a,2], [b,1], [b,2], [c,1], and [c,2].

In English, this problem might be something like "for each product, for each day of the week, produce a report of sales".

Solution

Convert a source list of lists into a target list of lists, then apply one of the map, foreach, foldl (etc) functions to it.

The new loop_lists function should behave as follows:

1> loop_lists([[spanner, screwdriver],[monday,tuesday,wednesday]]).
[[spanner,monday],
 [spanner,tuesday],
 [spanner,wednesday],
 [screwdriver,monday],
 [screwdriver,tuesday],
 [screwdriver,wednesday]]

The function should be generic enough to handle any number of source lists; the number of elements in each target list will be equal to the number of source lists.

1> loop_lists([[a,b],[x,y],[1,2,3]]).
[[a,x,1],
 [a,x,2],
 [a,x,3],
 [a,y,1],
 [a,y,2],
 [a,y,3],
 [b,x,1],
 [b,x,2],
 [b,x,3],
 [b,y,1],
 [b,y,2],
 [b,y,3]]

The function would be used with the map/foreach/fold functions, or with list comprehensions.

> lists:map(MyFunction, loop_lists([ProductList,DayList])).
> [MyFunction(ProdDay) || ProdDay <- loop_lists([ProductList,DayList])].

Attempt #1

loop_lists([]) -> [[]];
loop_lists([H|[]]) -> [[X] || X <- H];
loop_lists([H|T]) -> [[X|Y] || X <- H, Y <- loop_lists(T)].

Discussion #1

This version works, but is not tail-recursive.

Attempt #2

loop_lists(L) -> loop_lists(L, []).
loop_lists([], Acc) -> Acc;
loop_lists([H|T], []) -> loop_lists(T, [[X] || X <- H]);
loop_lists([H|T], Acc) -> loop_lists(T, [lists:append(X, [Y]) || X <- Acc, Y <- H]).

Discussion #2

This version is tail-recursive, but uses lists:append, which may have a significant performance impact with larger lists.

Attempt #3

loop_lists(L) -> loop_lists(lists:reverse(L), []).
loop_lists([], Acc) -> Acc;
loop_lists([H|T], []) -> loop_lists(T, [[X] || X <- H]);
loop_lists([H|T], Acc) -> loop_lists(T, [[X|Y] || X <- H, Y <- Acc]).

Discussion #3

This version is tail-recursive. It uses lists:reverse once on the initial source list so that the target lists are accumulated in the correct order.

This version is probably the best of attempts 1-3, but still requires some amount of memory to hold the resulting looping list.

Comments about this recipe

Nested functions can be used to loop through multiple lists...

Fun1 = fun(Element1) ->
    Fun2 = fun(Element2) ->
        Fun3 = fun(Element3) ->
            DoSomething([Element1, Element2, Element3])
        end,
        lists:foreach(Fun3, List3)
    end,
    lists:foreach(Fun2, List2)
end,
lists:foreach(Fun1, List1).

... but I find that the eqivalent code using loop_lists to be much easier on the eyes:

lists:map(fun(X) -> DoSomething(X) end, loop_lists([List1, List2, List3])).

Contributors

-- PhilipRobinson - 15 Jun 2006