Haskell の重複排除のサンプルコードについて

Question

Haskell において、リストから重複を排除するサンプルコードを調べたところ、以下のようなコードを発見しました。

import qualified Data.Set as Set

f :: Ord a => a -> (Set.Set a -> [a]) -> Set.Set a -> [a]
f x k ss = if Set.member x ss then k ss else x : k (Set.insert x ss)

g :: Ord a => [a] -> [a]
g xs = foldr f (const []) xs Set.empty

上記のコードは、確かに正しく動作します。

> g [1, 2, 2, 3, 3, 3]
[1, 2, 3]

上記のコードで、試しに g [1, 2] としたときの動作は、以下のようになるのだろうな、と推測しています。

foldr f (const[]) [1,2]
= f 1 (foldr f (const[]) [2])
= f 1 (f 2 (foldr f (const[]) [])
= f 1 (f 2 (const[]))

g [1, 2]
= foldr f (const[]) [1,2] {}  -- Set.empty = {} と考えています。
= f 1 (f 2 (const[])) {}
= 1 : (f 2 (const[])) {1}
= 1 : (2 : (const[]) {1, 2})
= 1 : (2 : []))
= [1, 2]

教えていただきたいことは、以下の２点です。
(1) 上記の考えは合っているでしょうか？
(2) 上記の考えで合っていたとしても、なんとなく釈然としません。もっと、すっきり理解する考え方はないでしょうか？特に、f の k の部分が分かりにくく感じています。

初心者の質問で大変申し訳ないですが、どうぞ宜しくお願いいたします。

Answer 1

foldrを使わずに、通常の再帰として実装する方が分かりやすいと思います。

ご提示のコードを、通常の再帰を用いて実装すると、以下のようになります。

h [] _ = []
h (x:xs) ss = if Set.member x ss then h xs ss else x : h xs (Set.insert x ss)

g xs = h xs Set.empty

こちらの書き方であれば、何をしているのか追いやすいのではないでしょうか。

あとは、こちらの関数をfoldrを使う形に変換することで、ご提示のコードと等しいことを示します。

foldrを使う形に変換するためには、以下の形の再帰呼び出しになっている必要があります。

h [] = v
h (x:xs) = f x (h xs)

こちらの形に近づけるため、先頭で示した関数hの最後の引数を、ラムダ式を用いて右辺に持っていきます。

h [] = \_ -> []
h (x:xs) = \ss -> if Set.member x ss then h xs ss else x : h xs (Set.insert x ss)

あとは、目的の形になるように関数fをくくり出します。ついでに、\_ -> []はconst []と同じ意味なので置き換えます。

f x k = \ss -> if Set.member x ss then k ss else x : k (Set.insert x ss)

h [] = const []
h (x:xs) = f x (h xs)

ここまでくれば、関数hをfoldrで書き換えることができます。ついでに、関数fの右辺のラムダ式の仮引数ssを、左辺の末尾の引数に持っていきます。

f x k ss = if Set.member x ss then k ss else x : k (Set.insert x ss)

h xs = foldr f (const []) xs

最後に、先頭で示した関数g内の関数hの呼び出しをfoldrに書き換えてあげれば、ご提示のコードに変換されます。

Comments

[KN2018]

大変詳しい解答を下さり、本当にありがとうございました。とても深く感謝しております！
まず最初に、通常の再帰で実装する方法を書いてくださり、「なるほど！」と目から鱗が落ちる思いでした。最初に foldr で実装されたサンプルコードを発見してしまったので、foldr ばかりで考えていたのですが、教えてくださったように再帰で解決するのが非常に自然ですね。教えてもらえれば非常に簡潔なコードで分かりやすいのですが、言われなければ自分では気付けなかったです。
次に、再帰で実装されたものを foldr に書き直す方法に、とても感動しました。今までの自分の経験では、fold に利用する関数が単純な2項演算子でしかなかったので、今回の様な「f x k ss」のような関数を、fold に組み込みたいと思った場合、どうすれば良いのか見当もつきませんでした。今回、このような考え方があるということを教えてもらえることができて、本当に感動しました。心から感謝しております。
f が２変数関数となるように、右結合であることを意識しながら「h (x:xs) = f x (h xs)」と、まずは書き下してみることが重要だったんですね。
自分ではまったく思い付くことができないことを、スラスラと理解できる方が世の中にはいらっしゃる、ということは当然のことだと思いますが、今回、そのことを改めて実感することができました。
今回は、コードの面だけでなく、人生という面からも良い勉強となりました。大変ありがとうございました。

