Y-combinator in Erlang

[Vladimir Sekissov]

Good day,

joe> 	> Fac  = fun(0, F) -> 1; 
joe>                     (N, F) -> N * F(N-1, F) end.

Yes, I deed so many times but using fixed-point property of Y we can
easy get some interesing results.

For example, lets slightly modify our y definition:

ya(A, X) ->
  F = fun (P) -> X(fun (Arg) -> A(P(P), Arg) end) end,
  F(F).

fact(FA) ->
  fun (0) -> 1;
      (N) -> N * FA(N-1)
  end.

mk_fact1() ->
  Apply =
    fun (F, A) ->
        R=apply(F, [A]),
        io:format("arg:~p, result:~p~n", [A, R]),
        R
    end,
  ya(Apply, fun fact/1).

>From shell:

(svg@REDACTED)20> F =  svglib.lambda:mk_fact1().
#Fun<svglib.lambda.2.120521652>
(svg@REDACTED)21> F(5).
arg:0, result:1
arg:1, result:1
arg:2, result:2
arg:3, result:6
arg:4, result:24
120

Please mention that  we didn't modify our core function `fact/1' at all.

Best Regards,
Vladimir Sekissov

joe> I *strongly* object - the average joe would *not* use the Y combinator
joe> but write factorial thus:
joe> 
joe> 	> Fac  = fun(0, F) -> 1; 
joe>                     (N, F) -> N * F(N-1, F) end.
joe> 
joe>         #Fun<erl_eval.11.1870983>
joe> 	
joe> This is because the above form looks pretty much like factorial as God
joe> intended it to be written. 
joe> 
joe> It is called thus:
joe> 
joe> 	> Fac(6, Fac).
joe>         720
joe> 
joe> /Joe
joe> 
joe>   Now  how the  average  Håkan might  have  written it  is a  entirely
joe> different matter :-)
joe> 
joe> 
joe> 
joe> On Tue, 7 Jan 2003, Hakan Millroth wrote:
joe> 
joe> > Now you see why I used to argue that introducing funs etc into Erlang 
joe> > would make life tougher for the average joe :-)
joe> > 
joe> > -- Hakan
joe> > 
joe> > On Tuesday, January 7, 2003, at 06:41  PM, Vladimir Sekissov wrote:
joe> > 
joe> > > Good day,
joe> > >
joe> > > I've surprisingly found Y-combinator very useful to solve practical
joe> > > problem of writing recursive anonymous functions in Erlang.
joe> > >
joe> > > Code were translated to Erlang from
joe> > > http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html.
joe> > >
joe> > >
joe> > > -module(lambda).
joe> > >
joe> > > -export([y/1, mk_fact/0]).
joe> > >
joe> > > %% Y-combinator itself
joe> > > y(X) ->
joe> > >   F = fun (P) -> X(fun (Arg) -> (P(P))(Arg) end) end,
joe> > >   F(F).
joe> > >
joe> > > %% Factorial example
joe> > > mk_fact() ->
joe> > >   F =
joe> > >     fun (FA) ->
joe> > > 	fun (N) ->
joe> > > 	    if (N == 0) -> 1;
joe> > > 	       true -> N * FA(N-1)
joe> > > 	    end
joe> > > 	end
joe> > >     end,
joe> > >   y(F).
joe> > >
joe> > >
joe> > > From shell:
joe> > >
joe> > > 1> F = mk_fact().
joe> > > #Fun<lambda.3.115879927>
joe> > >
joe> > > 2> F(5).
joe> > > 120
joe> > >
joe> > > Best Regards,
joe> > > Vladimir Sekissov
joe> >