在二郎一个列表

Question

我试图求解器编写一个Erlang策划作为一个练习（我是一个完整的新手，但我认为这是一个有趣的练习函数式语言）

我想它的笛卡尔电源尽可能通用，所以我觉得我需要一个笛卡尔函数。就像：

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]] 

我想不出一个纯粹的功能（递归，地图，折叠...）的解决方案。 任何线索？奖金，如果它是懒惰的。

Answer 1

你可能会发现这个堆栈溢出问题很有帮助，它处理在函数式语言中产生一个列表的笛卡尔功效。现在的问题是针对F＃，但在评论Haskell的例子还有：F#: how to find Cartesian power

Answer 2

从Haskell的实现：

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

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

不知道如何可以使Erlang的名单懒虽然。

更新： 这个版本在性能方面通过简单地使其尾递归（虽然我相信这是所有三个之间没有渐近差异）

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]). 

在比较@得到改善stemm的版本：

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：甚至更​​好：

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

Answer 3

由@ Ed'ka提供的解决方案简洁而好看，但尽管如此，它的复杂性却是O(N)。

我建议你考虑Exponentiation by squaring method，它提供了O(log(N))复杂的功率计算。使用这种技术，笛卡尔功率可以用这种方式实现：

%% 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.从壳（我已经打包功能cart成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]]