これは「Haskell (その2) Advent Calendar 2017」の1日目の記事です。遅くなってすいません。
読者として末尾再帰ぐらいは理解しているHaskellerを想定しています。
トップレベルとローカル関数
再帰を用いて関数を書いているとき、トップレベルで再帰するか、ローカル関数で再帰するか、ときどき迷う。この記事では、僕なりの判断基準を示したい。
Data.Listで定義されている再帰が必要な関数は、ほとんどがトップレベルで再帰している。代表例のmapの例を見てみよう。
map :: (a -> b) -> [a] -> [b] map _ [] = [] map f (x:xs) = f x : map f xs
mapをローカル関数を使う実装にしてみよう。この記事では、ローカル関数名としてgoを用いる。(loopを使う流儀もある。)
map' :: (a -> b) -> [a] -> [b] map' f xxs = go [] xxs where go acc [] = acc go acc (x:xs) = go (acc ++ [f x]) xs
Haskellerなら、(++)を使いリストの末尾に要素を追加していることに違和感を覚えるだろう。
以前、NTT Dataで利用されたHaskellドリルが話題となった。全体的にはよいのだけれど、上記のmap'のように、必ずwhereの中にローカル関数を定義させていたことには賛同できなかった。
Haskellを習得する際は、リストプログラミングから入ることが多く、初心者はどうしてもトップレベルで再帰しがちである。Haskellドリルには、これを矯正する効果が多少はあるかもしれない。
一方、ローカル関数で再帰する例として、以下のコードを取り上げる。
udpLookup :: ByteString -> Socket -> Int -> (DNSMessage -> Bool) -> Int -> (Socket -> IO DNSMessage) -> IO DNSMessage udpLookup query sock tm checkSeqno retry rcv = go 0 False where go cnt mismatch | cnt == retry = if mismatch then E.throwIO SequenceNumberMismatch else E.throwIO RetryLimitExceeded | otherwise = do mres <- timeout tm (send sock query >> rcv sock) case mres of Nothing -> go (cnt + 1) False Just res | checkSeqno res -> if trunCation $ flags $ header res then E.throwIO TCPFallback else return res | otherwise -> go (cnt + 1) True
このコードの意味は分からなくてもよいが、このコードをトップレベルでの再帰に書き直してみると、次のようなことが分かるだろう。
- 引数の数が多くなって、再帰の際に変化する引数がどれなのパッと見分からなくなる
- 蓄積変数など本来関数に閉じているべきパラメータを外に見せなければならなくなる
さてさて、トップレベルとローカル関数を使い分ける基準はあるのだろうか？
遅延評価とトップレベル
Data.Listの関数がトップレベルで定義されているのは、遅延評価と関係がある。私は遅延評価のファンではない。なぜなら、遅延評価が役立つ場面は、以下の3つしかないからである。
- リスト処理
- CASでの変数の更新
- 純粋性のテスト
Haskellのデフォルトの評価戦略が正格評価だったらよかったのにと思う。ただし、遅延評価がリスト処理に役立つのは間違いない。狭義の意味では、関数プログラミングはリストプログラミングであるから、関数プログラミングに遅延評価が必要であると勘違いしやすい。
Haskellで構造が遅延する一般的なデータ型はリストかData.Sequenceぐらいである。Data.Mapでさえ構造は遅延しない。私の定義では、関数プログラミングとは不変データプログラミングである。Haskellでは、構造が正格な不変データが多いので、デフォルトは正格評価であってほしい。
デフォルトを正格評価にするStrict/StrictDataプラグマは、GHC 8.0で実装された。GHC 8.4がリリースされれば、3つのメジャーバージョンを保守するポリシーでは GHC 7.x を捨てられるので、Strict/StrictDataプラグラマを活用できるようになるだろう。
前置きが長くなったが、遅延評価がリスト処理に役立つ例を見てみよう。以下は、map とhead を組み合わせた例である。
head $ map (+1) [1,2,3,4,5] -> head (2 : map (+1) [2,3,4,5]) -> 2
mapでは、トップレベルで再帰しているため、構造を再帰の外で作っている。そのため、遅延評価の下では無駄な計算が起こらない。一方、ローカル関数を使うmap'だと次のようになる。
head $ map' (+1) [1,2,3,4,5] -> head [2,3,4,5,6] -> 2
ローカル関数の利点
では、リストを生成しない関数はどうだろうか？ 上記のローカル関数を使う関数をトップレベルに書き換えたときの欠点が、ローカル関数を使う関数の利点であるから：
- 再帰の際に変化する引数がどれなのかパッと見て分かる
- 関数に閉じているべきパラメータを外に見せなくて済む
実は、もう一つ性能が良くなるという利点もある。Haskellの通常のデータはポインターで指されており、即値ではない。Intであろうと本当の値はポインターで指されている。トップレベルの再帰に、たとえば Int を使うと、関数を呼び出すごとにポインターをたどることになる。公開されている関数の引数は、即値に最適化できないからである。
ローカル関数を使うと、コンパイラは最適化に積極的になれる。
- ローカル関数の引数は、可能であれば即値が使われる
- ローカル関数から見たトップレベルの引数も可能であれば即値が使われる
こういう形式をWorker Wrapperと言って、プログラマーが少し手助けすることでコンパイラーに最適化を促す手法の一種である。たとえば、udpLookupなら、go が Worker、udpLookup が Wrapper である。