Answer 2

こんにちは。

foldr f (const []) [1, 2]
= f 1 (foldr f (const []) [2])
= f 1 (f 2 (foldr f (const []) [])
= f 1 (f 2 (const []))

質問のここまでは問題ないです。
実際の結果となるリストを生成しているのは f の x : k (Set.insert x ss) この部分であって、
この Set は単に重複の検出にしか利用していないわけですね。

その点を意識したうえでこの関数を読み解くと、
この場合は f 1 (f 2 (const [])) を先に展開すればよく、

f2 :: Set.Set Int -> [Int]
f2 s = f 2 (const []) s
= if Set.member 2 s then const [] s else 2 : const [] (Set.insert 2 s)
= if Set.member 2 s then [] else 2 : [] -- const [] x == []
= if Set.member 2 s then [] else [2]

f1 :: Set.Set Int -> [Int]
f1 s = f 1 (f2) s
= if Set.member 1 s then f2 s else 1 : f2 (Set.insert 1 s)

このようにできます。

最後にこの関数に {} を入れることで、

f1 {} = if Set.member 1 {} then f2 {} else 1 : f2 {1} -- Set.member 1 {} == false
= 1 : f2 {1}
= 1 : if Set.member 2 {1} then [] else [2] -- Set.member 2 {1} == false
= 1 : [2]
= [1, 2]

このような順序で解決します。

よって、質問の展開例は、if 式を暗黙に解決していますが、展開の順序としては正しいといえます。

おそらくリストの順序を保持しながら重複を排除するための関数なのかなと想定されますが、
順序を保持しなくてもよいのであれば g = Set.toList . Set.fromList で済んでしまうので、
無用に複雑な感じにも見えてしまいますね。

foldr の結果型を関数にするのはよくあるテクニックですが、素直に展開しようとするとちょっと混乱しがちなので、
f :: Int -> (a -> b) -> (a -> b) のとき、
foldr f initial [1, 2, 3, 4] a == (f 1 . f 2 . f 3 . f 4 $ initial) a
のように、関数合成の連結をすべて処理した後に改めて引数を適用するものだと意識すると良いかもしれません。

Comments

[KN2018]

丁寧に回答をくださり、大変ありがとうございました。
f 1 (f 2 (const [])) を展開して考える、という考え方は大変参考になりました。foldr の結果型を関数にする、という考え方が苦手ですので、具体的な例を交えて教えてくださり、とても参考になります。
時間をかけて、丁寧な回答を書いてくださり、とても感謝しております。
今回は、通常の再帰を fold に書き直す手法を教えてくださった回答をベストアンサーにしましたが、丁寧に教えてくださったことに、深く感謝しております。大変ありがとうございました。

Answer 3

memberはBoolを返します

member :: Ord a => a -> Set a -> Bool

Setは一つの型引数メンバを持つ構造体です

data Set a

Set.memberからTrueが返る時、関数kがパターンマッチでSet aからaを取り出し、配列に格納します
Falseの場合はxと[x,ss]が:で結ばれ、[x,x,ss]が生成されます

main=print $ f 1 Set.toList (Set.singleton 2)

[1,1,2]

Comments

[KN2018]

お返事を下さって、大変ありがとうございます。ただ、ss というのは、見つかった値を格納していく Set であり、その ss に、次に読み込まれた値があるかどうかを確認するために存在しているのであって、[x, ss] のようにリスト化するものではないと思うのですが、どうでしょうか？
k は Set a -> [a] であるので、Set.toList のようなものを想像するのは分かるのですが、今の場合は、最終的には (const []) がその役割を担っているように思っています。（つまり、最終的には ss は廃棄するという感じでしょうか。）
あと、これは重複した値を排除するサンプルコードなので、[1,1,2] のように重複した値が結果として得られているのも、少し目的が異なるのかな？と思っています。
いかがでしょうか？？