共计 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)
最初将 bar
和 baz
联合起来:
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
正文完