M.Hiroi's Home Page

お気楽 Haskell プログラミング入門

初級編 : 遅延評価

Copyright (C) 2013-2021 Makoto Hiroi
All rights reserved.

はじめに

今回は Haskell の特徴である「遅延評価 (delayed evaluation または lazy evaluation)」について説明します。

●Haskell の遅延評価

一般的なプログラミング言語の場合、関数を呼び出す前に引数が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。Haskell は正格評価ではありません。関数の引数は、その値が必要になるまで評価は行われません。具体的には、引数を参照するときに評価が行われます。これを「遅延評価」といいます。遅延評価は関数の引数を評価するときだけではなく、変数の値を評価するときにも行われます。

他のプログラミング言語、たとえば Scheme では delay と force を使って遅延評価を行うことができます。Scheme の場合、評価結果は保存 (キャッシュ) されるので、再度引数 (変数) を参照すると、保存されている値が返されます。GHC の場合、昔のバージョンでは Scheme と同様に評価結果をキャッシュしていたのですが、今のバージョン (ver 8.8 4) ではキャッシュされません。

簡単な例を示しましょう。

Prelude> :{
Prelude| fibo 0 = 0
Prelude| fibo 1 = 1
Prelude| fibo n = fibo (n - 1) + fibo (n - 2)
Prelude| :}
Prelude> :set +s
Prelude> fibo 30
832040
(2.86 secs, 781,575,904 bytes)
Prelude> a = fibo 30
(0.00 secs, 30,944 bytes)
Prelude> a
832040
(2.84 secs, 781,575,856 bytes)
Prelude> a
832040
(2.86 secs, 781,575,856 bytes)

関数 fibo はフィボナッチ数を返します。fibo は二重再帰になっているので、実行時間はとても遅いです。

ghci で実行時間を計測するときは、コマンド :set で +s を指定してください。実行時間と使用したメモリを表示します。取り消す場合はコマンド :unset を使います。fibo 30 を評価すると 3 秒ほど時間がかかります。

次に a = fibo 30 を評価します。Haskell は遅延評価なので、変数 a を参照するまで fibo 30 は評価されません。すぐにプロンプトが表示されます。その次に変数 a を参照します。このとき、fibo 30 が評価されるので、a の値を表示するのに約 3 秒かかります。

再度 a を参照すると、a の値を表示するのに同じ時間がかかるので、ghci (ver 8.8.4) は評価結果をキャッシュしていないことがわかります。なお、これは GHC ver 8.4.4 での動作です。Haskell には複数の実装があるので、評価結果をキャッシュする処理系があるかもしれません。ご注意くださいませ。

●たらいまわし関数

それでは、遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。

リスト : たらいまわし関数

tarai :: Int -> Int -> Int -> Int
tarai x y z =
  if x <= y then y
  else tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)

tak :: Int -> Int -> Int -> Int
tak x y z =
  if x <= y then z
  else tak (tak (x - 1) y z) (tak (y - 1) z x) (tak (z - 1) x y)

関数 tarai や tak は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。

関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。

関数 tarai は遅延評価を行う処理系では高速に実行できることが知られています。正格な評価を行うプログラミング言語では時間がかかっても、Haskell ではあっというまに計算することができます。

tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。Haskell は x > y のときにだけ引数 z を評価するので、無駄な計算を省略することができます。なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。

実行時間を比較するため、x <= y のときにも引数 z を評価する関数 tarai' を作ります。次のリストを見てください。

リスト : たらいまわし関数 (2)

tarai' :: Int ->  Int -> Int -> Int
tarai' x y z =
  if x <= y then z `seq` y
  else tarai' (tarai' (x - 1) y z) (tarai' (y - 1) z x) (tarai' (z - 1) x y)

関数 seq x y は x を評価してから y を評価する関数です。返り値は y の評価結果です。x `seq` y `seq` z とすると、x, y, z の順番で評価し、最後に評価した z の結果を返します。

簡単な実行例を示します。

Prelude>:m Debug.Trace
Prelude Debug.Trace> trace "first" 10 `seq` trace "second" 20 `seq` trace "third" 30
first
second
third
30

Haskell のモジュール Debug.Trace にある関数 trace を使うと、seq の引数が順番に評価されていることがよくわかると思います。trace は第 2 引数の式を評価して返しますが、このとき第 1 引数の文字列を画面に表示します。:m はモジュールをロードする ghci のコマンドです。

