リストは非決定性のモナド - あどけない話

Haskell のリストはモナドであり、それは非決定性の文脈を表すと言われます。しかし、そのことを扱った例題は少なくて、しかもイマイチでした。そこで、Scheme で書かれたよい例題を Haskell で書き直してみました。 「On Lisp」の「非決定性」の章では、謎めいた関数 choose と fail が出てきます。こんな難しい話をしなくても、Haskell では単に全探索することで非決定性を実現できます。なぜなら、Haskell の評価戦略は遅延評価なので、答えの先頭しか要求しなければ、残りの答えは探さないからです。 というわけで、Haskell で非決定性の問題を解くことは、リストを使って普通にプログラミングすることとなんら変わりません。 三平方の定理 「もうひとつの Scheme 入門」に載っている三平方の定理に関する問題を解いてみましょう。 x = [1,2,3,4,5],

[l-_-ll]

"Haskell では単に全探索することで非決定性を実現できます。なぜなら、Haskell の評価戦略は遅延評価なので、答えの先頭しか要求しなければ、残りの答えは探さないからです。"