0

私は Haskell でコーディングを行ってきましたが、ユニオン関数を実装するというアイデアを理解できませんでした。また、Haskell プラットフォーム内に埋め込まれた関数定義もいくつか見つけました。しかし、問題は、それを機能させるためのきちんとしたわかりやすい方法が必要なことです。誰でもそれで私を助けることができますか？

4

2 に答える 2

11

union :: Eq a => [a] -> [a] -> [a]which が 2 つの入力リストを取り、各引数リストのすべての要素を含む 3 番目のリストを返すことについて話していると仮定すると、それはパッケージ内Data.Listの which で定義されます。base

ソースでは、2 つの関数に分割されています。一般化された関数unionByは、等値のカスタム定義 (型が equal の関数) を受け取り、等値の具体的な実装として渡すことによって型クラス(==) :: a -> a -> Boolを使用する関数を定義します。Eq(==)

union                   :: (Eq a) => [a] -> [a] -> [a]
union                   = unionBy (==)

ただし、Haskell では等式推論を使用できるため(==)、コードに置き換えることができます。unionBy

union = unionBy (==)

-- so...

union       :: Eq a => [a] -> [a] -> [a]
union xs ys =  xs ++ foldl (flip (deleteBy (==))) (nubBy (==) ys) xs

この同じパターンはunionByindeleteByとの定義でさらに 2 回発生しますがnubBy、どちらも同じ規則に従います。deleteリストから要素を削除し、nub一意の要素のリストを返します。定義を単純化して のすべての痕跡を取り除き(==)、単純に要素aがEq定義されていると仮定します。

union xs ys = xs ++ foldl (flip delete) (nub ys) xs

これで、定義がおそらくより読みやすくなりました。とのunionは、によって処理された一意の (「ベッド」) 値に追加されます。その最終的な結果は、 fromの各要素を1 つずつ試行することです。それが最終的に意味することは、以下の要素からそれぞれの一意の要素に追加される ことです。xsysxsnubysfoldl (flip delete) _ xsfoldldeletexs(nub ys)union xs ysxsysxs

余談ですが、このソースを手にunionすると、最初の引数の重複を 2 番目の引数とは異なる方法で処理する方法など、いくつかの風変わりな動作に気付くことができます。

union [1,1,2] [2] == [1,1,2]
union [2] [1,1,2] == [2,1]

のような概念[]を表すために を使用した結果です。ただし、 を使用して結果を表示する場合は問題ありません。SetunionSet.fromList

xs, ys :: Eq a => [a]
Set.fromList (xs `union` ys) == Set.fromList xs `Set.union` Set.fromList ys

また、別の定義を提供しますunion

union xs ys = Set.toList (Set.fromList xs `Set.union` Set.fromList ys)

foldlでは、そのトリックはどのように機能するのでしょうか。to seeの定義を展開してみましょうfoldl。再び等式の推論を悪用します。

union xs ys = xs ++ (case xs of
  []      -> nub ys
  (x:xs') -> foldl (flip delete) (delete x (nub ys)) xs'
  )

これにより、トリックがより明確になります。 の要素を循環し、xsから 1 つずつ削除します(nub ys)。

unionこれがコードをもう少し明確にするのに役立つことを願っていますが、真の意味は、等式推論が Haskell コードを分析するための強力なツールであるということです。関数の定義を手動でインライン化して、コードを直接単純化することを恐れないでください。

于 2013-10-08T02:49:50.083 に答える