パーサコンビネータなんかでよく使う、 some
と many
という関数があります。それぞれ引数を1回以上/0回以上実行して結果のリストを返す関数で、これの単純な定義は
some v = (:) <$> v <*> many v many v = some v <|> pure []
となります。 some
は v : (many v)
、 many
は some 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プログラムを自作言語に移植するときにハマりまくってます(マイナーな悩みだ…)
今回のsome
とmany
のケースも、自作言語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 } };