subsequencesを紐解く

個人的に好きな関数は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]]

となるわけです。
ね、簡単でしょ？