Cartesian Power of a list in Erlang

Question

I'm trying to code an erlang Mastermind solver as an exercise (I'm a complete newbie, but I reckon it's an interesting exercise for a functional language)

I want it to be as general as possible, so I feel that I need a Cartesian Power function. Something like:

cart_pow([a,b],2) -> [[a,a],[a,b],[b,a],[b,b]]
cart_pow([a,b],3) -> [[a,a,a],[a,a,b],[a,b,a],[a,b,b],[b,a,a],[b,a,b],[b,b,a],[b,b,b]]

I can't think of a purely functional (recursive, map, fold...) solution. Any clues? Bonus if it's lazy.

Answer 1

Solution provided by @Ed'ka is laconic and nice, but despite this, its complexity is O(N).

I'd suggest you to take into account Exponentiation by squaring method, which provides O(log(N)) complexity in calculations of power. Using this technique, cartesian power may be implemented in such way:

%% Entry point
cart(List, N) ->
        Tmp = [[X] || X <- List],
        cart(Tmp, Tmp, N).

cart(_InitialList, CurrList, 1) ->
        CurrList;
cart(_InitialList, CurrList, N) when N rem 2 == 0 ->
        Tmp = mul(CurrList, CurrList),
        cart(Tmp, Tmp, N div 2);
cart(InitialList, CurrList, N) ->
        Tmp = cart(InitialList, CurrList, N - 1),
        mul(InitialList, Tmp).

mul(L1, L2) ->
        [X++Y || X <- L1, Y <- L2].

P.S. Example of usage from shell (I've packed function cart into mudule my_module):

1> c(my_module).
{ok,my_module}
2> 
2> my_module:cart([0,1], 2).
[[0,0],[0,1],[1,0],[1,1]]
3> 
3> my_module:cart([0,1], 3).
[[0,0,0],
 [0,0,1],
 [0,1,0],
 [0,1,1],
 [1,0,0],
 [1,0,1],
 [1,1,0],
 [1,1,1]]

Answer 2

From Haskell implementation:

cart_pow(Xs, N) -> 
    sequence(lists:duplicate(N, Xs)).

sequence([]) ->
    [[]];
sequence([Xs|Xss]) ->
    [[X|Xs1] || X <- Xs, Xs1 <- sequence(Xss)].

Not sure how you can make Erlang's lists lazy though.

Update: This version can be improved in terms of performance by simply making it tail-recursive (even though I believe there is no asymptotic differences between all three)

cart_pow(Xs, N) -> 
    sequence(lists:duplicate(N, Xs)).

sequence(Xss) ->
    sequence(Xss, [[]]).

sequence([], Acc) ->
    Acc;
sequence([Xs|Xss], Acc) ->
    sequence(Xss, [[X|Xs1] || X <- Xs, Xs1 <- Acc]).

In comparison with @stemm's version:

1> timer:tc(fun() -> length(tmp1:cart([0,1], 20)) end).
{383939,1048576}
2> timer:tc(fun() -> length(tmp1:cart_pow([0,1], 20)) end).
{163932,1048576}

PS: Or even better:

sequence(Xss) ->
    lists:foldl(fun(Xs, A) -> [[X|Xs1] || X <- Xs, Xs1 <- A] end, [[]], Xss).