top page > computer > haskell > web_lecture > for_programmer > take_foldr.html
更新日:
文責: 重城良国

関数foldrで関数takeを定義

はじめに

関数take, drop, splitAtの関数foldrでの表現はすこし難しいかもしれない。ステップ1として具体的な値をいれて展開してみる。その次により抽象的な意味について考えてみる。リストをたたみこんだ結果が関数になるという考えかただ。リストの値によって関数が次々と変化していく。たとえばxを追加することによって「[x1, x2, ...]からn個とる関数」が「[x, x1, x2, ...]からn個とる関数」に変換されるという考えかただ。

ウォーミングアップ

以下の問題を考えてみよう。

[1, 2, 3, 4, 5, ...]からn個とる関数fun1があったとする。それでは[10, 1, 2, 3, 4, 5, ...]からn個とる関数fun2はfun1を使ってどのように表せるだろうか。まずは対話環境でlet fun1 n = [1 .. n]として関数fun1を作っておこう。

[x1, x2, ...]からn個とる関数fがあったとする。また関数gは[x, x1, x2, ...]からn個とる。xを引数にとり関数fを関数gに変換する関数convを書け。conv 10 fun1が関数fun2になれば良い。

takeF :: Int -> [a] -> [a]

定義

以下の定義を見てみよう。ftakeはtakeの第1引数と第2引数とを入れかえたものだ。

step x f n | n > 0 = x : f (n - 1)
step _ _ _ = []

ftake :: [a] -> Int -> [a]
ftake (x : xs) n = step x (ftake xs) n
ftake _ _ = []

順を追って見ていけばわかるはずだ。step x (ftake xs) nはnが1以上ではx : ftake xs (n - 1)に展開される。nが0以下ならば[]だ。つまりうえの定義は以下と同じことだ。よく見くらべてみよう。

ftake (x : xs) n | n > 0 = x : ftake xs (n - 1)
ftake _ _ = []

ひとつめの関数ftakeの定義から不要な仮引数nを消す。

ftake (x : xs) = step x (ftake xs)
ftake _ = const []

この形はfoldrの枠組みになっている。

ftake = foldr s (const [])
where
s x f n | n > 0 = x : f (n - 1)
s _ _ _ = []

第1引数と第2引数を入れかえる必要がある。

takeF = flip $ foldr s (const [])
where
s x f n | n > 0 = x : f (n - 1)
s _ _ _ = []

何が起きたのか

関数foldrを使って関数takeが定義できた。ここで使われている関数stepについて考えてみよう。関数(step x)は「リスト[x1, x2, x3, ...]からn個とる関数」を「リスト[x, x1, x2, x3, ...]からn個とる関数」に変換している。全体としては関数(const [])を初期値としてリストを関数へとたたみこんでいる。

下書き1

リスト[5, 3, 4, 1, 8]からn個とりだす関数fがあったとする。

f 2 => [5, 3]
f 4 => [5, 3, 4, 1]

これを使ってリスト[10, 5, 3, 4, 1, 8]からn個とりだす関数gを作ろう。

g n | n > 0 = 10 : f (n - 1)
g _ = []

たとえば[10, 5, 3, 4, 1, 8]から3個とりだすのは、[5, 3, 4, 1, 8]から2個とりだした結果の先頭に10を追加すれば良い。より一般化してリスト[x1, x2, x3, ...]からn個とりだす関数fを使ってリスト[x, x1, x2, x3, ...]からn個とりだす関数gを作る。

g n | n > 0 = x : f (n - 1)
g _ = []

このような関係になるように、値xと関数fから関数gを作成する関数stepを作成する。

step x f n | n > 0 = x : f (n - 1)
step _ _ _ = []

gの部分をstep x fに置き換えた。つまり

g == step x f

step xはリスト[x1, x2, x3, ...]からn個とりだす関数をリスト[x, x1, x2, x3, ...]からn個とりだす関数に変換する関数となる。これを使って関数ftakeを作成する。関数ftakeはtakeの第1引数と第2引数とを入れかえたものとする。

下書き2

まずは第1引数と第2引数をとりかえたftakeを考えてみる。

ftake :: [a] -> Int -> [a]
ftake (x : xs) n | n > 0 = x : ftake xs (n - 1)
ftake _ _ = []

これを以下のように書き換える。

ftake (x : xs) =
\n -> if n > 0 then x : ftake xs (n - 1) else []
ftake _ = const []

関数foldrの枠組みに合わせるにはftake (x : xs)をxとftake xsで表現すれば良い。うえの式のxとftake xsを引1引数と第2引数に置き換える。

step x f = \n -> if n > 0 then x : f (n - 1) else []

関数stepの第2引数は整数値をとってリストを返す関数だ。関数fを関数\n -> ...に変換している。終了条件を消して見てみよう。n > 0のときに行われる処理のみを示すということだ。

step x f = \n -> x : f (n - 1)

これはこう読める。新たな要素xが追加されると関数fは「整数nをとりxをf (n - 1)の先頭に追加した値を返す関数」に変換される。関数fが整数nをとりn個の値を返す関数だとすると、step x fは整数nをとりxと(n - 1)個の値を返す関数となる。

ftake = foldr s (const [])
where
s x f n | n > 0 = x : f (n - 1)
s x f n = []

「関数foldrによる定義」へもどる 「関数foldrで関数dropを定義」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics