12

2 つのリストが与えられると、これら 2 つのリストのデカルト積であるすべての順列のリストを作成できます。

permute :: [a] -> [a] -> [[a]]
permute xs ys = [ [x, y] | x <- xs, y <- ys ]

Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ]

permute を拡張して、2 つのリストを取得する代わりに、リスト (長さ n) のリストを取得し、リスト (長さ n) のリストを返すようにするにはどうすればよいですか?

permute :: [[a]] -> [[a]]

Example> permute [ [1,2], [3,4], [5,6] ]
            == [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc

Hoogle で関連するものを見つけることができませんでした.署名に一致する唯一の関数はtranspose、目的の出力を生成しない でした。

編集:これの2リストバージョンは本質的にデカルト積だと思いますが、 n-aryデカルト積の実装に頭を悩ませることはできません。ポインタはありますか？

4

6 に答える 6

22 
Prelude> sequence [[1,2],[3,4],[5,6]]
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
于 2010-08-02T11:55:55.737 に答える
6

LINQ を使用したデカルト積の計算に関する Eric Lippert の記事は、何が起こっているのかについての理解を深めるのに非常に役立ちました。多かれ少なかれ直訳は次のとおりです。

cartesianProduct :: [[a]] -> [[a]]
cartesianProduct sequences = foldr aggregator [[]] sequences
                   where aggregator sequence accumulator = 
                         [ item:accseq |item <- sequence, accseq <- accumulator ]

または、より「Haskell-y」の簡潔で無意味なパラメーター名を使用します;)

cartesianProduct = foldr f [[]]
                    where f l a = [ x:xs | x <- l, xs <- a ]

これは結局のところ、投稿された sclv と非常によく似ています。

于 2010-08-02T14:30:29.493 に答える
3

jleedevの回答の補足として（コメントでこれをフォーマットできませんでした）：

リスト関数をモナド関数にチェックなしで簡単に置き換える:

sequence ms = foldr k (return []) ms
   where
    k m m' = do { x <- m; xs <- m'; return (x:xs) }

....

    k m m' = m >>= \x -> m' >>= \xs -> [x:xs]
    k m m' = flip concatMap m $ \x -> flip concatMap m' $ \xs -> [x:xs]
    k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m

.... 

sequence ms = foldr k ([[]]) ms
   where
     k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m
于 2010-08-02T12:36:49.053 に答える
2

出力をより細かく制御したい場合は、リストを適用ファンクターとして使用できます。次に例を示します。

(\x y z -> [x,y,­z]) <$>  [1,2]­ <*> [4,5]­ <*> [6,7]

代わりにタプルのリストが必要だとしましょう:

(\x y z -> (x,y,­z)) <$>  [1,2]­ <*> [4,5]­ <*> [6,7]

そして、それはまた、ちょっとクールに見えます...

于 2010-08-03T12:05:13.620 に答える