y-комбинатор В стандарте мл

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

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

Теперь вы можете легко определить 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))

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

1 6
functional-programming y-combinator sml

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
5