subsequencesを紐解く


個人的に好きな関数はsubsequencesです
計算量が2^nなのがたまにきずって言うかそれがやりたいわけですがね
何をする関数かと言うと全組み合わせ生成です
コードを見た方が早いですね

```haskell
import Data.List (subsequences)

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

おーなんかすごい
全パターン列挙って地味に難しく思うのは私だけでしょうか？
そんなsubsequencesの中身を見て見ましょう
[ソース](https://hackage.haskell.org/package/base-4.9.1.0/docs/src/Data.OldList.html#subsequences)はbase-4.9.1.0のものです

```haskell
-- | 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
```

おや、意外とシンプルですね
たったこれだけのことで複雑な組み合わせを網羅できるのでしょうか？

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

紐解いて行きましょう

```haskell
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の定義

```haskell
subsequences :: [a] -> [[a]]
subsequences xs =  [] : nonEmptySubsequences xs
```

nonEmptySubsequencesって奴のラッパーみたいですね
そちらの定義も

```haskell
nonEmptySubsequences :: [a] -> [[a]]
nonEmptySubsequences []      =  []
nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
  where f ys r = ys : (x : ys) : r
```

リストを消費しながら再帰し、その結果をfoldする
なるほどワカラン

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

まずは再帰が終わるまで

```haskell
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を簡約

``` haskell
[] : [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]) : []))))
```

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

```haskell
[] : [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]]
```

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