Hatena::ブログ(Diary)

あどけない話

2017-12-12

goな関数

これは「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 である。

まとめ

結論はいたって簡単だ。

notogawanotogawa 2017/12/12 14:35 ローカル関数の利点についてはともかく,途中の展開はおかしいと思います.

> リストを生成する関数はトップレベルで再帰するべきである。

生成したリストを後々構造再帰で消費することを考慮するならば,
生成がリスト構造に対して再帰的になっているかかが主な問題点であるので,
記事中でのmap.goの定義が生成的ではないのが無駄な計算が起こる原因です.
この点に関してトップレベルかどうかは何も関係が無いのではないでしょうか.

kazu-yamamotokazu-yamamoto 2017/12/12 15:25 「map.goの定義が生成的」→「map'.goの定義が再帰的」でしょうか?

kazu-yamamotokazu-yamamoto 2017/12/12 15:31 確かに、(トップレベルとローカル関数)と(再帰的と蓄積的?)は直行していると思います。しかし、Wrapperの中に(蓄積的でなく)再帰的なWorkerを使ってる実装って、何か有名なものはありますか?

notogawanotogawa 2017/12/12 16:10 「map'.goの定義が再帰的」ですね.

> Wrapperの中に(蓄積的でなく)再帰的なWorkerを使ってる実装

GHC.Base.foldr とかでしょうか?ただ,
今の話としてはそういう実装を例示する意味は特段無いかと思います.

通常,リストを分解しながら結果を蓄積するような補助関数を導入したら,
遅延評価のもとでも最後までリストを分解して結果を蓄積しないと結果を取り出せないのは明らかです.
これは,たとえmap'.goがreverseしてしまうのを覚悟の上で(++)でなく(:)で蓄積しても同じです.
そして,そう書くかどうかはトップレベルでもローカルでも関係ありません.

蓄積変数を補助関数に導入するなら同時にその蓄積変数を積極評価してサンクを潰しつつ,
末尾再帰の形に持っていくことが主眼になりがちので,発生する計算が無駄な計算かどうかは,
最終的にそこを積極評価することが妥当なのかという設計に集約されるのではないかと.

kazu-yamamotokazu-yamamoto 2017/12/12 21:25 ここで言いたいのは、蓄積変数を使いたくなったら、ローカル関数を作って、蓄積変数は隠蔽するのがいいみないな話なのです。

notogawanotogawa 2017/12/12 22:16 はい.そして,そこからだと

> リストを生成する関数はトップレベルで再帰せよ

の適切な根拠は出てこない筈というのが最初のコメントです.

kazu-yamamotokazu-yamamoto 2017/12/13 10:06 あー。
リストを生成する関数は、トップレベルで再帰してもいい(ローカル関数でも再帰していい)、ぐらいならOKですか?

notogawanotogawa 2017/12/13 11:52 うーん,この件について「リストを生成する関数」特化して何か言うのって難しくないですかね?

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/kazu-yamamoto/20171212/1513050147