tarai' は x <= y のときに z `seq` y で引数 z を評価して無駄な計算を行っているので、実行時間はとても遅くなるはずです。それでは実行してみましょう。

Prelude> :l tarai.hs
[1 of 1] Compiling Main             ( tarai.hs, interpreted )
Ok, one module loaded.
*Main> :set +s
*Main> tarai 12 6 0
12
(0.01 secs, 89,040 bytes)
*Main> tarai' 12 6 0
12
(8.19 secs, 2,445,409,256 bytes)

実行環境 : Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz

結果は一目瞭然で、tarai' は約 8.2 秒かかりますが、tarai は瞬時に計算を終えてしまいます。なお、これはインタプリタ ghci での結果であり、コンパイルするともっと高速になるでしょう。興味のある方はいろいろ試してみてください。

●末尾再帰

再帰定義のなかで、処理の最後で再帰呼び出しを行う場合を「末尾再帰 (tail recursion)」といいます。英語では tail recursion ですが、日本語では末尾再帰のほかに末端再帰とか終端再帰と呼ぶことがあります。末尾再帰は簡単な処理で繰り返しに変換できることが知られています。

ML や Lisp などの関数型言語や論理型言語の Prolog では、プログラムをコンパイルもしくは実行するときに、末尾再帰を繰り返しに変換する処理系があります。この機能を「末尾再帰最適化」[*1] といいます。なかには Scheme のように、言語仕様に末尾再帰最適化を行うことを明記しているプログラミング言語もあります。

たとえば、階乗を計算する関数 fact を思い出してください。

リスト : 階乗

fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n - 1)

上記リストの fact は最後に n と fact の返り値を乗算しているので、このプログラムは末尾再帰ではありません。これを末尾再帰に変換すると次のようになります。

リスト : 階乗 (末尾再帰)

fact :: Integer -> Integer
fact n = facti n 1 where
  facti 0 a = a
  facti n a = facti (n - 1) (a * n)

局所関数 facti を見てください。最後の再帰呼び出しで、facti の返り値をそのまま返しているので、このプログラムは末尾再帰になっています。これで階乗を計算できるなんて、ちょっと不思議に思われるかもしれません。そこが再帰呼び出しの面白いところです。このプログラムでは引数 a の使い方がポイントです。

たとえば facti 4 1 を実行すると、このプログラムでは 4 * 3 * 2 * 1 を計算しています。このとき、計算の途中経過を変数 a に記憶しているのです。正格評価を行う処理系で、末尾再帰最適化を適用する前の facti の呼び出しを図に示すと、次のようになります。

facti 4 1
  facti 3 4
    facti 2 12 
      facti 1 24
        facti 0 24
        => a の値 24 を返す
      => 24
    => 24
  => 24
=> 24

変数 a には計算途中の値が格納されていることがわかります。このような変数を「累算変数」とか「累算器」といいます。純粋な関数型言語では、while や loop など繰り返しの構文が用意されていない言語があります。Haskell もそうですが、論理型言語の Prolog にも単純な繰り返しはありません。これらのプログラミング言語では、繰り返しのかわりに末尾再帰を使ってプログラミングを行い、末尾再帰最適化によりプログラムを高速に実行することができます。

ただし、Haskell は遅延評価を行う処理系なので、上図のような動作をするとは限りません。これはあとで詳しく説明します。

-- note --------
[*1] 末尾再帰最適化は一般的な呼び方で、厳密には「末尾呼び出し最適化」とか「末尾最適化」といいます。詳しい説明は拙作のページ Scheme Programming 「関数型電卓プログラム fncalc の作成 (4) 末尾再帰とは?」をお読みください。

●フィボナッチ関数の高速化

今度は累算変数を使って、二重再帰を末尾再帰へ変換してみましょう。例題としてフィボナッチ関数を取り上げます。「再帰定義」で作成したフィボナッチ関数は二重再帰になっているので、とても時間がかかります。二重再帰を末尾再帰に変換すると、プログラムを高速に実行することができます。次のリストを見てください。

リスト : フィボナッチ関数 (末尾再帰)

fibo :: Integer -> Integer
fibo n = fiboi n 0 1 where
  fiboi 0 a _  = a
  fiboi n a b = fiboi (n - 1) b (a + b)

