Edited at

subsequencesを紐解く

More than 1 year has passed since last update.

個人的に好きな関数はsubsequencesです

計算量が2^nなのがたまにきずって言うかそれがやりたいわけですがね

何をする関数かと言うと全組み合わせ生成です

コードを見た方が早いですね

import Data.List (subsequences)

main = print $ subsequences [1..3] -- [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

おーなんかすごい

全パターン列挙って地味に難しく思うのは私だけでしょうか?

そんなsubsequencesの中身を見て見ましょう

ソースはbase-4.9.1.0のものです

-- | The 'subsequences' function returns the list of all subsequences of the argument.

--
-- > subsequences "abc" == ["","a","b","ab","c","ac","bc","abc"]
subsequences :: [a] -> [[a]]
subsequences xs = [] : nonEmptySubsequences xs

-- | The 'nonEmptySubsequences' function returns the list of all subsequences of the argument,
-- except for the empty list.
--
-- > nonEmptySubsequences "abc" == ["a","b","ab","c","ac","bc","abc"]
nonEmptySubsequences :: [a] -> [[a]]
nonEmptySubsequences [] = []
nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
where f ys r = ys : (x : ys) : r

おや、意外とシンプルですね

たったこれだけのことで複雑な組み合わせを網羅できるのでしょうか?

できるんだからしょうがない(´・_・`)

紐解いて行きましょう

subsequences [1..3]

[] : nonEmptySubsequences [1..3]
[] : [1] : (foldr f [] $ nonEmptySubsequences [2..3])
[] : [1] : (foldr f [] $ ([2] : foldr f [] $ nonEmptySubsequences [3]))
[] : [1] : (foldr f [] $ ([2] : foldr f [] $ ([3] : foldr f [] $ nonEmptySubsequences [])))
[] : [1] : (foldr f [] $ ([2] : foldr f [] $ ([3] : foldr f [] [])))
[] : [1] : (foldr f [] $ ([2] : foldr f [] $ ([3] : [])))
[] : [1] : (foldr f [] $ ([2] : foldr f [] [[3]]))
[] : [1] : (foldr f [] $ ([2] : ([3] : (2 : [3]) : [])))
[] : [1] : (foldr f [] $ ([2] : [[3], [2,3]]))
[] : [1] : (foldr f [] $ [[2], [3], [2,3]])
[] : [1] : ([2] : (1 : [2]) : ([3] : (1 : [3]) : ([2,3] : (1 : [2,3]) : []))))
[] : [1] : ([2] : (1 : [2]) : ([3] : (1 : [3]) : ([2,3] : ([1,2,3]) : [])))
[] : [1] : ([2] : (1 : [2]) : ([3] : (1 : [3]) : [[2,3], [1,2,3]]))
[] : [1] : ([2] : (1 : [2]) : ([3] : ([1, 3]) : [[2,3], [1,2,3]]))
[] : [1] : ([2] : (1 : [2]) : ([[3], [1, 3], [2,3], [1,2,3]]))
[] : [1] : ([2] : ([1, 2]) : [[3], [1, 3], [2,3], [1,2,3]])
[] : [1] : [[2], [1, 2], [3], [1, 3], [2,3], [1,2,3]]
[] : [[1], [2], [1, 2], [3], [1, 3], [2,3], [1,2,3]]
[[], [1], [2], [1, 2], [3], [1, 3], [2,3], [1,2,3]]

はい終了です、ワカリヤスイネ

それでは失礼なので順を追って行きます

まずはsubsequencesの定義

subsequences :: [a] -> [[a]]

subsequences xs = [] : nonEmptySubsequences xs

nonEmptySubsequencesって奴のラッパーみたいですね

そちらの定義も

nonEmptySubsequences :: [a] -> [[a]]

nonEmptySubsequences [] = []
nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
where f ys r = ys : (x : ys) : r

リストを消費しながら再帰し、その結果をfoldする

なるほどワカラン

こう言う時は順番に関数適応グラフを作って見ていくとわかり易くなります

まずは再帰が終わるまで

subsequences [1..3]

[] : nonEmptySubsequences [1..3]
[] : [1] : (foldr f [] $ nonEmptySubsequences [2..3])
[] : [1] : (foldr f [] $ ([2] : foldr f [] $ nonEmptySubsequences [3]))
[] : [1] : (foldr f [] $ ([2] : foldr f [] $ ([3] : foldr f [] $ nonEmptySubsequences [])))
[] : [1] : (foldr f [] $ ([2] : foldr f [] $ ([3] : foldr f [] [])))

subsequences [1..3]とするとこう言う展開が行われます

それを順番に簡約します

一通りfoldrを簡約

[] : [1] : (foldr f [] $ ([2] : foldr f [] $ ([3] : [])))

[] : [1] : (foldr f [] $ ([2] : foldr f [] [[3]]))
[] : [1] : (foldr f [] $ ([2] : ([3] : (2 : [3]) : [])))
[] : [1] : (foldr f [] $ ([2] : [[3], [2,3]]))
[] : [1] : (foldr f [] $ [[2], [3], [2,3]])
[] : [1] : ([2] : (1 : [2]) : ([3] : (1 : [3]) : ([2,3] : (1 : [2,3]) : []))))

あとはリストのコンストラクターを潰していくだけ

[] : [1] : ([2] : (1 : [2]) : ([3] : (1 : [3]) : ([2,3] : (1 : [2,3]) : []))))

[] : [1] : ([2] : (1 : [2]) : ([3] : (1 : [3]) : ([2,3] : ([1,2,3]) : [])))
[] : [1] : ([2] : (1 : [2]) : ([3] : (1 : [3]) : [[2,3], [1,2,3]]))
[] : [1] : ([2] : (1 : [2]) : ([3] : ([1, 3]) : [[2,3], [1,2,3]]))
[] : [1] : ([2] : (1 : [2]) : ([[3], [1, 3], [2,3], [1,2,3]]))
[] : [1] : ([2] : ([1, 2]) : [[3], [1, 3], [2,3], [1,2,3]])
[] : [1] : [[2], [1, 2], [3], [1, 3], [2,3], [1,2,3]]
[] : [[1], [2], [1, 2], [3], [1, 3], [2,3], [1,2,3]]
[[], [1], [2], [1, 2], [3], [1, 3], [2,3], [1,2,3]]
subsequences [1..3] == [[], [1], [2], [1, 2], [3], [1, 3], [2,3], [1,2,3]]

となるわけです。

ね、簡単でしょ?