StandardMLのy-コンビネータ

Question

私はこのようにSMLでy-コンビネータを書くことができます： 真円度のために型の不一致を回避するために、まず新しいデータ型を宣言します。

val Y = fn f => (fn x => fn a => f (unroll x x) a) 
      (Roll (fn x => fn a => f (unroll x x) a))) 

は、その後、あなたが行われて、あなたはこのようにそれを使用することができます：

val f = Y (fn f => fn n => if n = 0 then 1 else n * f (n-1)) 

---

私の質問がある

datatype 'a mu = Roll of ('a mu -> 'a) 
val unroll = fn Roll x => x 

今すぐ簡単に、Yコンビネータを定義することができます。 SMLにyコンビネータを実装する他の方法はありますか？

Answer 1

もちろん、組み込みの再帰自体を使用することもできます。

fun Y f = f (fn x => Y f x) 

または

fun Y f x = f (Y f) x 

また、データ型と同じ方法で例外を使用しますが、唯一のmonomorphicallyことができます。

exception Roll of exn -> int -> int 
val unroll = fn Roll x => x 
fun Y f = (fn x => fn a => f (unroll x x) a) (Roll (fn x => fn a => f (unroll x x) a)) 

をしかし、私は約それをカバーすることを参照して一緒に考えています。

編集：そのために必要な自己アプリケーションは再帰タイプを必要とするため、あなたがすることはできません

fun Y f : 'a -> 'b = 
    let 
    exception Roll of exn -> 'a -> 'b 
    val unroll = fn Roll x => x 
    in 
    (fn x => fn a => f (unroll x x) a) (Roll (fn x => fn a => f (unroll x x) a)) 
    end