Sunday, March 5, 2017

Learning about the Y-Combinator

Mike Vanier wrote an awesome article on the Y-Combinator function that I've been working my way through. It's a fascinating read. Here are my notes on it so far.

  • An explicit recursive definition is a recursive function definition whose body contain the name of the recursive function. For example, (define (hello a) (hello a)).
  • It's possible to generate the recursive version of a function without using an explicit recursive definition by use of higher-order functions. Holy shit, right? 
  • The Y-Combinator is one such higher-order function that can generate a recursive version of a function by using it's non-recursive function. 
  • In functional programming, you can create the non-recursive version of a function by abstracting out the recursive call. So instead of referencing itself, it will reference a function that's to be passed in as an argument by a higher order function. Common technique in FP.
  • Pass an identity function as an argument to the non-recursive function to get the factorial of all numbers up to 0. For example, (define factorial-zero (almost-factorial identity)). This will fail for N > 0. However, it will succeed if you pass factorial-zero as an argument to factorial-one! This can be proven although why it works is still a mystery to me. 
  • By performing the above process infinity times, you can get the factorial of all numbers up to infinity. The function that can do that for all numbers up to infinity is the factorial function! But how the heck do you define this chain of functions up to infinity?
  • To be continued ...



No comments:

Post a Comment