hello. – foldr

hello.

@jessewilliamson

            
            function doubleList(nums){
              var res = [];
              for(var i = 0; i < nums.length; i++){
                res.push(nums[i] * 2);
              }
              return res;
            }
            
          

• Today I want to talk about loops
• This is a simple loop, we've all written something like it
• In imperative languages loops are the primary means of iteration
• They become so common place we don't even notice the moving parts

what if javascript didn't have loops?

Array.prototype.map/forEach/reduce/filter

cheater!

• pretend there were no native iteration methods
• pretend you were concerned with something other than arrays

recursion:

see recursion

recursion occurs when the solution to a problem depends on the solution to smaller versions of the same problem

recursion & loops solve the same problem

both are used to repeat an action

however...

there is a subtle but important distinction between the two

let's compare

            
            function sum(nums){
              var res 0;
              for(var i = 0; i < nums.length; i++){
                res += nums[i];
              }
              return res;
            }
            
          

            
            function sum(nums){
              if(!nums.length) return 0;
              return nums.shift() + sum(nums);
            }
            
          

• In the loop we concern we have to set up state, concern ourselves with looping variables, etc.
• In the recursive version, we consider different cases
• What happens if the list is empty? What happens otherwise

recursive thinking

it's not just a function calling itself

it requires a new way of looking at problems

• if you're like me, you learned with loops, so you need to unlearn them
• recursion requires a different perspective, but it is actually much simpler

establish the base case(s) that return a value

reduce the input so that a base case is eventually hit

• begin with a base or terminal case (or cases)
• the terminal case will be the stopping point for the function and returns some value
• then reduce your input with each step until a base case is met

maximum

find the largest number in an list

what do we do if the list is empty?

probably throw an error

what do we do if it's a singleton list?

return the only number we have

what do we do otherwise?

compare the head to the largest number from the rest of the list

ES5

            
              function maximum(nums){
                if(!nums.length) throw "empty list";
                if(nums.length == 1) return nums[0];
                return Math.max(nums.shift(), maximum(nums));
              }
            
          

ES6

            
              function maximum([x, ...xs]){
                if (x === undefined) throw "empty list";
                if (xs === undefined) return x;
                return Math.max(x, maximum(xs));
              }
            
          

• ES6 gives us destructuring which simplifies things quite a bit
• It breaks the list into the head and tail
• An empty list will give us undefined x
• A singleton list will have xs undefined

Visualizing Recursion

• Being able to visualize each step of a recursive function is great for understanding
• Because much of what a loop is doing is internal, this type of reasoning requires assumptions
• Whereas with recursion each step is literally the output of the current function

sum([1,2,3,4,5])

1 + (sum([2,3,4,5]))

1 + (2 + (sum([3,4,5])))

1 + (2 + (3 + (sum([4,5]))))

1 + (2 + (3 + (4 + (sum([5])))))

1 + (2 + (3 + (4 + (5 + (sum([]))))))

1 + (2 + (3 + (4 + (5 + 0))))

1 + (2 + (3 + (4 + 5)))

1 + (2 + (3 + 9))

1 + (2 + 12)

1 + 14

15

• recall the function sum from before
• it sums a list by taking the first element, and adding that value to the sum of the rest of the list
• with each step we take the head and add it to the sum of the rest of the list
• this repeats until we reach then end and we get zero
• the recursion then works its way back to the final solution

so how do we define foldr/reduce for list

• foldr takes an accumulator value, a function that gets applied to the accumulator and each item in the list, and a list

what do we do with an empty list?

return the accumulator

what do we do otherwise?

apply the function to the accumulator & the head of the list, then fold the rest

            
              function foldr(a, f, xs){
                if(!xs.length) return a;
                return foldr(f(a, xs.shift()), f, xs);
              }
            
          

            
              function foldr(a, f,[x, ...xs]){
                return (x === undefined) ? a : foldr(f(x), f, xs);
              }
            
          

            
              function add(x,y){
                return x + y;
              }

              foldr(0, add, [1,2,3,4,5]) //=> 15
            
          

visualizing foldr

• recall the recursion can parallel structures, foldr is a nice illustration

1 : 2 : 3 : 4 : 5 : []

• notice how much this looks like the result of the sum function
• that similarity illustrates that sum is actually a fold
• as such it could be written as a partially applied fold
• this also illustrates an important point about recursive functions: they can mirror the structures they operate on

flavors of recursion

direct recursion

most common example of recursion

involves a function calling itself one or more times

natural fit when dealing with recursive data structure

• this is the type of recursion focused on in this talk
• by "one or more times" I'm the number of times the function is called at each step
• if the function is called once, it's just referred to as direct. More than once is "multiple"

multiple recursion

direct recursion with multiple calls

            
              function fib(n){
                if(n === 0) return 0;
                if(n === 1) return 1;
                return fib(n-2) + fib(n-1);
              }
            
          

• if I'm honest, I couldn't express this visually
• however, it does illustrate how closely recursive functions mirror the underlying algorithm
• this is pretty close to the textbook definition for calculating fibonnacci numbers

mutual/indirect recursion

2 or more functions calling each other

natural fit when dealing with mutually recursive structures (trees)

even/odd

            
              function isEven(n){
                return n === 0 ? true : isOdd(n-1);
              }

              function isOdd(n){
                return n === 0 ? false : isEven(n-1);
              }
            
          

            
            isEven(4); //=> true;
            //=> isEven(4) => isOdd(3) => isEven(2) => isOdd(1) => isEven(0) => true
            
          

• this function works by bouncing back between functions until one ends on zero

why not recursion

ye olde call stack

each call creates a new stack frame

each call builds a deferred operation

