Haskellで2つのリストのデカルト積を作成したいのですが、その方法がわかりません。デカルト積は、リスト要素のすべての組み合わせを提供します。
xs = [1,2,3]
ys = [4,5,6]
cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
これは実際の宿題の質問ではなく、そのような質問とは関係ありませんが、この問題を解決する方法は、私が立ち往生している問題に役立つ可能性があります。
これは、リスト内包表記を使用すると非常に簡単です。xsリストとのデカルト積を取得するには、の各要素と の各要素のysタプルを取得するだけです。(x,y)xxsyys
これにより、次のリスト内包表記が得られます。
cartProd xs ys = [(x,y) | x <- xs, y <- ys]
他の回答が指摘しているように、リスト内包表記を使用することは、Haskell でこれを行う最も自然な方法です。
ただし、 Haskell を学んでいて、 のような型クラスに関する直感を開発したい場合はMonad、このわずかに短い定義が同等である理由を理解するのは楽しい演習です。
import Control.Monad (liftM2)
cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)
これを実際のコードで書きたいとは思わないかもしれませんが、基本的な考え方は Haskell で常に見られるものです:liftM2非モナド関数(,)をモナドに持ち上げるために使用しています。リストモナド。
これが意味をなさない、または役に立たない場合は、忘れてください。これは、問題を別の方法で見るだけです。
sequence入力リストが同じタイプの場合、 (Listモナドを使用して)を使用して、任意の数のリストのデカルト積を取得できます。これにより、タプルのリストではなくリストのリストが取得されます。
> sequence [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
Applicative Functor を使用してこれを行う非常にエレガントな方法があります。
import Control.Applicative
(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]
基本的な考え方は、「ラップされた」引数に関数を適用することです。
(+) <$> (Just 4) <*> (Just 10)
-- Just 14
リストの場合、関数はすべての組み合わせに適用されるため、それらを で「タプル」するだけ(,)です。
http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functorsまたは (より理論的な) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdfを参照してください。詳細。
他の回答では、2 つの入力リストが有限であると仮定しています。慣用的な Haskell コードには無限リストが含まれることが多いため、必要な場合に備えて、無限デカルト積を生成する方法について簡単にコメントしておく価値があります。
標準的なアプローチは、対角化を使用することです。1 つの入力を上部に、もう 1 つの入力を左側に書き出すと、完全なデカルト積を含む 2 次元のテーブルを次のように書くことができます。
1 2 3 4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...
. . . . . .
. . . . . .
. . . . . .
もちろん、任意の 1 つの行で作業すると、次の行に到達する前に要素が無限に得られます。同様に、列方向に進むと悲惨なことになります。しかし、グリッドの端に到達するたびに少し右から始めて、左に下る対角線に沿って進むことができます。
a1
a2
b1
a3
b2
c1
a4
b3
c2
d1
...等々。順番に、これは私たちに与えるでしょう：
a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...
これを Haskell でコーディングするには、まず 2 次元のテーブルを生成するバージョンを記述します。
cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]
対角化の非効率的な方法は、最初に対角線に沿って反復し、次に各対角線の深さに沿って反復し、毎回適切な要素を引き出すことです。説明を簡単にするために、両方の入力リストが無限であると仮定します。そのため、境界チェックをいじる必要はありません。
diagonalBad :: [[a]] -> [a]
diagonalBad xs =
[ xs !! row !! col
| diagonal <- [0..]
, depth <- [0..diagonal]
, let row = depth
col = diagonal - depth
]
この実装は少し残念です。リストのインデックス作成操作を繰り返すと、処理!!が進むにつれてコストが高くなり、漸近的なパフォーマンスがかなり低下します。より効率的な実装では、上記のアイデアを使用しますが、zipper を使用して実装します。したがって、無限グリッドを次のように 3 つの形状に分割します。
a1 a2 / a3 a4 ...
/
/
b1 / b2 b3 b4 ...
/
/
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...
. . . . .
. . . . .
. . . . .
左上の三角形は、既に発行したビットです。右上の四角形は、部分的に放出されたが結果に寄与する行になります。一番下の四角形は、まだ出力を開始していない行になります。まず、上の三角形と上の四角形が空になり、下の長方形がグリッド全体になります。各ステップで、上部の四辺形の各行の最初の要素を放出し (基本的に斜線を 1 つ移動)、下部の四角形から上部の四辺形に新しい行を 1 つ追加します (基本的に水平線を 1 つ下に移動します)。 ）。
diagonal :: [[a]] -> [a]
diagonal = go [] where
go upper lower = [h | h:_ <- upper] ++ case lower of
[] -> concat (transpose upper')
row:lower' -> go (row:upper') lower'
where upper' = [t | _:t <- upper]
これは少し複雑に見えますが、はるかに効率的です。また、単純なバージョンでパントした境界チェックも処理します。
しかし、もちろん、このコードをすべて自分で書くべきではありません! 代わりに、universeパッケージを使用する必要があります。Data.Universe.Helpersには、(+*+)上記cartesian2dとdiagonal機能をまとめてデカルト積演算を与える があります。
Data.Universe.Helpers> "abcd" +*+ [1..4]
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)]
その構造が役立つ場合は、対角線自体も表示できます。
Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4]
[('a',1)]
[('a',2),('b',1)]
[('a',3),('b',2),('c',1)]
[('a',4),('b',3),('c',2),('d',1)]
[('b',4),('c',3),('d',2)]
[('c',4),('d',3)]
[('d',4)]
一緒に製品化するリストが多数ある場合、反復(+*+)によって特定のリストに不当な偏りが生じる可能性があります。choices :: [[a]] -> [[a]]n次元デカルト積のニーズに使用できます。
これを実現するさらに別の方法は、アプリケーションを使用することです。
import Control.Applicative
cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys
さらに別の方法では、do表記法を使用します。
cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
y <- ys
return (x,y)
他の人がすでに指摘しているように、正しい方法はリスト内包表記を使用することですが、何らかの理由でリスト内包表記を使用せずにそれを行いたい場合は、次のようにすることができます。
cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys
これを行う非常に簡単な方法の 1 つは、リスト内包表記を使用することです。
cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = [(x, y) | x <- xs, y <- ys]
私はHaskellの専門家ではありませんが（決して）、これを行う方法だと思います。
何かのようなもの：
cartProd x y = [(a,b) | a <- x, b <- y]
これが私の n 項デカルト積の実装です。
crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]
リスト内包表記を使用しない再帰パターン マッチング
crossProduct [] b=[]
crossProduct (x : xs) b= [(x,b)] ++ crossProduct xs b
cartProd _ []=[]
cartProd x (u:uv) = crossProduct x u ++ cartProd x uv