Y Combinator

y.escript

#!/usr/bin/env escript

main(_Args) ->
    Y = fun(Generator) ->
                Gen = fun(X) ->
                              fun(Args) ->
                                      (Generator(X(X)))(Args)
                              end
                      end,
                Gen(Gen)
        end,

    Fac = Y(fun(Callback) ->
                    fun(Arg) ->
                            if
                                Arg =< 1 -> 1;
                                true -> Arg * Callback(Arg-1)
                            end
                    end
            end),

    Fib = Y(fun(Callback) ->
                    fun(Arg) ->
                            if
                                Arg =< 1 -> 1;
                                true     -> Callback(Arg - 1) + Callback(Arg - 2)
                            end
                    end
            end),

    io:format("~p~n~p~n", [Fac(5), Fib(5)]).

y.rb

#!/usr/bin/env ruby

def y 
  ->(gen){gen[gen]}[
    ->(x){->(args){yield(x[x])[args]}}
  ]
end

fac = y do |callback|
  ->(i){i <= 1 ? 1 : callback[i-1] * i}
end

fib = y do |callback|
  ->(i){i <= 1 ? 1 : callback[i-1] + callback[i-2]}
end

puts "#{fac[5]}\n#{fib[5]}"

ruby 代码说明:

• lamdba{|x| dosth} 等价于 ->(x){dosth}
• func.call(args) 等价于 func[args]

revision 4变更说明: 使用函数定义ycombinator，借助yield/block机制简化代码