these operations can't be run until the final call

• because of these limitations, recursion is a bad idea for large calculations

But recursion is old, surely this is solved

yup, and the solution is tail-recursion

a tail call occurs when the final action of a function is a function call

if that function recurses, we have tail-recursion

tail-recursive sum

            
              function sum(nums){
                return go(0, nums);

                function go(a, [x, ...xs]){
                  if(x === undefined) return a;
                  return go(a + x, xs);
                }
              }
              
            

tail-recursive functions rely on an accumulator

the function is given the current state of the return value

going back through stack isn't required

some languages optimize tail-recursion

the result is effectively a loop

it runs in constant time & linear space

javascript is *not* one of those languages

yet

es6 will support "proper tail-calls"

• I personally thinkg proper tail-calls is huge, and doesn't get enough love
• It means you don't need to write loops, your tail-recursive functions will operate in the same space as loops
• Douglas Crockford (for whatever that is worth), gave a talk at NordicJS last year and said that once tail-calls land in ES6, he'll never right a loop again. Admittedly, that was one of only, maybe, two things in his talk that made a lick of sense (the other being that he doesn't use 'this').

there is no support for tail-call optimzation currently

some libraries, like babel (formerly 6to5), do have support

trampolines to the rescue

a trampoline is a mechanism for looping over thunk-returning functions, and invoking them; simulating tail-call elimination

yes you have to use a loop to build a trampoline

no the irony is not lost on me

thunk???

a thunk is just an unevaluated expression

so a "thunk-returning" function is one that returns a function that, when invoked, will perform the next computation

• thunks are how lazy languages like Haskell work. Everything is wrapped in a thunk which isn't invoked until it is needed

                
                  function trampoline(fn){
                    return function(/*args*/){
                      var res = fn.apply(this, arguments);
                      while(res instanceof Function){
                        res = res();
                      }
                      return res;
                    }
                  }
                
              

trampoline is a decorator that adds tail-call optimization to the original function

using the trampoline

              
            function sum(nums){
              var go = trampoline(function _sum(a, [x, ...xs]){
                return (x === undefined) ? a : function() { return _sum(a + x, xs); };
              });
              return go(0, nums);
            }
              
            

quick recap

recursion solves problems by solving smaller versions of the same problem

recursion focuses on decomposing a problem, while loops focus on iteration

recursion allows us to visually represent our computation

recursive functions often parallel the structures they operate on

recursive functions can be a performance issue

we can use tail-recursive functions to remove direct recursion

we can use trampolines to get the benefits of tail-call elimination

the end ?

anonymous recursion

recursion without names

this can be accomplished two ways

explicitly through function passing

implicitly through reflection

lucky us!

javascript supports both

factorial

            
            function factorial(n){
              return n == 0 ? 1 : n * factorial(n-1);
            }

            factorial(5); //=> 120 
            
          

arguments.callee

            
            function factorial(n){
              return n == 0 ? 1 : n * arguments.callee(n-1);
            }

            factorial(5); //=> 120
            
          

making it higher-order

            
            function factorial(h){
              return function(n){
                return n == 0 ? 1 : n * h(n-1);
              }
            }
            
          

            
            function factorial(h){
              return function(h){
                return n == 0 ? 1 : n * h(h)(n-1);
              }
            }
            
          

but what function do we pass in

            
            factorial(factorial)(5); //=> 120
            
          

• the function we pass has to be able to calculate the next step
• if we pass factorial to itself, we get such a function
• we then need to pass along function to the next step

factorial is the "fix point" of factorial

• the fix point of any function is an input that yields the same output
• for example, fix points of a square function are 0 and 1
• for higher-order recursive functions like factorial, they are their own fix point
• but we can do better

working towards a more general solution

              
               function factorial(h){
                return  function(n){
                  var f = function(q){
                    return function(n){
                      return n == 0 ? 1 : n * q(n-1);
                    };
                  };
                  return f(h(h))(n);
                };
              }

              factorial(factorial)(5); //=> 120
            
          

• The first thing we want to get rid of is the need for factorial to call f(f). That's an implementation detail
• we introduce a new function so that our inner "factorial" function doesn't have any knowedge of the recursion
• This also separate the inner function from the variable bindings around it

refactoring

            
             var h = function(q){
              return function(n){
                return n == 0 ? 1 : n * q(n-1);
               };
             };

             function factorial(h){
              return function(n){
                return f(h(h))(n);
              };
            }

            factorial(factorial)(5); //=> 120;
            
          

• the function g in our previous step is the exact factorial function we want so we extract it here and the results are the same

a wild Y appears

            
            function factorial(f){
              return function(n){
                return n == 0 ? 1 : n * f(n-1);
              };
            }

            function Y(f){
              var g = function(h){
                return function(n){
                  return f(h(h))(n);
                }
              }

              return g(g);
            }

            Y(factorial)(5); //=> 120;
            
          

• We can abstract over f by introducing a function that accepts f as an argument
• We assign our previous version of "factorial" to g, and apply g to itself
• calling g with itself is the same thing we did when we called factorial with itself
• The result is a function that takes an argument, and recursively calls f
• This is the Y combinator (technically Z) and it computes the fixed point of a function

a more accurate Y

            
              function Y(f){
                return (function(h){
                  return function(n){
                    return f(h(h))(n);
                  }
                })(
                  function(h){
                    return function(n){
                      return f(h(h))(n);
                    }
                  }
                );
              }
            
          

• Y comes from lambda calculus which doesn't all for assignment
• This version of Y is more reflective of that

the Y combinator gives us a way to make recursive functions without names, or any other language mechanisms.

it's just functions

of course, we don't ever need to use it

it's still cool as hell though

thanks!