Edited at

# subsequencesを紐解く

More than 1 year has passed since last update.

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

```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]`とするとこう言う展開が行われます

それを順番に簡約します

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

となるわけです。

ね、簡単でしょ？