局所関数 fiboi の累算変数 a と b の使い方がポイントです。現在のフィボナッチ数を変数 a に、ひとつ先の値を変数 b に格納しておきます。あとは a と b を足し算して、新しいフィボナッチ数を計算すればいいわけです。fiboi の呼び出しを図に示すと、次のようになります。

fiboi 5 0 1
  fiboi 4 1 1
    fiboi 3 1 2
      fiboi 2 2 3
        fiboi 1 3 5
          fiboi 0 5 8
          => a の値 5 を返す
        => 5
      => 5
    => 5
  => 5
=> 5

図 : 関数 fiboi の呼び出し

二重再帰では、同じ値を何回も求めていたため効率がとても悪かったのですが、このプログラムでは無駄な計算を行っていないので、値を高速に求めることができます。

●末尾再帰と正格評価

Haskell は遅延評価を行う処理系なので、「末尾再帰」でプログラムしたからといって、正格評価を行う処理系と同じ動作になるとは限りません。たとえば、整数 1 から n までの合計値を求める関数 sum' を作ってみましょう。

リスト : 1 から n までの合計値を求める

sum' :: Integer -> Integer
sum' 0 = 0
sum' n = n + sum' (n - 1)

-- 末尾再帰
sumi :: Integer -> Integer
sumi n = iter n 0
  where
    iter 0 a = a
    iter n a = iter (n - 1) (a + n)

どちらも簡単な関数ですが、n が大きな値になると関数 sum' はスタックオーバーフローします。

*Main> sum' 10000000
*** Exception: stack overflow

これに対し、末尾再帰でプログラムした sumi はスタックオバーフローしませんが、そのかわりにメモリスワップが発生して、実行速度が極端に遅くなります。これは Haskell の遅延評価が原因です。

累積変数 a の値は、sumi の返り値が必要となるまで評価されません。たとえば、n = 5 とすると、再帰呼び出しで (((((0 + 5) + 4) + 3) + 2) + 1) という式が組み立てられ、sumi の返り値を評価するときに、この式が計算されて合計値が求められます。次のように、trace を使うと式 (a + n) が遅延評価されていることがよくわかります。

リスト : トレース表示

import Debug.Trace

sumi :: Integer -> Integer
sumi n = iter n 0
  where
    iter 0 a = trace "oops0" a
    iter n a = iter (n - 1) (trace "oops1" (a + n))
*Main> sumi 5
oops0
oops1
oops1
oops1
oops1
oops1
15

最初に iter の返り値 a が評価され、そのことにより組み立てられていた式が順番に評価されていくことがわかると思います。この場合、組み立てた式を保存するメモリが必要になるため、末尾再帰でプログラムしても n が大きくなるとメモリを大量に消費してしまうのです。

このような場合、正格評価を行う関数 seq を使うとうまくいきます。次のリストを見てください。

リスト : 正格評価バージョン

sumi' :: Integer -> Integer
sumi' n = iter n 0
  where
    iter 0 a = a
    iter n a = a `seq` iter (n - 1) (n + a)

seq で累積変数 a を強制的に評価します。これで再帰呼び出しが行われるたびに式を計算するので、n が大きな値でもメモリを大量消費せずに計算することができます。

実際に試してみましょう。

*Main> sum' 10000000
*** Exception: stack overflow
*Main> sumi' 10000000
50000005000000

ghci での実行なので、ちょっと時間がかかりますが、値を求めることができました。なお、GHC のモジュールには正格評価を行う関数も用意されています。たとえば、畳み込みを行う関数 foldl には、正格評価を行う関数 foldl' がモジュール Data.List に用意されています。

簡単な実行例を示します。

Prelude> :m Data.List
Prelude Data.List> :set +s
Prelude Data.List> foldl (+) 0 [1 .. 1000000]
500000500000
(0.55 secs, 161,304,744 bytes)
Prelude Data.List> foldl' (+) 0 [1 .. 1000000]
500000500000
(0.09 secs, 88,073,904 bytes)

実行環境 : Ubunts 18.04 (WSL), Intel Core i5-6200U 2.30GHz

foldl よりも foldl' のほうが速いみたいですね。興味のある方はいろいろ試してみてください。


初版 2013 年 1 月 27 日
改訂 2021 年 1 月 11 日