Fibonacci Function Gallery - Part 1

In this deck we are going to look at a number of different implementations of a function for computing the nth element of the Fibonacci sequence.

In part 1 we look at the following:
* Naïve Recursion
* Efficient Recursion with Tupling
* Tail Recursion with Accumulation
* Tail Recursion with Folding
* Stack-safe Recursion with Trampolining

Transcript

1. Fibonacci Function Gallery @philip_schwarz slides by https://fpilluminated.com/ Part 1 • Naïve Recursion • Efficient Recursion with Tupling • Tail Recursion with Accumulation • Tail Recursion with Folding • Stack-safe Recursion with Trampolining
2. In this deck we are going to look at a number of different implementations of a function for computing the nth element of the Fibonacci sequence. To begin with, let’s see how Paul Hudak introduces what is known as the ‘naïve’ implementation. @philip_schwarz
3. Paul E. Hudak 14.2 Recursive Streams Many problems are most easily solved using recursive streams. The use of recursive streams, a very powerful programming idiom, will be explored in detail in this section. Consider, for example, the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … in which the first two numbers are 1, and each subsequent number is the sum of its two predecessors. The value of the nth Fibonacci number is defined mathematically as: 𝑓𝑖𝑏 𝑛 = 1 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏 𝑛 − 2 From this definition, a Haskell function can be defined straightforwardly to compute the nth Fibonacci number: 𝑓𝑖𝑏 ∷ 𝐼𝑛𝑡𝑒𝑔𝑒𝑟 → 𝐼𝑛𝑡𝑒𝑔𝑒𝑟 𝑓𝑖𝑏 0 = 1 𝑓𝑖𝑏 1 = 1 𝑓𝑖𝑏 𝑛 = 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏 𝑛 − 2 There is only one problem: This function is horribly inefficient! DETAILS Try running this program on successively larger values of n; In Hugs, values larger than only 20 or so cause a noticeable delay. 𝑖𝑓 𝑛 = 0 ∨ 𝑛 = 1 𝑖𝑓 𝑛 ≥ 2 1 naïve implementation #1
4. To understand the cause of this inefficiency, let’s begin the calculation of, say, 𝑓𝑖𝑏 8 : 𝑓𝑖𝑏 8 ⇒ 𝑓𝑖𝑏 7 + 𝑓𝑖𝑏 6 ⇒ 𝑓𝑖𝑏 6 + 𝑓𝑖𝑏 5 + 𝑓𝑖𝑏 5 + 𝑓𝑖𝑏 4 ⇒ 𝑓𝑖𝑏 5 + 𝑓𝑖𝑏 4 + 𝑓𝑖𝑏 4 + 𝑓𝑖𝑏 3 + 𝑓𝑖𝑏 4 + 𝑓𝑖𝑏 3 + 𝑓𝑖𝑏 3 + 𝑓𝑖𝑏 2 ⇒ 𝑓𝑖𝑏 4 + 𝑓𝑖𝑏 3 + 𝑓𝑖𝑏 3 + 𝑓𝑖𝑏 2 + 𝑓𝑖𝑏 3 + 𝑓𝑖𝑏 2 + 𝑓𝑖𝑏 2 + 𝑓𝑖𝑏 1 + 𝑓𝑖𝑏 3 + 𝑓𝑖𝑏 2 + 𝑓𝑖𝑏 2 + 𝑓𝑖𝑏 1 + 𝑓𝑖𝑏 2 + 𝑓𝑖𝑏 1 + 𝑓𝑖𝑏 1 + 𝑓𝑖𝑏 0 … It is easy to see that this calculation is blowing up exponentially. That is, to compute the nth Fibonacci number will require a number of steps proportional to 2n. Sadly, many of the computations are being repeated, but in general we cannot expect a Haskell implementation to realise this and take advantage of it. So what do we do? Paul E. Hudak naïve implementation #1
5. As for recursive streams (mentioned in the first of the previous two slides), we will be looking into their use later on. 𝑓𝑖𝑏 ∷ 𝐼𝑛𝑡𝑒𝑔𝑒𝑟 → 𝐼𝑛𝑡𝑒𝑔𝑒𝑟 𝑓𝑖𝑏 0 = 1 𝑓𝑖𝑏 1 = 1 𝑓𝑖𝑏 𝑛 = 𝑓𝑖𝑏 𝑛 − 1 + 𝑓𝑖𝑏 𝑛 − 2 def fib(i: Int): BigInt = i match case 0 => 0 case 1 => 1 case _ => fib(i - 1) + fib(i - 2) As we have just seen, the naïve☨ implementation consists of a recursive function whose time complexity is exponential in its parameter. Here is the Scala version of the Haskell function. naïve implementation #1 ☨ at this point we refer to the naïve implementation as such due to its exponential time complexity
6. As a minimal illustration of the exponential time complexity of the naïve implementation, here are a handful of very rough timings (on my laptop) for executing a program that just calls fib to compute the nth factorial number fib(35) about 3 seconds fib(40) about 5 seconds fib(45) about 14-15 seconds fib(50) about 2 minutes
7. In the next slide, Richard Bird first gives his explanation of why the time complexity of the naïve implementation is exponential, and then shows how the tupling technique can be used to produce a second implementation whose time complexity is linear.
8. 7.4 Tupling The technique of program optimisation known as tupling is dual to that of accumulating parameters: a function is generalised, not by including an extra argument, but by including an extra result. Our aim in this section is to illustrate this important technique through a number of instructive examples. … 7.4.2 Fibonacci function Another example where tupling can improve the order of growth of the time complexity of a program is provided by the Fibonacci function. 𝑓𝑖𝑏 0 = 0 𝑓𝑖𝑏 1 = 1 𝑓𝑖𝑏 𝑛 + 2 = 𝑓𝑖𝑏 𝑛 + 𝑓𝑖𝑏 𝑛 + 1 The time to evaluate 𝑓𝑖𝑏 𝑛 by these equations is given by T 𝑓𝑖𝑏 𝑛 , where T 𝑓𝑖𝑏 0 = 𝑂 1 T 𝑓𝑖𝑏 1 = 𝑂 1 T 𝑓𝑖𝑏 𝑛 + 2 = T 𝑓𝑖𝑏 𝑛 +T 𝑓𝑖𝑏 𝑛 + 1 + 𝑂 1 The timing function T 𝑓𝑖𝑏 therefore satisfies equations very like that of 𝑓𝑖𝑏 itself. It is easy to check by induction that T 𝑓𝑖𝑏 𝑛 = Θ 𝑓𝑖𝑏 𝑛 , so the time to compute 𝑓𝑖𝑏 is proportional to the size of the result. Since 𝑓𝑖𝑏 𝑛 = Θ(𝜙𝑛), where 𝜙 is the golden ratio 𝜙 = (1 + 5)/2, the time is therefore exponential in 𝒏. Now consider the function 𝑓𝑖𝑏𝑡𝑤𝑜 defined by 𝑓𝑖𝑏𝑡𝑤𝑜 𝑛 = (𝑓𝑖𝑏 𝑛, 𝑓𝑖𝑏 (𝑛 + 1)) Clearly, 𝑓𝑖𝑏 𝑛 = 𝑓𝑠𝑡 (𝑓𝑖𝑏𝑡𝑤𝑜 𝑛). Synthesis of a recursive program for 𝑓𝑖𝑏𝑡𝑤𝑜 yields 𝑓𝑖𝑏𝑡𝑤𝑜 0 = (0,1) 𝑓𝑖𝑏𝑡𝑤𝑜 𝑛 + 1 = 𝑏, 𝑎 + 𝑏 , where 𝑎, 𝑏 = 𝑓𝑖𝑏𝑡𝑤𝑜 𝑛 It is clear that this program takes linear time. In this example the tupling strategy leads to a dramatic increase in efficiency, from exponential to linear. Richard Bird
9. def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = i match case 0 => (0, 1) case _ => fibtwo(i - 1) match { case (fibⱼ, fibₖ) => (fibₖ, fibⱼ + fibₖ) } def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = i match case 0 => (0, 1) case _ => fibtwo(i - 1) match { case (a, b) => (b, a + b) } extension [A,B](pair: (A,B)) def first: A = pair(0) 𝑓𝑖𝑏 𝑛 = 𝑓𝑠𝑡 (𝑓𝑖𝑏𝑡𝑤𝑜 𝑛) 𝑓𝑖𝑏𝑡𝑤𝑜 0 = (0,1) 𝑓𝑖𝑏𝑡𝑤𝑜 𝑛 + 1 = 𝑏, 𝑎 + 𝑏 , where 𝑎, 𝑏 = 𝑓𝑖𝑏𝑡𝑤𝑜 𝑛 As we have just seen, the second implementation also involves a recursive function, but its time complexity is linear (in its parameter), rather than exponential. Here is the Scala version of the Haskell function. We can make it look a bit easier on the eye if we rename the recursively computed fibonacci numbers from fibⱼ, and fibₖ to a and b. tupling-based implementation #2
10. Remember these timings for the naïve implementation? fib(35) about 3 seconds fib(40) about 5 seconds fib(45) about 14-15 seconds fib(50) about 2 minutes Contrast that with the fact that the tupling-based implementation takes only about 3-4 seconds to compute fib(5,000).
11. In the next two slides, Stuart Halloway explains why the naïve implementation is `stack-consuming`.
12. Let’s begin by implementing the Fibonaccis using a simple recursion. The following Clojure function will return the nth Fibonacci number: 1: ; bad idea 2: (defn stack-consuming-fibo [n] 3: (cond 4: (= n 0) 0 5: (= n 1) 1 6: :else (+ (stack-consuming-fibo (- n 1)) 7: (stack-consuming-fibo (- n 2))))) Lines 4 and 5 define the basis, and line 6 defines the induction. The implementation is recursive because stack-consuming-fibo calls itself on lines 6 and 7. Test that stack-consuming-fibo works correctly for small values of n: (stack-consuming-fibo 9) -> 34N Good so far, but there’s a problem calculating larger Fibonacci numbers such as F(1000000): (stack-consuming-fibo 1000000) -> StackOverflowError clojure.lang.Numbers.minus (Numbers.java:1837) def fib(i: Int): BigInt = i match case 0 => 0 case 1 => 1 case _ => fib(i - 1) + fib(i - 2) naïve implementation Stuart Halloway stuarthalloway naïve implementation #1
13. Stuart Halloway stuarthalloway Because of the recursion, each call to stack-consuming-fibo for n > 1 begets two more calls to stack-consuming-fibo. At the JVM level, these calls are translated into method calls, each of which allocates a data structure called a stack frame. The stack-consuming-fibo creates a depth of stack frames proportional to n, which quickly exhausts the JVM stack and causes the StackOverflowError shown earlier. (It also creates a total number of stack frames that’s exponential in n, so its performance is terrible even when the stack does not overflow.) Clojure function calls are designated as stack-consuming because they allocate stack frames that use up stack space. In Clojure, you should almost always avoid stack-consuming recursion as shown in stack-consuming-fibo. As an example of the naïve☨ implementation blowing the stack, if we try to use it to compute the ten thousandth Fibonacci number, we get a stack overflow error. $ scala Welcome to Scala 3.5.0 (22.0.2, Java OpenJDK 64-Bit Server VM). Type in expressions for evaluation. Or try :help. scala> def fib(i: Int): BigInt = i match | case 0 => 0 | case 1 => 1 | case _ => fib(i - 1) + fib(i - 2) | def fib(i: Int): BigInt scala> fib(10_000) java.lang.StackOverflowError at rs$line$1$.fib(rs$line$1:4) <…above line repeated 1023 more times…> ☨ at this point we refer to the naïve version as such due to both its exponential time complexity and its stack consumption
14. The tupling-based implementation is also stack-consuming, so it also blows the stack for sufficiently large n, e.g. scala> extension [A,B](pair: (A,B)) | def first: A = pair(0) | def first[A, B](pair: (A, B)): A scala> def fibtwo(i: Int): (BigInt, BigInt) = i match | case 0 => (0, 1) | case _ => fibtwo(i - 1) match { case (a, b) => (b, a + b) } | def fibtwo(i: Int): (BigInt, BigInt) scala> def fib(i: Int): BigInt = | fibtwo(i).first | def fib(i: Int): BigInt scala> fib(7_500) java.lang.StackOverflowError at rs$line$3$.fibtwo(rs$line$3:1) <…above line repeated 1023 more times…> def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = i match case 0 => (0, 1) case _ => fibtwo(i - 1) match { case (a, b) => (b, a + b) } tupling-based implementation #2
15. In the next 3 slides, Stuart Halloway looks at a tail-recursive implementation, and a self-recursive implementation.
16. Tail Recursion Functional programs can solve the stack-usage problem with tail recursion. A tail-recursive function is still defined recursively, but the recursion must come at the tail, that is, at an expression that’s a return value of the function. Languages can then perform tail-call optimization (TCO), converting tail recursions into iterations that don’t consume the stack. The stack-consuming-fibo definition of Fibonacci is not tail recursive, because it calls add (+) after both calls to stack-consuming-fibo. To make fibo tail recursive, you must create a function whose arguments carry enough information to move the induction forward, without any extra “after” work (like an addition) that would push the recursion out of the tail position. For fibo, such a function needs to know two Fibonacci numbers, plus an ordinal n that can count down to zero as new Fibonaccis are calculated. You can write tail-fibo as follows: 1: (defn tail-fibo [n] 2: (letfn [(fib 3: [current next n] 4: (if (zero? n) 5: current 6: (fib next (+ current next) (dec n))))] 7: (fib 0N 1N n))) Line 2 introduces the letfn macro: (letfn fnspecs & body) ; fnspecs ==> [(fname [params*] exprs)+] letfn is like let but is dedicated to creating local functions. Each function declared in a letfn can call itself or any other function in the same letfn block. Line 3 declares that fib has three arguments: the current Fibonacci, the next Fibonacci, and the number n of steps remaining. Line 5 returns current when there are no steps remaining, and line 6 continues the calculation, decrementing the remaining steps by one. Finally, line 7 kicks off the recursion with the basis values 0 and 1, plus the ordinal n of the Fibonacci we’re looking for. Stuart Halloway stuarthalloway
17. tail-fibo works for small values of n: (tail-fibo 9) -> 34N But although it’s tail recursive, it still fails for large n: (tail-fibo 1000000) -> StackOverflowError java.lang.Integer.numberOfLeadingZeros (Integer.java:1054) The problem here is the JVM. While functional languages such as Scheme or Haskell perform TCO, the JVM doesn’t perform this optimization. The absence of TCO is unfortunate but not a showstopper for functional programs. Clojure provides several pragmatic workarounds: explicit self-recursion with recur, lazy sequences, and explicit mutual recursion with trampoline. We’ll discuss the first two here and defer the discussion of trampoline, which is a more advanced feature, until later in the chapter. Self-recursion with recur One special (and common) case of recursion that can be optimized away on the JVM is self-recursion. Fortunately, the tail-fibo is an example: it calls itself directly, not through some series of intermediate functions. Stuart Halloway stuarthalloway
18. In Clojure, you can convert a function that tail-calls itself into an explicit self-recursion with recur. Using this approach, convert tail-fibo into recur-fibo: 1: ; better but not great 2: (defn recur-fibo [n] 3: (letfn [(fib 4: [current next n] 5: (if (zero? n) 6: current 7: (recur next (+ current next) (dec n))))] 8: (fib 0N 1N n))) The critical difference between tail-fibo and recur-fibo is on line 7, where recur replaces the call to fib. The recur-fibo won’t consume stack as it calculates Fibonacci numbers and can calculate F(n) for large n if you have the patience: (recur-fibo 9) -> 34N (recur-fibo 1000000) -> 195 ... 208,982 other digits ... 875N Stuart Halloway stuarthalloway
19. In Scala there is no need for explicit self-recursion: in the case of a function recursively calling itself in tail position, the compiler automatically performs tail-call optimisation. See the next slide for how Dean Wampler puts it.
20. def fib(i: Int): BigInt = i match case 0 => 0 case 1 => 1 case _ => fib(i - 1) + fib(i - 2) Recursion is a hallmark of FP and a powerful tool for writing elegant implementations of many algorithms. Hence, the Scala compiler does limited tail-call optimizations itself. It will handle functions that call themselves, but not mutual recursion (i.e., “a calls b calls a calls b,” etc.). Still, you might want to know if you got it right and the compiler did in fact perform the optimization. No one wants a blown stack in production. Fortunately, the compiler can tell you if you got it wrong if you add an annotation, tailrec, as shown in this refined version of factorial: … … If fact is not actually tail recursive, the compiler will throw an error. Consider this attempt to write a naïve recursive implementation of Fibonacci sequences: scala> import scala.annotation.tailrec scala> @tailrec | def fibonacci(i: Int): BigInt = | if i <= 1 then BigInt(1) | else fibonacci(i - 2) + fibonacci(i - 1) 4 | else fibonacci(i - 2) + fibonacci(i - 1) | ^^^^^^^^^^^^^^^^ | Cannot rewrite recursive call: it is not in tail position 4 | else fibonacci(i - 2) + fibonacci(i - 1) | ^^^^^^^^^^^^^^^^ | Cannot rewrite recursive call: it is not in tail position We are attempting to make two recursive calls, not one, and then do something with the returned values, in this case add them. So this function is not tail recursive. (It is naïve because it is possible to write a tail recursive implementation.) naïve implementation naïve implementation #1 Dean Wampler @deanwampler
21. Here is the Scala version of the Clojure tail-recursive☨ implementation. (defn tail-fibo [n] (letfn [(fib [current next n] (if (zero? n) current (fib next (+ current next) (dec n))))] (fib 0N 1N n))) def fib(i: Int): BigInt = tailFib(0, 1, i) @tailrec def tailFib(fibⱼ: BigInt, fibₖ: BigInt, i: Int): BigInt = i match case 0 => fibⱼ case _ => tailFib(fibₖ, fibⱼ + fibₖ, i - 1) def fib(i: Int): BigInt = tailFib(0, 1, i) @tailrec def tailFib(a: BigInt, b: BigInt, i: Int): BigInt = i match case 0 => a case _ => tailFib(b, a + b, i - 1) Again, we can make it look a bit easier on the eye by renaming the recursively computed fibonacci numbers from fibⱼ and fibₖ to a and b. tail-recursive implementation #3 ☨ the tail-recursive version is not naïve because it is stack-safe and its time complexity is linear rather than exponential
22. Remember the fact that the tupling-based implementation encountered a stack overflow when computing fib(7,500)? As an example, the tail-recursive implementation is perfectly happy to compute fib(10,000): assert(fib(10_000) == BigInt("3364476487643178326662161200510754331030214846068006390656476997468008144216666236815559551363 373402558206533268083615937373479048386526826304089246305643188735454436955982749160660209988418393386 465273130008883026923567361313511757929743785441375213052050434770160226475831890652789085515436615958 298727968298751063120057542878345321551510387081829896979161312785626503319548714021428753269818796204 693609787990035096230229102636813149319527563022783762844154036058440257211433496118002309120828704608 892396232883546150577658327125254609359112820392528539343462090424524892940390170623388899108584106518 317336043747073790855263176432573399371287193758774689747992630583706574283016163740896917842637862421 283525811282051637029808933209990570792006436742620238978311147005407499845925036063356093388383192338 678305613643535189213327973290813373264265263398976392272340788292817795358057099369104917547080893184 105614632233821746563732124822638309210329770164805472624384237486241145309381220656491403275108664339 451751216152654536133311131404243685480510676584349352383695965342807176877532834823434555736671973139 274627362910821067928078471803532913117677892465908993863545932789452377767440619224033763867400402133 034329749690202832814593341882681768389307200363479562311710310129195316979460763273758925353077255237 594378843450406771555577905645044301664011946258097221672975861502696844314695203461493229110597067624 326851599283470989128470674086200858713501626031207190317208609408129832158107728207635318662461127824 553720853236530577595643007251774431505153960090516860322034916322264088524885243315805153484962243484 829938090507048348244932745373262456775587908918719080366205800959474315005240253270974699531877072437 682590741993963226598414749819360928522394503970716544315642132815768890805878318340491743455627052022 356484649519611246026831397097506938264870661326450766507461151267752274862159864253071129844118262266 105716351506926002986170494542504749137811515413994155067125627119713325276363193960690289565028826860 8362241082050562430701794976171121233066073310059947366875"))
23. Next, here is an implementation using a left fold. def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = (1 to i).foldLeft(BigInt(0), BigInt(1)) { case ((a, b), _) => (b, a + b) } While it consists of two functions, neither of which is recursively defined, a left fold is tail recursive, so the time complexity of this implementation is linear. 𝑓𝑜𝑙𝑑𝑙 ∷ 𝛽 → 𝛼 → 𝛽 → 𝛽 → 𝛼 → 𝛽 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 = 𝑏 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑏 𝑥: 𝑥𝑠 = 𝑓𝑜𝑙𝑑𝑙 𝑓 𝑓 𝑏 𝑥 𝑥𝑠 @tailrec def foldl[A,B](f: B => A => B)(b: B)(as: List[A]): B = as match case Nil => b case x::xs => foldl(f)(f(b)(x))(xs) left fold-based implementation #4
24. def fib(i: Int): BigInt = i match case 0 => 0 case 1 => 1 case _ => fib(i - 1) + fib(i - 2) version #1 (naïve) • not tail-recursive (not stack-safe) • exponential time complexity • linear stack frame depth def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = i match case 0 => (0, 1) case _ => fibtwo(i - 1) match { case (a, b) => (b, a + b) } version #2 (tupling-based) • not tail-recursive (not stack-safe) • linear time complexity • linear stack frame depth Implementations explored so far def fib(i: Int): BigInt = tailFib(0, 1, i) @tailrec def tailFib(a: BigInt, b: BigInt, i: Int): BigInt = i match case 0 => a case _ => tailFib(b, a + b, i - 1) version #3 (tail-recursive) • tail-recursive (stack-safe) • linear time complexity def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = (1 to i).foldLeft(BigInt(0), BigInt(1)) { case ((a, b), _) => (b, a + b) } version #4 (left fold-based) • non-recursive (stack-safe) • linear time complexity
25. Sergei Winitzki sergei-winitzki-11a6431 There is no automatic recipe for converting an arbitrary function into a tail-recursive one. The accumulator trick does not always work! In some cases, it is impossible to implement tail recursion in a given recursive computation. An example of such a computation is the “merge-sort” algorithm where the function body must contain two recursive calls within a single expression. (It is impossible to rewrite two recursive calls as one tail call.) What if our recursive code cannot be transformed into tail-recursive code via the accumulator trick, but the recursion depth is so large that stack overflows occur? There exist special techniques (e.g., “continuations” and “trampolines”) that convert non-tail-recursive code into code that runs without stack overflows. While we have already seen that it is possible to write a tail recursive implementation (e.g. version #2), there is a technique, called trampolining, that can be used to make even the naïve implementation stack safe.
26. In the next two slides we look at how Noel Welsh explains how the Eval monad in Cats can be used for trampolining purposes.
27. Noel Welsh @noelwelsh 9.6.4 Trampolining and Eval.defer One useful property of Eval is that its map and flatMap methods are trampolined. This means we can nest calls to map and flatMap arbitrarily without consuming stack frames. We call this property “stack safety”. For example, consider this function for calculating factorials: def factorial(n: BigInt): BigInt = if (n == 1) n else n * factorial(n - 1) It is relatively easy to make this method stack overflow: factorial(50000) // java.lang.StackOverflowError // ... We can rewrite the method using Eval to make it stack safe: def factorial(n: BigInt): Eval[BigInt] = if(n == 1) { Eval.now(n) } else { factorial(n - 1).map(_ * n) }
28. Noel Welsh @noelwelsh factorial(50000).value // java.lang.StackOverflowError // ... Oops! That didn’t work—our stack still blew up! This is because we’re still making all the recursive calls to factorial before we start working with Eval's map method. We can work around this using Eval.defer, which takes an existing instance of Eval and defers its evaluation. The defer method is trampolined like map and flatMap, so we can use it as a quick way to make an existing operation stack safe: def factorial(n: BigInt): Eval[BigInt] = if(n == 1) { Eval.now(n) } else { Eval.defer(factorial(n - 1).map(_ * n)) } factorial(50000) // res: A very big value Eval is a useful tool to enforce stack safety when working on very large computations and data structures. However, we must bear in mind that trampolining is not free. It avoids consuming stack by creating a chain of function objects on the heap. There are still limits on how deeply we can nest computations, but they are bounded by the size of the heap rather than the stack.
29. /** * Eval is a monad which controls evaluation. * * This type wraps a value (or a computation that produces a value) * and can produce it on command via the `.value` method. * * There are three basic evaluation strategies: * * - Now: evaluated immediately * - Later: evaluated once when value is needed * - Always: evaluated every time value is needed * * The Later and Always are both lazy strategies while Now is eager. * Later and Always are distinguished from each other only by * memoization: once evaluated Later will save the value to be returned * immediately if it is needed again. Always will run its computation * every time. * * Eval supports stack-safe lazy computation via the .map and .flatMap * methods, which use an internal trampoline to avoid stack overflows. * Computation done within .map and .flatMap is always done lazily, * even when applied to a Now instance. * … */ sealed abstract class Eval[+A] extends … /** * Defer a computation which produces an Eval[A] value. * * This is useful when you want to delay execution of an expression * which produces an Eval[A] value. Like .flatMap, it is stack-safe. */ def defer[A](a: => Eval[A]): Eval[A] = … /** * Construct an eager Eval[A] value (i.e. Now[A]). */ def now[A](a: A): Eval[A] = Now(a) def factorial(n: BigInt): Eval[BigInt] = if(n == 1) { Eval.now(n) } else { Eval.defer(factorial(n - 1).map(_ * n)) }
30. def fib(i: Int): Eval[BigInt] = i match case 0 => Eval.now(0) case 1 => Eval.now(1) case _ => for a <- Eval.defer(fib(i - 1)) b <- fib(i - 2) yield a + b Here is how we can use the Eval monad to make the naïve implementation stack-safe def fib(i: Int): BigInt = i match case 0 => 0 case 1 => 1 case _ => fib(i - 1) + fib(i - 2) def fib(i: Int): Eval[BigInt] = i match case 0 => Eval.now(0) case 1 => Eval.now(1) case _ => Eval.defer(fib(i - 1)) .flatMap(a => fib(i - 2) .map(b => a + b)) same as above, but using the syntactic sugar of a for comprehension stack-safe naïve Eval-based implementation #5 ☨ we refer to this version as naïve because while it is stack-safe, its time complexity is still exponential
31. Remember these timings for the naïve implementation? Naïve fib(35) about 3 seconds fib(40) about 5 seconds fib(45) about 14-15 seconds fib(50) about 2 minutes While the stack-safe naïve implementation avoids stack overflows, it is much slower than the naïve one, e.g. Stack-safe naïve fib(35) about 5 seconds fib(40) about 14-15 seconds fib(45) about 2 minutes fib(50) ? I got bored of waiting after 20 minutes, but it had finished within 23.
32. If you are interested in knowing more about trampolining, consider taking a look at this
33. We can also do something similar with the Cats Effect IO Monad, because 1. its map and flatMap functions are also trampolined 2. it also provides a defer function. By the way, the documentation for IO provides a Fibonacci function example! /** * Suspends a synchronous side effect which produces an `IO` in `IO`. * * This is useful for trampolining (i.e. when the side effect is conceptually the allocation * of a stack frame). Any exceptions thrown by the side effect will be caught and sequenced * into the `IO`. */ def defer[A](thunk: => IO[A]): IO[A] = … … IO is trampolined in its flatMap evaluation. This means that you can safely call flatMap in a recursive function of arbitrary depth, without fear of blowing the stack. def fib(n: Int, a: Long = 0, b: Long = 1): IO[Long] = IO.pure(a + b) flatMap { b2 => if (n > 0) fib(n - 1, b, b2) else IO.pure(a) } /** * Lifts a pure value into `IO`. … */ def pure[A](value: A): IO[A] = …
34. Here is the IO equivalent of the Eval-based stack-safe implementation. def fib(i: Int): IO[BigInt] = i match case 0 => IO.pure(0) case 1 => IO.pure(1) case _ => for a <- IO.defer(fib(i - 1)) b <- fib(i - 2) yield a + b stack-safe naïve IO-based implementation #6 def fib(i: Int): Eval[BigInt] = i match case 0 => Eval.now(0) case 1 => Eval.now(1) case _ => for a <- Eval.defer(fib(i - 1)) b <- fib(i - 2) yield a + b ☨ we also refer to this version as naïve because while it is stack-safe, its time complexity is still exponential
35. To conclude part 1, the next slide is a recap of the different implementations that we have explored.
36. version #1 (naïve) • not tail-recursive (not stack-safe) • exponential time complexity • linear stack frame depth version #2 (tupling-based) • not tail-recursive (not stack-safe) • linear time complexity • linear stack frame depth Implementations explored so far version #3 (accumulator-based) • tail-recursive (stack-safe) • linear time complexity def fib(i: Int): Eval[BigInt] = i match case 0 => Eval.now(0) case 1 => Eval.now(1) case _ => for a <- Eval.defer(fib(i - 1)) b <- fib(i - 2) yield a + b def fib(i: Int): IO[BigInt] = i match case 0 => IO.pure(0) case 1 => IO.pure(1) case _ => for a <- IO.defer(fib(i - 1)) b <- fib(i - 2) yield a + b def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = (1 to i).foldLeft(BigInt(0), BigInt(1)) { case ((a, b), _) => (b, a + b) } def fib(i: Int): BigInt = i match case 0 => 0 case 1 => 1 case _ => fib(i - 1) + fib(i - 2) 1 def fib(i: Int): BigInt = fibtwo(i).first def fibtwo(i: Int): (BigInt, BigInt) = i match case 0 => (0, 1) case _ => fibtwo(i - 1) match { case (a, b) => (b, a + b) } 2 def fib(i: Int): BigInt = tailFib(0, 1, i) def tailFib(a: BigInt, b: BigInt, i: Int): BigInt = i match case 0 => a case _ => tailFib(b, a + b, i - 1) 3 4 5 6 1 2 3 version #4 (stack-safe naïve - Eval-based) • not tail-recursive but stack-safe • exponential time complexity 5 version #5 (stack-safe naïve - IO-based) • not tail-recursive but stack-safe • exponential time complexity 6 version #4 (left fold-based) • non-recursive (stack-safe) • linear time complexity 4
37. See you in part 2, in which we generate potentially infinite streams of Fibonacci numbers. @philip_schwarz