不动点组合子

[CharLemAznable]

不动点组合子(Fixed-point combinator, 或不动点算子, 使用FIX表示)是计算其他函数的一个不动点的高阶函数.

不动点算子具有以下特性, 对于任何函数f都有:

FIX f = f (FIX f)

不动点组合子中最有名的(也可能是最简单的)是Y组合子:

Y = λf. (λx. f (x x)) (λx. f (x x))

另一个常见不动点组合子是图灵不动点组合子, 即Θ组合子:

Θ = (λx. λy. (y (x x y))) (λx.λy.(y (x x y)))

实现不动点组合子时用到的类型:

|　名称　　　　　| Type                                           |
|　　　　　　　　|                                                |
|　递归参数　　　| T                                              |
|　递归返回　　　| R                                              |
|　递归函数　　　| Func<T, R>                                     |
|　单步函数　　　| Func<Func<T, R>, Func<T, R>>                   |
|　不动点组合子　| Func<Func<Func<T, R>, Func<T, R>>, Func<T, R>> |

不动点组合子:

一个以单步函数为参数的返回递归函数的高阶函数

参考使用 Lambda 表达式编写递归 系列文章

[CharLemAznable]

Java实现Y组合子

import lombok.val;
import java.util.function.Function;

public class YCombinator {

    public static <T, R> Function<T, R> of(Function<Function<T, R>, Function<T, R>> f) {
        Function<Function, Function<T, R>> r = p -> {
            @SuppressWarnings("unchecked")
            val w = (Function<Function, Function<T, R>>) p;
            return f.apply(param -> w.apply(w).apply(param));
        };
        return r.apply(r);
    }
}

[CharLemAznable]

Java实现Y组合子 简化版

import java.util.function.Function;

public class YCombinator {

    public static <T, R> Function<T, R> of(Function<Function<T, R>, Function<T, R>> f) {
        return n -> f.apply(of(f)).apply(n);
    }
}

[CharLemAznable]

Go实现Y组合子

type RecFunc func(n interface{}) interface{}

func YComb(f func(RecFunc) RecFunc) RecFunc {
    var r = func(p interface{}) RecFunc {
        var w = p.(func(v interface{}) RecFunc)
        return f(func(param interface{}) interface{} {
            return w(w)(param)
        })
    }
    return r(r)
}

[CharLemAznable]

Go实现Y组合子 简化版

type RecFunc func(interface{}) interface{}

func YComb(f func(RecFunc) RecFunc) RecFunc {
    return func(n interface{}) interface{} {
        return f(YComb(f))(n)
    }
}

[CharLemAznable]

Objective-C实现Y组合子

#define YCombinator(ARG_TYPE, RET_TYPE, REC_NAME, IMP_BLOCK)                    \
^RET_TYPE (^(RET_TYPE (^(^f)(RET_TYPE (^)(ARG_TYPE)))(ARG_TYPE)))(ARG_TYPE) {   \
    RET_TYPE (^(^r)(id))(ARG_TYPE) = ^(id p) {                                  \
        RET_TYPE (^(^w)(id))(ARG_TYPE) = p;                                     \
        return f(^RET_TYPE (ARG_TYPE param) {                                   \
            return w(w)(param);                                                 \
        });                                                                     \
    };                                                                          \
    return r(r);                                                                \
}(^RET_TYPE (^(RET_TYPE (^REC_NAME)(ARG_TYPE)))(ARG_TYPE) {                     \
    return IMP_BLOCK;                                                           \
})

[CharLemAznable]

Objective-C实现Y组合子 简化版

#define YCombinator(NAME, ARG_TYPE, RET_TYPE)           \
typedef RET_TYPE(^NAME##RecFunc)(ARG_TYPE);             \
NAME##RecFunc NAME(NAME##RecFunc(^f)(NAME##RecFunc)) {  \
    return ^RET_TYPE(ARG_TYPE n) {                      \
        return f(NAME(f))(n);                           \
    };                                                  \
}

[CharLemAznable]

Kotlin实现Y组合子

object YCombinator {

    fun <T, R> of(f: YFunction<YFunction<T, R>, YFunction<T, R>>): YFunction<T, R> {
        return object : YFunction<T, R> {
            override fun apply(t: T): R {
                return f.apply(of(f)).apply(t)
            }
        }
    }

    interface YFunction<in T, out R> : Function<R> {
        fun apply(t: T): R
    }
}

[CharLemAznable]

Kotlin实现Y组合子 高阶函数

object YCombinator {

    fun <T, R> of(f: ((T) -> R) -> ((T) -> R)): (T) -> R {
        return { t: T -> f(of(f))(t) }
    }
}