y-combinator in StandardML

Question

Я знаю, что могу написать y-combinator в SML следующим образом: Сначала объявите новый тип данных, чтобы обойти несоответствие типа из-за округлости.

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

Теперь вы можете легко определить, у-комбинатор:

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)) 

---

Мой вопрос: Существуют ли другие способы реализации y-комбинатора в SML?

Answer 1

Вы можете, конечно, использовать встроенную рекурсию, например.

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

или

fun Y f x = f (Y f) x 

Вы также можете использовать исключения таким же образом, как тип данных, но только мономорфно:

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)) 

Но я считаю, наряду со ссылками, что о охватывает его.

Edit: На самом деле, вы можете сделать это полиморфный с помощью исключения местного:

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