4

特定のリストのパワーセットを生成しようとしているときに、インターネット経由でこの関数に出会いました。説明はありませんでしたが、テストの結果、正しく動作しているように見えます。この機能がどのように機能しているのか理解できません。そのような説明に感謝します。

generateSubset [] = [[]]
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p
4

3 に答える 3

10

簡単に証明できるベキ集合の性質を次に示します。 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 []  = [[]]
于 2012-08-16T13:43:47.163 に答える
4

あなたが与えたコードは、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)されるため、これは として解析されます。

于 2012-08-16T13:55:19.263 に答える
2

空リストの冪集合は、空リストのみを含むリストです。

空でないリストの累乗を計算するには、最初にテールの累乗を計算します。次に、そのパワー セットを、ヘッドがすべてのサブセットの先頭に追加されたバージョンのパワー セットと連結します。したがって、テールのパワー セットが[[2,3],[2],[3],[]]で、ヘッドの1パワー セットが である場合、結果のパワー セットは になります[[], [3], [2], [2,3], [1],[1,3],[1,2],[1,2,3]]

于 2012-08-16T13:40:00.970 に答える