9.md

再帰ドリル(9)：リストを生成する再帰

今回は、入力としてリストを取り、出力としてリストを返す関数を再帰で実現することを考える。これらの関数は、出力のリストによって大まかに二分できる。

• 入力のリストとは反対向きのリストを出力する
• 入力のリストと同じ向きのリストを出力する

逆向きのリスト

ここでは、逆向きのリストを生成する関数 my_reverse について考える。

> my_reverse [1,2,3]
[3,2,1]

リストを扱う関数は、再帰ドリル(8)で説明した基本操作から実装できる。このドリルの趣旨としては、すべてを作っていくべきであるが、ここでは説明を簡単にするため二つのリストを連結する演算子(++)は、すでに実装されているとしよう。

入力のリストとは反対向きのリストを出力する関数 my_reverse は、(++) を使うと、以下のように素朴な再帰で実装できる。

my_reverse :: [a] -> [a]
my_reverse []     = []
my_reverse (x:xs) = my_reverse xs ++ [x]

この関数の動作を考えてみよう。

     my_reverse (1:2:3:[])
→   my_reverse (2:3:[]) ++ [1]
→  (my_reverse (3:[])   ++ [2]) ++ [1]
→ ((my_reverse []       ++ [3]) ++ [2]) ++ [1]
→ (([] ++ [3]) ++ [2]) ++ [1]
→ ([3] ++ [2]) ++ [1]
→ [3,2] ++ [1]
→ [3,2,1]

正確な議論は割愛するが、効率が悪そうであることは理解できるだろう。

逆向きのリストを生成する関数は、蓄積変数を使う末尾再帰と相性がよいことが知られている。my_reverse を末尾再帰の形に直した my_reverse_iter は、以下の通り。

my_reverse_iter :: [a] -> [a]
my_reverse_iter as = iter as []
  where
    iter :: [a] -> [a] -> [a]
    iter []     ys = ys
    iter (x:xs) ys = iter xs (x:ys)

ローカル関数 iter の動作は次のようになる。

   iter (1:2:3:[])        []
-> iter   (2:3:[])     (1:[])
-> iter     (3:[])   (2:1:[])
-> iter        []  (3:2:1:[])

入力のリストを先頭から順に取り出して、空リストに追加していけば、自ずと逆向きになると言う訳だ。

学んだこと：

• 入力のリストとは反対向きのリストを出力する関数は、蓄積変数を使う末尾再帰と相性がよい

同じ向きのリスト

同じ向きのリストを生成する関数の例として my_map を考える。my_map は、関数とリストを取り、リストのそれぞれの要素に関数を適用した新しいリストを出力する。

> my_map (+1) [1,2,3]
[2,3,4]

この関数はどう実装すると効率がよいだろうか？ 仮に末尾再帰で実装してみる。ここでも話を簡単にするために、reverse は定義済みとする。

my_map_iter :: (a -> b) -> [a] -> [b]
my_map_iter g as = reverse (iter g as [])
  where
    iter _ []     acc = acc
    iter f (x:xs) acc = iter f xs (f x : acc)

この関数は、関数をそれぞれの要素に適用した逆向きのリストを一旦作り、さらに逆向きにすることで、入力と同じ向きに直す。

[1,2,3]
↓ iter
[4,3,2]
↓ reverse
[2,3,1]

リストを破壊的に逆向きにできるプログラミング言語では、この手法が取られることも多い。一方で、遅延評価、あるいは遅延リストを持つプログラミング言語では、素朴な再帰を使う。

my_map :: (a -> b) -> [a] -> [b]
my_map _ []     = []
my_map f (x:xs) = f x : my_map f xs

この関数の動作は以下の通り(本当は足し算も遅延するが、分かりにくいので、そこは評価されることにする)。

   my_map (+1) (1:2:3:[])
→ 2 : my_map (+1) (2:3:[])
→ 2 : 3 : my_map (+1) (3:[])
→ 2 : 3 : 4 : my_map (+1) ([])
→ 2 : 3 : 4 : []

ここで、my_map (+1) (1:2:3:[]) の先頭の要素を取り出すことを考えよう。あまり使わないが、今回は head を使うことにする。

   head (my_map (+1) (1:2:3:[]))
→ head (2 : my_map (+1) (2:3:[]))
→ 2

my_map (+1) (2:3:[]) は、不要な計算であり、遅延評価の下では計算されない。このように、プログラミング言語が遅延評価を採用しているか、遅延リストを提供しているなら、素朴な再帰の方が効率がよいのである。(専門的には、このような再帰を余再帰と言う。)

学んだこと：

• プログラミング言語が遅延評価を採用しているか、遅延リストを提供しているなら、同じ向きのリストを生成する関数は、素朴な再帰で実装するのと効率がよい

これ以降、プログラミング言語が遅延評価を採用しているか、遅延リストを提供していると仮定する。Haskell のデフォルトの評価戦略は遅延評価である。

演習

同じ向きのリストを生成する関数を実装する。foo xs はできていると信じて、foo (x:xs) を完成させること。

フィルタ

判定関数が True を返す要素だけを残す my_filter を実装したい。

> my_filter even [1,2,3,4,5]
[2,4]

以下を編集して my_filter を完成させよ。

my_filter :: (a -> Bool) -> [a] -> [a]
my_filter _ []     = []
my_filter p (x:xs) = undefined

連結

二つのリストを連結する関数 my_append を定義したい。

> my_append [1,2] [3,4,5]
[1,2,3,4,5]

以下を編集して my_append を完成させよ。

my_append :: [a] -> [a] -> [a]
my_append []     ys = ys
my_append (x:xs) ys = undefined

入力としてリストのリストを取り、内側のリストすべてを連結する関数 my_concat を定義したい。

> my_concat [[1,2],[3,4,5],[6]]
[1,2,3,4,5,6]

以下を編集して my_concat を完成させよ。ヒント：my_append を使う。

my_concat :: [[a]] -> [a]
my_concat []       = []
my_concat (xs:xss) = undefined

第一引数で指定された要素をリストの要素の間に挟み込む関数 my_intersperse を実装したい。

> my_intersperse 0 []
[]
> my_intersperse 0 [1]
[1]
> my_intersperse 0 [1,2]
[1,0,2]
> my_intersperse 0 [1,2,3]
[1,0,2,0,3]

以下を編集して my_intersperse を完成させよ。ヒント：基底部に注意。

my_intersperse :: a -> [a] -> [a]
my_intersperse = undefined

分割

判定関数が True を返す要素の前でリストを二分割する my_break を定義したい。

> my_break (==3) []
([],[])
> my_break (==3) [1]
([1],[])
> my_break (==3) [1,2,3,4,5]
([1,2],[3,4,5])

以下を編集して my_break を完成させよ。

my_break :: (a -> Bool) -> [a] -> ([a], [a])
my_break _ [] = ([],[])
my_break p (x:xs) = undefined

隣り合う同じ要素をグループ化する関数 my_group を実装したい。

> my_group []
[]
> my_group [1]
[[1]]
> my_group [1,1,0,1,2,2,2,0,0]
[[1,1],[0],[1],[2,2,2],[0,0]]

以下を編集して my_group を完成させよ。ヒント：my_break を使う。

my_group :: Eq a => [a] -> [[a]]
my_group []     = []
my_group (x:xs) = undefined

[目次] [演習9]