Potenza cartesiana di una lista in Erlang

Question

Sto cercando di codificare un Erlang Mastermind risolutore come esercizio (io sono un novizio completo, ma mi sa che è un esercizio interessante per un linguaggio funzionale)

lo voglio per essere il più generale possibile, quindi sento di aver bisogno di una funzione di alimentazione cartesiana. Qualcosa di simile:

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

Non riesco a pensare ad una soluzione puramente funzionale (ricorsiva, mappa, piega ...). Eventuali indizi? Bonus se è pigro.

Answer 1

È possibile trovare questa domanda di sovraccarico dello stack utile, che si occupa della generazione della potenza cartesiana di un elenco in lingue funzionali. La domanda è mirato per F #, ma c'è un esempio Haskell nei commenti così: F#: how to find Cartesian power

Answer 2

Da implementazione Haskell:

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

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

Non sei sicuro di come si può fare liste di Erlang pigro però.

Aggiornamento: Questa versione può essere migliorato in termini di prestazioni, semplicemente rendendo ricorsiva in coda (anche se credo che ci sia alcuna differenza asintotica tra tutti e tre)

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 confronto con @ La versione di 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: O ancora meglio:

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

Answer 3

La soluzione fornita da @ Ed'ka è laconica e piacevole, ma nonostante ciò, la sua complessità è O(N).

Si consiglia di prendere in considerazione Exponentiation by squaring method, che fornisce la complessità O(log(N)) nei calcoli di potenza. Utilizzando questa tecnica, il potere cartesiano può essere implementato in questo modo:

%% 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. Esempio di utilizzo da shell (ho funzione cart confezionato in 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]]