lambdaway :: lambdafact

1 | list | login |load

| |

_h1 [[fac9]] | λ factorial

_p How to compute ({i in a wiki page}) a factorial with λ calculus in a post card.
 
{pre {@ style="box-shadow:0 0 8px #000; transform:rotate(-2deg); padding:10px;"}
'{def CONS {lambda {:a :b :c} {:c :a :b}}}         -> {def CONS {lambda {:a :b :c} {:c :a :b}}}
'{def HEAD {lambda {:p} {:p {lambda {:a :b} :a}}}} -> {def HEAD {lambda {:p} {:p {lambda {:a :b} :a}}}}
'{def TAIL {lambda {:p} {:p {lambda {:a :b} :b}}}} -> {def TAIL {lambda {:p} {:p {lambda {:a :b} :b}}}}
'{def SUCC {lambda {:n :f :x} {:f {:n :f :x}}}}    -> {def SUCC {lambda {:n :f :x} {:f {:n :f :x}}}}
'{def MULT {lambda {:n :m :f :x} {:n {:m :f} :x}}} -> {def MULT {lambda {:n :m :f :x} {:n {:m :f} :x}}} 
'{def DISP {lambda {:n}
          {:n {lambda {:x} {+ :x 1}} 0}}}         -> {def DISP {lambda {:n} {:n {lambda {:x} {+ :x 1}} 0}}}
'{def c0 {lambda {:f :x} :x}}                      -> {def c0 {lambda {:f :x} :x}}
'{def c1 {lambda {:f :x} {:f :x}}}                 -> {def c1 {lambda {:f :x} {:f :x}}}
...
'{def c7 {lambda {:f :x} {:f {:f {:f {:f {:f {:f {:f :x}}}}}}}}} -> {def c7 {lambda {:f :x}
             {:f {:f {:f {:f {:f {:f {:f :x}}}}}}}}}

'{def FACT {lambda {:n}
  {TAIL {{:n {lambda {:p}
   {CONS {SUCC {HEAD :p}}
         {MULT {HEAD :p} {TAIL :p}}}}}
   {CONS {c1} {c1}}}}}}                           -> {def FACT
 {lambda {:n}
  {TAIL {{:n {lambda {:p}
   {CONS {SUCC {HEAD :p}} {MULT {HEAD :p} {TAIL :p}}}}}
   {CONS {c1} {c1}}}}}}

'{DISP {c7}}                                       -> {DISP {c7}}
'{DISP {FACT {c7}}}                                -> {DISP {FACT {c7}}}
}

_p In other words

{pre {@ style="box-shadow:0 0 8px #000; transform:rotate(1deg); padding:10px;"}
'{DISP  
 {{lambda {:n}
  {{lambda {:c} {:c 
    {lambda {:a :b} :b}}} {{:n 
     {lambda {:p} 
     {{lambda {:a :b :c} {:c :a :b}}
      {{lambda {:n :f :x} {:f {:n :f :x}}}
       {{lambda {:c} {:c
         {lambda {:a :b} :a}}} :p}}
         {{lambda {:n :m :f :x} {:n {:m :f} :x}}
          {{lambda {:c} {:c
            {lambda {:a :b} :a}}} :p}
            {{lambda {:c} {:c
              {lambda {:a :b} :b}}} :p}}}}}
              {{lambda {:a :b :c} {:c :a :b}}
               {{lambda {:n :f :x} {:f {:n :f :x}}}
                 {lambda {:a :b} :b}}
                 {{lambda {:n :f :x} {:f {:n :f :x}}}
                   {lambda {:a :b} :b}}}}}} 
                   {{lambda {:f :x}
                    {:f {:f {:f {:f {:f {:f {:f :x}}}}}}}}}}}
-> 5040
}

_ul Explanations in [[fromroots2canopy]].
_ul Feedback in [[Hacker News|https://news.ycombinator.com/item?id=24658404]]: null, as usual.