純粋関数型言語で定義できない純粋な関数 - sumiiのブログ並列論理和の続きで真のエキスパート氏から教えていただいた話（の劣化コピー）。並列論理和は、逐次言語では定義できないけど「計算可能」な（並列言語では定義でき、領域理論でも連続になる）関数でしたが、その親戚というか兄弟です。 MLで（実はHaskellでも良いのですが）、unit→unit型の純粋な（＝副作用のない）関数は、 let f1 () = () let rec f2 () = f2 () の2つがあります。ただし、たとえ内部の実装が異なっても、外部から観察できる振る舞いが同じ関数は同じとみなします。たとえば let f1' () = try (raise E) with E -> () なるf1'はf1と同じ（かつ純粋）とみなします。 以下、「関数」としてデフォルトでは「振る舞いが純粋な関数」だけを考えることにします。すると、上と同様に、(unit→unit)→unit型の関数は l
