特定のリストのパワーセットを生成しようとしているときに、インターネット経由でこの関数に出会いました。説明はありませんでしたが、テストの結果、正しく動作しているように見えます。この機能がどのように機能しているのか理解できません。そのような説明に感謝します。
generateSubset [] = [[]]
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p
特定のリストのパワーセットを生成しようとしているときに、インターネット経由でこの関数に出会いました。説明はありませんでしたが、テストの結果、正しく動作しているように見えます。この機能がどのように機能しているのか理解できません。そのような説明に感謝します。
generateSubset [] = [[]]
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p
簡単に証明できるベキ集合の性質を次に示します。 P(A ∪ B) = {a ∪ b | a ∈ P(A), b ∈ P(B)}. 特に、特定の集合 S を要素 s と、s ではないすべての要素 S' に分解すると、
P(S) = P({s} ∪ S')
= {a ∪ b | a ∈ P({s}), b ∈ P(S')}.
ここで、P({s}) は十分に小さいので、手で計算できます: P({s}) = {{}, {s}}。この事実を使って、私たちは学びます
P(S) = {a ∪ b | a ∈ {{}, {s}}, b ∈ P(S')}
= {b | b ∈ P(S')} ∪ {{s} ∪ b | b ∈ P(S')}
= P(S') ∪ {{s} ∪ b | b ∈ P(S')}
= let p = P(S') in p ∪ {{s} ∪ b | b ∈ p}
つまり、空でないセットの累乗を計算する 1 つの方法は、要素を選択し、剰余の累乗を計算してから、各サブセットに要素を追加するか追加しないかのいずれかです。あなたが示した関数は、リストをセットの表現として使用して、これを単純にコードに変換します。
-- P ({s} ∪ S') = let p = P(S') in p ∪ {{s} ∪ b | b ∈ p}
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p
残っている唯一のことは、再帰の基本ケースを与えることです。これは、べき乗セットの定義から直接得られます。
-- P ({}) = {{}}
generateSubset [] = [[]]
あなたが与えたコードは、Haskell のシンタックス シュガーを多く使用しています。(セマンティクスについては他の人が既に説明しているので、ここでは省略します。)コードで気づいた主な構文は次のとおりです。
型注釈の欠如。Haskell は型推論を使用するため、型注釈はオプションになります (ただし推奨されます)。GHCi を使用して型を決定します。
*Main> :t generateSubset
generateSubset :: [a] -> [[a]]
パターンマッチング。素敵な紹介については、LYAHを参照してください。
式をしましょう。もう一度、LYAHを参照してください。
一部適用 - (x:)
。 勝利のためのLYAH!
演算子セクション --(x:)
再び。これにより、中置関数 (この場合は:
) の部分的な適用が可能になります。以下と同じです:
myCons :: a -> [a] -> [a]
myCons e es = e : es
myPartial :: [a] -> [a]
myPartial = myCons x -- partial application
関数/演算子の優先順位の使用 -- p ++ map (x:) p
. 関数の適用は常に中置演算子の適用よりも優先(p) ++ (map (x:) p)
されるため、これは として解析されます。
空リストの冪集合は、空リストのみを含むリストです。
空でないリストの累乗を計算するには、最初にテールの累乗を計算します。次に、そのパワー セットを、ヘッドがすべてのサブセットの先頭に追加されたバージョンのパワー セットと連結します。したがって、テールのパワー セットが[[2,3],[2],[3],[]]
で、ヘッドの1
パワー セットが である場合、結果のパワー セットは になります[[], [3], [2], [2,3], [1],[1,3],[1,2],[1,2,3]]
。