6 ms·

Church factorial can be implemented without recursion though. Hint: consider a function that maps the pair <n,n!> to <(n+1),(n+1)!> ...

• tromp 13y ago
  Here is Church factorial in graphical notation: ┬────────────────────── │ ┬────────────── ─ ┬ ┬ │ ┼─┬───────┬──── ┬ │ │ │ ┼─┼───────┼─┬── │ │ │ │ │ ┼─┬─┬── ┼─┼─┬ │ │ │ │ │ ┼─┼─┼─┬ │ ├─┘ │ │ │ │ │ └─┤ ├─┘ ├─┘ │ │ │ │ │ ├─┘ │ │ │ │ │ └───┤ │ │ │ │ │ ├─────┘ │ │ │ └─────┤ │ │ │ └───────────┤ │ │ └─┤ │ └─┘
  • lisper 13y ago
    That's pretty cool looking, but I have no idea what I'm looking at. Does this notation have a name? Is it documented somewhere? (Hm, I wonder how hard it would be to write a parser for it. :-)
    • tromp 13y ago
      That's my graphical notation for lambda calculus, documented at http://www.cwi.nl/~tromp/cl/diagrams.html http://www.cwi.nl/~tromp/cl/diagrams.html Btw, here's an even shorter version of factorial: ┬──────────────── ┼─────────────┬── │ ──┬──────── ┼ ┬ │ ┬─┼─┬────── │ │ │ │ │ ┼─┬─┬── │ │ │ │ │ ┼─┼─┼─┬ │ │ │ │ │ └─┤ ├─┘ │ │ │ │ │ ├─┘ │ │ │ │ ├───┘ │ │ │ ├─┘ │ │ └─┤ │ │ └───────────┤ │ └─┘ In de-Bruijn notation it is \\2 (\\1 (2 (\\3 2 (2 1)))) (\2) (\1), which in conventional notation is \n\f.n (\x\m.m (x (\a\b.m a (a b)))) (\x.f) (\x.x)
      • lisper 13y ago
        Wow! That is wicked-cool! Thanks!
      • lisper 13y ago
        BTW, is there a description of how this works written up anywhere? I tried to reverse-engineer it and got lost in lambdas. (I did manage to translate it into Scheme and verify empirically that it works!)
• lisper 13y ago
  Whether the loop is recursive or iterative you still need a loop, so you still need a Y combinator.
  • tromp 13y ago
    You don't need Y if you apply a Church numeral instead, which gives you a bounded iteration.
    • lisper 13y ago
      Ah, good point!