リストを可能なすべてのタプルのリストに分割する必要がありますが、その方法がわかりません。
例えば：
pairs ["cat","dog","mouse"]
結果は次のようになります。
[("cat","dog"), ("cat","mouse"), ("dog","cat"), ("dog","mouse"), ("mouse","cat"), ("mouse","dog")]
最初の 2 つは作成できましたが、残りの 2 つを取得する方法がわかりません。
これが私がこれまでに持っているものです：
pairs :: [a] -> [(a,a)]
pairs (x:xs) = [(m,n) | m <- [x], n <- xs]
この答えは 2 つの部分に分かれています。最初の部分は、質問に直接対処します。2 番目の部分は、最初の部分の背後にある数学を掘り下げるために、(文字通り) 接線で始まります。したがって、それは限られた関心の難しい資料であることが判明するかもしれませんが、少数の過激派がそれを楽しむかもしれないと思いました。
私がこれまで見てきた答えは、リスト内包表記またはそれに相当するモナドをうまく利用していますが、重複を除外するために等値Eqを使用しているため、追加の制約が必要です。これは、要素のすべてのペアを 2 つの異なる位置に作成するソリューションです。
最初に、リストの各要素を他の位置にある要素のリストで装飾する便利な関数を作成します。「1 つを選択して他の要素を残す」すべての方法です。これは、リストを使用して置換なしで選択するためのものを収集する場合に非常に便利であり、私がよく使用するものです。
picks :: [x] -> [(x, [x])]
picks [] = []
picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs]
map fst . picks = id結果の各位置で選択された要素は、元のリストのその位置の要素になることに注意してください。これが、「装飾する」という意味です。
他の回答と同じリスト内包表記法を使用して、2 つを簡単に選択できるようになりました。ただし、リスト自体から最初のコンポーネントを選択する代わりに、そのリストから選択するpicksと同時に、2 番目のコンポーネントの候補リストを取得できます。
allPairs :: [x] -> [(x, x)]
allPairs xs = [(y, z) | (y, ys) <- picks xs, z <- ys]
トリプルを取るのも同じくらい簡単picksです。
allTriples :: [x] -> [(x, x, x)]
allTriples ws = [(x, y, z) | (x, xs) <- picks ws, (y, ys) <- picks xs, z <- ys]
統一性を保つために、コードの効率を少し下げて、両方(z, _) <- picks ysではなく書くことにほとんど魅力を感じます。z <- ys
入力リストに重複がない場合、タプルは異なる位置から要素を取得するため、出力に重複するタプルはありません。しかし、あなたは得るでしょう
Picks> allPairs ["cat", "cat"]
[("cat","cat"),("cat","cat")]
これを回避するには、選択前に重複を削除し、要素タイプのインスタンスをallPairs . nubもう一度要求する を自由に使用してください。Eq
過激主義者のみ: コンテナー、微積分、コモナド、組み合わせ論アホイ!
picksは、微分計算から生じる、より一般的な構造の 1 つのインスタンスです。functor の任意のコンテナ型ソートについてf、その数学的導関数 ∂ffが 1 つの要素が削除された構造体を表すというのは面白い事実です。例えば、
newtype Trio x = Trio (x, x, x) -- x^3
導関数を持つ
data DTrio x = Left3 ((), x, x) | Mid3 (x, (), x) | Right3 (x, x, ()) -- 3*x^2
この構造には、多くの操作を関連付けることができます。∂ を実際に使用できると想像してください (そして、型ファミリを使用してコード化できます)。次に、次のように言うことができます
data InContext f x = (:-) {selected :: x, context :: ∂f x}
コンテキストによって装飾された選択された要素のタイプを指定します。私たちは確かに手術を受けることを期待すべきです
plug :: InContext f x -> f x -- putting the element back in its place
このplug操作は、ノードがサブツリーのコンテナーと見なされるツリー内をジッパーで移動している場合、ルートに向かって移動します。
InContext fまた、私たちは共通点になることを期待する必要があります。
counit :: InContext f x -> x
counit = selected
選択した要素を投影し、
cojoin :: InContext f x -> InContext f (InContext f x)
すべての要素をそのコンテキストで装飾し、再フォーカスできるすべての可能な方法を示し、別の要素を選択します。
計り知れないピーター・ハンコックはかつて、構造全体からコンテキスト内の要素を選択するためのすべての可能な方法を収集して、「下に」(「ルートから離れる」ことを意味する) 移動できることも期待すべきであると私に示唆しました。
picks :: f x -> f (InContext f x)
x入力構造内のすべての要素fをそのコンテキストで装飾する必要があります。私たちはそれを期待すべきです
fmap selected . picks = id
これは私たちが以前に持っていた法則ですが、
fmap plug (picks fx) = fmap (const fx) fx
装飾されたすべての要素が元のデータの分解であることを示しています。上記の法律はありませんでした。我々は持っていた
picks :: [x] -> [(x, [x])]
すべての要素をそのコンテキストに少し似たもので装飾するわけではありません。他の要素のリストだけでは、「穴」がどこにあるのかわかりません。実は、
∂[] x = ([x], [x])
穴の前の要素のリストを穴の後の要素から分離します。間違いなく、私は書くべきだった
picks :: [x] -> [(x, ([x], [x]))]
picks [] = []
picks (x : xs) = (x, ([], xs)) : [(y, (x : ys, ys')) | (y, (ys, ys')) <- picks xs]
これも確かに非常に便利な操作です。
しかし、実際に起こっていることは非常に理にかなっていて、わずかな乱用にすぎません。私が最初に書いたコードでは、局所的に有限のバッグまたは順序なしリスト[]を表現しています。バッグは特定の位置の概念を持たないリストであるため、1 つの要素を選択すると、そのコンテキストは残りの要素のバッグになります。それはそう
∂Bag = Bag -- really? why?
の正しい概念picksは確かに
picks :: Bag x -> Bag (x, Bag x)
で表すBagと[]、それが私たちが持っていたものです。さらに、バッグの場合、plugは公正(:)であり、バッグの平等 (つまり順列) までは、 の第 2 法則picks が成り立ちます。
バッグのもう 1 つの見方は、ベキ級数です。バッグは、任意のサイズのタプルの選択であり、すべての可能な順列 (サイズn に対してn! ) が識別されます。したがって、x^n を n で除算する必要があるため、階乗で商を求めた累乗の大きな和として組み合わせて書くことができます。n! x を選択できた注文では、同じバッグが提供されます。
Bag x = 1 + x + x^2/2! + x^3/3! + ...
それで
∂Bag x = 0 + 1 + x + x^2/2! + ...
シリーズを横にシフトします。Bag実際、ベキ級数 forがexp(またはe ^x)のベキ級数であることに気付いたかもしれません。これは、独自の導関数であることで有名です。
それで、ふー！ほらね。指数関数のデータ型解釈から自然に生じる操作は、それ自体の導関数であり、置換なしの選択に基づいて問題を解決するための便利なキットです。
リスト内包表記を使用できます。
allpairs :: Eq a => [a] -> [(a,a)]
allpairs xs = [ (x1,x2) | x1 <- xs, x2 <- xs, x1 /= x2 ]
私のアプローチは、他の人のアプローチと多少似ています。必要ありませんEq。
allpairs :: [t] -> [(t,t)]
allpairs [] = []
allpairs [_] = []
allpairs (x:xs) = concatMap (\y -> [(x,y),(y,x)]) xs ++ allpairs xs
もう 1 つの可能性は、モナド表記を使用することです。
pairs :: (Eq a) => [a] -> [(a,a)]
pairs l = do
x <- l
y <- l
guard (x /= y)
return (x, y)
(この定義の最も一般的なタイプは にpairsなりますが、それが意味を成す以外(MonadPlus m, Eq a) => m a -> m (a,a)のインスタンスはないと思います。)MonadPlus[]
pairs = (filter.uncurry) (/=) . (join.liftA2) (,)
import Control.Applicative
pairs xs = filter (uncurry (/=)) $ (,) <$> xs <*> xs