Chapter 2: Getting started - devhak2/fpinscala GitHub Wiki

Contents

• Notes: Chapter notes and links to further reading related to the content in this chapter
• FAQ: Questions related to the chapter content. Feel free to add questions and/or answers here related to the chapter.

Notes

We assume in this chapter that you have the Scala compiler and interpreter already up and running. See the documentation page of Scala's website for more details about how to get Scala set up and links to lots of supplementary material about Scala itself.

Factorial and Fibonacci

We also assume some familiarity with the factorial function and we give only a brief explanation of the Fibonacci sequence.

A reader has suggested that when asking for the nth fibonacci number it should be based from 1, not 0 like the current solution. i.e.

def fib(n: Int): Int = {
    @annotation.tailrec
    def loop(n: Int, prev: Int, curr: Int): Int =
      if (n <= 1) prev   //instead of n == 0. Really n at 0 should be undefined but I'm just returning 0 here...
      else loop(n-1, curr, prev + curr)
      
    loop(n, 0, 1)
  }

Lambda calculus

The notions of first-class and higher-order functions are formalized by the lambda calculus.

Parametric polymorphism

For more on parametric polymorphism, see the Wikipedia article.

Parametricity

When we can "follow the type" of a function to derive the only possible implementation, we say that the definition is given by parametricity. See the Wikipedia article on parametricity, and Philip Wadler's excellent paper Theorems for free!

Curry

The idea of Currying is named after the mathematician Haskell Curry. He also discovered one of the most important results in computer science, the Curry-Howard isomorphism which says that a program is a logical proof, and the hypothesis that it proves is its type.

Function composition

Function composition in functional programming is closely related to function composition in mathematics.

FAQ

Are tail calls optimized if the @annotation.tailrec annotation isn't there?

They are still optimized, but the compiler won't warn you if it can't do the tail call optimization.

Is there a list of other annotation types somewhere?

See the Scaladoc for the Annotation class, and expand the "known subclasses" section.

Is the common style to define loops using local functions, rather than (private) standalone functions?

Yes, this is much more common. There's no need to pollute the namespace with helper functions you don't expect anyone to call.

Is a || go(x) considered a tail call? What about a && go(x)?

Yes