星にゃーんのブログ

ほとんど無害。

Haskellのsomeを正格評価したら無限ループする話

 パーサコンビネータなんかでよく使う、 somemany という関数があります。それぞれ引数を1回以上/0回以上実行して結果のリストを返す関数で、これの単純な定義は

some v = (:) <$> v <*> many v
many v = some v <|> pure []

となります。 somev : (many v)manysome v または [] を返すイメージです。 パーサコンビネータでは、例えば英数字1文字以上の文字列をパースしたいとき some alphaNum と書いたりします。

 面白いのは、一見とても自明に思えるこの定義は、遅延評価がないと無限ループしてしまう点です。 本当は v が失敗したら some v 自体が失敗してほしいところが、v が失敗するか否かに関わらず many v が実行されてしまいます。正格評価の気持ちで考えるとあたりまえですが、Haskellに慣れてるとびっくりするかもしれません。僕はびっくりしました。

 Haskell風の正格評価な言語であるPureScriptでは、 some の定義がちょっと違います。

some v = (:) <$> v <*> defer (\_ -> many v)

many v の実行が v が成功するか失敗するかわかるまで遅延されています。こうすれば正格評価な言語でも無限ループすることはありません。

 他にもHaskellには「遅延評価だからこの書き方できるけど、正格評価だと動かないな〜」となるケースが多く、Haskellプログラムを自作言語に移植するときにハマりまくってます(マイナーな悩みだ…) 今回のsomemanyのケースも、自作言語Malgo(https://github.com/malgo-lang/malgo)に移植した際に気づきました。

many : Parser a -> Parser (List a);
many = { v -> some v <|> pure Nil };

some : Parser a -> Parser (List a);
-- many v が必ず実行されてしまい、無限ループになる
some = { v -> Cons <$> v <*> many v };

-- PureScriptの例と同様に、many vの実行を明示的に遅延させる
some = { v -> Cons <$> v <*> defer { many v } };