关于elixir:使用-Elixir-推导-Y-组合子

38次阅读

共计 1046 个字符,预计需要花费 3 分钟才能阅读完成。

如何递归调用匿名函数,这个问题困扰我很久了。直到我据说了 Y 组合子。

一般的递归函数是这样的:

defmodule M do
    def foo(x) do
        case x do
            0 -> 0
            n -> foo(n-1) + n
        end
    end
end

而后我一步步把它革新成匿名函数,首先,函数体大抵不会变:

foo = fn x ->
    case x do
        0 -> 0
        n -> foo.(n-1) + n
    end
end

这里第二个 foo 的中央应该是 foo 这个函数自身被递归调用,然而这个时候 foo 的定义还没有实现。没关系,遇到不晓得的货色,就把它作为参数吧。

所以咱们批改了函数的定义,让它首先从参数 g 承受它自身的定义,因为 g 就是 bar,为了失去下面的本来的 foo,须要将它自身作为参数传递给本人,用 g.(g) 来失去 foo。这里有点绕,可能须要多看几遍。

bar = fn g ->
    # 上一步里的 foo 从这里开始
    fn x ->
        case x do
            0 -> 0
            n -> g.(g).(n-1) + n
        end
    end
end

baz = bar.(bar)

接下来想方法先把 g.(g) 这个货色替换掉,替换的准则是不扭转运行时的执行逻辑:

bar = fn g ->
    h = fn x -> g.(g).(x) end

    fn f ->
        fn x ->
            case x do
                0 -> 0
                n -> f.(n-1) + n
            end
        end
    end.(h)
end

baz = bar.(bar)

当初能够把和 foo 无关的逻辑剥离进去了:

foo = fn f ->
    fn x ->
        case x do
            0 -> 0
            n -> f.(n-1) + n
        end
    end
end

bar = fn i ->
    fn g ->
        h = fn x -> g.(g).(x) end
    
        i.(h)
    end
end.(foo)

baz = bar.(bar)

最初将 barbaz 联合起来:

baz = fn x -> x.(x) end.((fn i -> fn g -> i.(fn x -> g.(g).(x) end) end end).(foo))

foo 提取进去:

baz = fn f ->
    fn x -> x.(x) end.(
        (
            fn i ->
                fn g ->
                    i.(fn x -> g.(g).(x) end)
                end
            end
        ).(f)
    )
end.(foo)

化简内容:

baz = fn f ->
    fn x -> x.(x) end.(fn g -> f.(fn x -> g.(g).(x) end) end 
    )
end.(foo)

替换一下参数名,最终咱们失去 Y 组合子:

y = fn f ->
    fn x -> x.(x) end.(fn x -> f.(fn y -> x.(x).(y) end) end)
end

应用一下试试看:

foo = y.(fn f ->
    fn x ->
        case x do
            0 -> 0
            n -> f.(n-1) + n
        end
    end
end)

foo.(5)
# 15

正文完
 0