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

関数fix

(工事中 50%)

fix.hs

はじめに

リストを扱うさまざまな関数の定義を見ていくことで関数による抽象の層構造または網目構造を学んだ。「たたみこみ」を抽象化したり、その抽象を利用して、転写やろ過を定義したりした。これらはほとんどが再帰関数である。さらにその抽象化の層を根本までたどって「再帰」という考えかた自体を関数で表現してみよう。

関数fix

関数fixはData.Functionモジュールから公開されている。

% ghci
Prelude> :m Data.Function
Prelude Data.Function> :t fix
fix :: (a -> a) -> a
Prelude Data.Function> take 10 $ fix (1 :)
[1,1,1,1,1,1,1,1,1,1]

定義を見てみよう。

myFix :: (a -> a) -> a
myFix f = f (myFix f)

これを展開すると以下のようになる。

f (f (f (f (f (f ...

fix (1 :)であれば以下のようになるだろう。

1 : 1 : 1 : 1 : ...

再帰関数の定義

この関数fixをつかえばすべての再帰関数が明示的な再帰なしに書ける。階乗を求める関数を定義してみよう。

fact' :: (Integer -> Integer) -> Integer -> Integer
fact' _ n | n < 1 = 1
fact' f n = n * f (n - 1)

fact :: Integer -> Integer
fact = fix fact'

これでうまくいく。

Prelude> :l fix.hs
*Main> fact 10
3628800

にわかには信じがたい。いったい何が起きているのだろうか。fact'の定義を見ると関数と値をとって値が1未満ならば1を返し、そうでないなら関数にn - 1を与えて得た値にnをかけている。

*Main> fact' (+ 10) 3
36

2に(+ 10)を適用した結果に3をかけている。こう見るとfact'はごくふつうの高階関数だ。fact 3を展開してみよう。

fact 3
-> fix fact' 3
-> fact' (fix fact') 3
-> 3 * fix fact' 2
-> 3 * fact' (fix fact') 2
-> 3 * 2 * fix fact' 1
-> 3 * 2 * fact' (fix fact') 0
-> 3 * 2 * 1
-> 6

嘘みたいだが確かにそうなる。

fun f = [fを利用した定義]の形を考えてみよう。このfunにfixを適用すると以下のようになるだろう。

fix fun = fun (fix fun)
-> fix fun = [fix funを利用した定義]

fact'をこれを考慮した疑似コードにすると以下のようになる。

fix fact' n | n < 1 = 1
fix fact' n = n * fix fact' (n - 1)

fix fact'のかたまりをひとつの変数として考えるとこれが階乗の定義になっていることがわかる。

まとめ

「再帰」という概念そのものを関数として表現することができる。

「関数repeat, replicate, cycle」へもどる 「相互再帰と関数fix」へ

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