Functional Programming in Scala - Day 1

Summary

Skimmed Chapter 1 and read until Chapter 2, section 2.4.2

I’ve been looking for something to learn that would help with my practical engineering skills for a while now. That was when I came across a podcast that was interviewing Boris Cherny, who used to be a principal software engineer at Meta and is currently (2025/12/21) the head of Claude code at Anthropic. In this podcast, he described a book that “has had the greatest impact on him as an engineer”. This book was “Functional Programming in Scala” by Paul Chiusano and Runar Bjarnason. So I decided to give it a try.

I pretty much skimmed through chapter 1 because I was just itching to try the exercises that all of the reviews were talking about as one of the main highlights of this book. In addition, chapter 1 discusses a lot of concepts about functional programming, but doesn’t explain the actual applications of them all. I figured that since the book would probably introduce them at the right point in time, I don’t really need to pay attention to chapter 1 in detail. So, my reading of this book basically started out in chapter 2.

Today’s session was all about learning the basics of Scala and some introduction to functional programming. Sections 2.1 through 2.3 were really all about the basics of Scala. For example, it covers how functions are written, how to do some basic printing, and running Scala in the terminal.

There were a couple of things I did find interesting in the Scala basics section. First of all, it doesn’t have a static keyword like how Java does. So if we do want a similar functionality, you create a module with the keyword object instead of class. The next interesting topic was that you write the definitions of functions after the = sign. This is really going along the lines of thinking functions as just another value, and that you are assigning a function to a variable. Now along a similar vein, every value in Scala is an object. This allows for equivalency between these notations: 1 + 2 and 1.+(2). In this situation + is a method defined for the object 1, that can take in an argument of type Int. Equivalency between these two ways to call methods also allow for equivalency between these notations as well: MyModule.abs(-42) and MyModule abs -42. The last thing I found interesting was the Unit type. This is the type that a main function will return and its literal value is () which is pronounced “unit” just like the type. The Unit type serves a very similar purpose to void in languages like Java and C. Since the main function will not return anything meaningful, this type is used as its return value. When a method has this as its return type, very often it signifies that the method introduces some sort of side effects.

Section 2.4 is where it really starts describing more about functional programming. This chapter introduces “Higher-order Functions (HOFs)”, which is all about viewing functions as just values and passing functions into functions. Before the section starts talking about HOFs though, it firsts describes how to write loops functionally.

Consider the following factorial function. As can be observed, the way to write loops without a mutating a loop variable is to make it recursive! In FP, these loop helper methods are often named go or loop by convention.

def factorial(n: Int): Int = {
  def go(n: Int, acc: Int): Int = {
    if (n <= 0) acc
    else go(n-1, n*acc)
  }
  go(n, 1);
}

This also introduces another interesting concept called tail call elimination. This is the name for a phenomenon where the Scala compiler will take the recursive function and generate the same bytecode as it would for a while loop. A call is said to be in a tail position if the caller of it does nothing other than return the value of the recursive call itself. The go(n-1, n*acc) is in the tail position, because the function go only returns the value that the call itself produces. It would not be in a tail position if for example, the invocation was go(n-1, n*acc) + 1 or 1 + go(n-1, n*acc) because the +1 still has to occur after the recursive call returns. (Note that you can write an explicit while loop in Scala, but it is considered bad form since it hinders good compositional style.) So even though this factorial function is written symantically to communicate a recursive function, in actuality it executes the same way as a while loop.

The one issue is that the Scala compiler will not automatically communicate if tail call elimination is successful. However, the annotation @annotation.tailrec can be used to communicate to the Scala compiler that it is expected that tail call elimination occurs for the recursive function that is written.

def factorial(n: Int): Int = {
  @annotation.tailrec
  def go(n: Int, acc: Int): Int = {
    if (n <= 0) acc
    else go(n-1, n*acc)
  }
  go(n, 1);
}

An exercise is then presented. The exercise is to write a function to get the n-th Fibonacci number. The first two Fibonacci numbers are 0 and 1 so an example sequence would look like 0, 1, 1, 2, 3, 5, .... The definition of the function must use a local tail-recursive function. The signature of the function is def fib(n: Int): Int. My initial solution looked like this:

object FibonacciModule {
  def fib(n: Int): Int = {
    def go(n: Int): Int = {
      if (n <= 1) n
      else go(n-1) + go(n-2)
    }
    go(n)
  }
  
  def main(arr: Array[String]): Unit = {
    fib(5)
  }
}

This solution is the textbook solution that you would write for producing Fibonacci numbers when initially learning about recursion. However, this does not satisfy the requirement that the function must be a tail-recursive function because neither go(n-1) nor go(n-2) is in a tail position. Another evidence that would point out that tail call elimination is not happening is when this is run for n=46. Why is it so slow if tail call elimination is supposed to make a function written recursively behave the same as a while loop? Lastly, @annotation.tailrec can be written above the method signature and a compile time error would be thrown.

After some time thinking, I had to consult with the official solutions.

object FibonacciModule {
  def fib(n: Int): Int = {
    def go(n: Int, curr: Int, next: Int): Int = {
      if (n <= 0) curr
      else go(n-1, next, curr+next)
    }
    go(n, 0, 1)
  }
  
  def main(arr: Array[String]): Unit = {
    fib(5)
  }
}

At first I struggled to assign meaning to the functions fib and go. In my initial solution, the meaning was simple. fib(n) solves the problem (or answers the question) “What is the n-th value in the Fibonacci sequence? It is given that when n is 0, it is 0 and when n is 1 it is 1.” It seems like fib in the second solution also solves the same problem, but what does go solve for? One could make the argument that it does not “mean” anything, it is just a loop. I wasn’t personally satisfied with that understanding as it was still a recursive function that was answering some sort of question.

Things made a lot more sense once I wrote out the execution of go for a small n. I realized that the recursive function go answers the question “What is the n-th value in the Fibonacci sequence? It is given that when n is 0, it is curr and when n is 1, it is next.” For example, in the world of go(2, 2, 3) it is dealing with a sequence of 2, 3, 5, 8, .... So the value in the 2nd position (n=2) is 5.

go(5, 0, 1)
├ go(4, 1, 1)
│ ├ go(3, 1, 2)
│ │ ├ go(2, 2, 3)
│ │ │ ├ go(1, 3, 5)
│ │ │ │ └ go(0, 5, 8)
│ │ │ │   └ returns 5 since n <= 0
│ │ │ └ returns 5 
│ │ └ returns 5 
│ └ returns 5 
└ returns 5 

The reason why I was so confused was because a recursive function in the non-FP sense handles both communicating that this function will solve for the problem and will actually solve the problem. However, with this way of writing it, fib is communicating symantically that the function will solve for the problem and the function go will actually do the work to solve the problem. Indeed, when the second solution is run for some bigger n, it runs much faster than the first solution.

After this short detour of tail call elimination, the book introduces us to writing our first higher order function. The inital piece of code that was given to us was the following:

object MyModule {
  def abs(x: Int) = {...}

  private def formatAbs(x: Int) = {
    val msg = "The absolute value of %d is %d."
    msg.format(x, abs(x))
  }

  def main(args: Array[String]): Unit = {
    println(formatAbs(-42))
  }
}

Now the task is to add a factorial function to MyModule. A intuitive simple solution would be to do as follows.

object MyModule {
  def abs(x: Int) = {...}

  def factorial(x: Int) = {...}

  private def formatAbs(x: Int) = {
    val msg = "The absolute value of %d is %d."
    msg.format(x, abs(x))
  }

  private def formatFactorial(n: Int) = {
    val msg = "The factorial of %d is %d."
    msg.format(n, factorial(n))
  }

  def main(args: Array[String]): Unit = {
    println(formatAbs(-42))
    println(formatFactorial(9))
  }
}

Taking a good look at the methods formatFactorial and formatAbs, it can be seen that there is a lot that is common between these 2 methods. Using the concept of “a function as a value”, this can be further simplified to the following.

object MyModule {
  def abs(x: Int) = {...}

  def factorial(x: Int) = {...}

  private def formatResult(name: String, x: Int, f: Int => Int) = {
    val msg = "The %s of %d is %d."
    msg.format(name, x, abs(x))
  }

  def main(args: Array[String]): Unit = {
    println("absolute value", -42, abs)
    println("factorial", 9, factorial)
  }
}

Taking a look at the signature of formatResult it can be seen that the parameter name for the function to be passed in is a short name f. This is common in FP because the HOF should be general to the point that they have no opinion on what the argument should ascually do. All they need to know is the type, which in this case is Int => Int, a function that expects an Int as an argument and returns an Int.

Overall, very interesting first day, and I look forward to reading more about FP in this book.

---

Notes

• Started reading this because Boris Cherny recommended it as the one book that “has had the greatest impact on him as an engineer”.
  • Here is the video that I watched.

Chapter 1

• Basically skipped it.
  • It seemed to be just an overview of what FP was, and as a result introduced a lot of concepts that went over my head.
  • So I skipped it because I thought that these concepts that went over my head will get re-introduced when I have actually built intuition for these concepts, helping me better understand things.
  • Plus I’ve heard that this book has a bunch of exercises and I just wanted to actually get started on coding FP stuff in Scala since I thought that would teach me more than just reading through concepts about it.
• There’s a high likelihood that I might come back to it later to actually read through this chapter.

Chapter 2

2.1 Introducing Scala the language: an example

• This chapter starts off by showing an example program for an object called MyModule.
  • In Scala, an object is also known as a “module”
  • Scala code has to be in an object or a class. The difference will be described later, but MyModule is declared as an object because it’s “simpler”.
  • The term method will be used to refer to some function or field defined within an object or class using the def keyword.
  • The object keyword creates a new singleton type, which is like a class that only has a single named instance. In Java, it would be a lot like creating a new instance of an anonymous class.
  • Since Scala does not have an equivalent to Java’s static keyword, an object is often used in Scala where you might use a class with static members in Java.
• Scala kind of just seems like a slightly different version of Java so far.
• The following abs method is a pure function.

  • def abs(n: Int): Int = 
      if (n < 0) -n
      else n
    

  • In the argument list, the type annotation is optional.
    • Interesting, so Scala is not strongly typed?
  • The body of the method itself comes after a single equal sign (=).
    • This is also interesting, when then, do you use curly braces ({})?
  • The part that goes before the equals sign is the left-hand side or signature and the code that comes after the equals sign is the right-hand side or definition.
  • There is also an absence of an explicit return keyword. The value returned from a method is simply whatever value results from evaluating the right-hand side.
• The formatAbs function is another pure function
  • What’s a “pure function”?
    • It’s probably explained in Chapter 1.

  • private def formatAbs(x: Int) = {
      val msg = "The absolute value of %d is %d."
      msg.format(x, abs(x))
    }
    

  • The format is a standard library method defined on String.
  • The declaration of private is the same where it just means that this function cannot be called from any code outside of the MyModule object.
  • Note the omission of the return type of this function.
    • Scala is usually able to infer the return types of methods, but it’s generally considered good style to explicitly declare the return types of methods that you expect others to use.
    • The decision to omit the type annotation was because this method is internal to the MyModule object, and as such we don’t expect “others” to use it.
  • Ah, so because this function has more than one statement, that’s why we use the curly braces.
    • A pair of braces containing statements is called a block.
    • Statements are separated by newlines or by semicolons. In this case, a newline is used to separate the statements, so a semicolon isn’t necessary.
  • A val is an immutable variable. This means that inside the body of the formatAbs method, the name msg will always refer to the same String value.
    • In fact, the Scala compiler will complain if you try to reassign msg to a different value in the same block.
  • Note again, that a method simply returns the value of its right-hand side, which in this case is a block.
    • In Scala, the value of a multistatement block inside curly braces is the same as the value returned by the last expression in the block.
    • So the result of this method is just the value returned by the call to msg.format(x, abs(x)).
• The main method is an outer shell that calls into the purely functional core and prints the answer to the console.

  • def main(args: Array[String]): Unit =
      println(formatAbs(-42))
    

  • The book will sometimes call such methods procedures (or impure functions) rather than functions, to emphasize the fact that they have side effects.
  • The name main is special because when you run a program, Scala will look for a method named main with a specific signature.
    • It has to take an Array of Strings as its arugment.
      • The args array will contain the arguments that were given at the command line that ran the program.
      • They are not being used here.
    • The main method’s return type must be Unit.
      • Unit serves a similar purpose to void in programming languages like C and Java.
      • In Scala, every method has to return some value as long as it doesn’t crash or hang, but main doesn’t return anything meaningful, hence the Unit type.
      • There’s only one value of this type and the literal syntax for it is (), a pair of empty parentheses, pronounced “unit” just like the type.
      • Usually, a return type of Unit is a hint that the method has a side effect.

2.2 Running our program

• This section just talks about running Scala programs in the terminal.
• It’s pretty much the same as Java.
  • Use scalac [modulename].scala to compile the scala source code into Java bytecode, then use scala [modulename] to actually run the code.
  • Again, like Java, you can actually skip the compilation step and run the code directly with scala [modulename].scala
• The command scala will open up a read-evaluate-print loop (REPL) so that you can just try stuff out as you go.
• Faced some weird issues with running the file directly with scala [modulename].scala.

  • error: Compile server encountered fatal condition: javax/tools/DiagnosticListener
    java.lang.ClassNotFoundException: javax.tools.DiagnosticListener
    ...
    

  • Was using Java 21.0.8 and going the compile -> run route (scalac [modulename].scala then scala [modulename]) worked.
  • I could also add the -nc flag, so doing scala -nc [modulename].scala would work, but I didn’t want to remember the flag itself.
  • All I had to do was upgrade my Scala version from 2.11.12 to 3.7.4, as apparently, the -nc flag behavior has been a default from 2.13.0 (source)

2.3 Modules, objects, and namespaces

• In the REPL session in section 2.2, in order to invoke the abs method, it was required to call it by MyModule.abs.
  • This is because abs was defined in the MyModule object and in this case, “MyModule” is its namespace.
• Every value in Scala is what’s called an object, and each object may have zero or more members.
  • An object whose primary purpose is giving its members a namespace is sometimes called a module.
  • A member can be a method declared with the def keyword, or it can be another object declared with val or object.
• Members of objects can be accessed with the typical object-oriented dot notation.
  • This is the namespace (the name that refers to the object) followed by a dot (the period character), followed by the name of the member.
    • e.g. MyModule.abs(-42)
    • As another example, the toString member on the object 42 can be used by doing 42.toString.
  • The implementations of members within an object can refer to each other unqualified, but if needed they have access to their enclosing object using a special name: this.
    • “Unqualified” means without prefixing the object name.
  • Note that even an expression like “2+1” is just calling a member of an object.
    • In this case, this is just really syntactic sugar for the expression 2.+(1).
    • The “+” is a method on the object “2”, and it is passing in “1” as the argument to that method.
    • Scala has no special notion of operators, so it’s simply the case that “+” is a valid method name in Scala.
  • In fact, any method name can be used infix (omitting the dot and parentheses) like “+” when calling it with a single argument.
    • For example, MyModule.abs(42) is equivalent to MyModule abs 42.
• An object’s member can be brought into scope by importing it.
  • e.g. import MyModule.abs
  • All of an object’s non-private members can be brought into scope by using the underscore syntax: import MyModule._.

2.4 Higher-order functions: passing functions to functions

• The first new idea for the basics of functional programs is that functions are values.
  • Therefore, just like values of other types - such as integers, strings, and lists - functions can be assigned to variables, stored in data structures, and passed as arguments to functions.
  • Interesting, so this is probably why the methods are written as def [methodname](): [type] = [do something here] with an equal sign.
    • In this case, it’s really just hammering in the point that we are assigning this function to this variable called methodname.

2.4.1 A short detour: writing loops functionally

• The way that a loop is written functionally, without mutating a loop variable, is with a recursive function.
  • To write a loop with a recursive function just so that you don’t mutate the loop variable seems a little ridiculous to me.
  • But I’ll give it a try for the sake of learning how to think in the functional style.
  • I guess functional programming is really serious about not having any side effects whatsoever.

• def factorial(n: Int): Int = {
    def go(n: Int, acc: Int): Int =
      if (n <= 0) acc
      else go(n-1, n*acc)
  
    go(n, 1)
  }
  

  • In the function factorial there’s a recursive helper function inside the body for the “loop”. Such functions are called go or loop by convention.
  • In Scala, a function can be defined inside any block, including within another function definition.
  • Since this go function is local to factorial it can only be referred to from within the body of the factorial function, just like a local variable would.

• def go(n: Int, acc: Int): Int =
    if (n <= 0) acc
    else go(n-1, n*acc)
  

  • The arguments to go are the state for the loop, where n is the remaining value and acc is the current accumulated factorial.
    • The next iteration is just the recursive call go(n-1, n*acc).
    • The loop ends when a value without a recursive call is returned.
  • Scala will detect this self-recursion and compiles it to the same sort of bytecode as would be emitted for a while loop, so as long as the recursive call is in tail position.
    • The basic idea is that tail call elimination is applied when there’s no additional work left to do after the recursive call returns.
• A call is said to be in tail position if the caller does nothing other than return the value of the recursive call.
  • For example, in the function go above, the invocation go(n-1, n*acc) is in tail position, since the method go(n: Int, acc: Int) will return the value of this recursive call (go(n-1, n*acc)) directly and does nothing else with it.
  • However, if the line was instead 1 + go(n-1, n*acc) then go would no longer be in tail position, since the method would still have work (adding 1) when go returns its result.
• If all recursive calls made by a function are in tail position, Scala automatically compiles the recursion to iterative loops that don’t consume call stack frames for each iteration.
  • However, Scala will not inform if the tail call elimination by default.
    • The tailrec annotation (@annotation.tailrec) can be used to tell the Scala compiler that tail call elimination is expected for the recursive function that this annotation is placed on.

    • def factorial(n: Int): Int = {
        @annotation.tailrec
        def go(n: Int, acc: Int): Int =
          if (n <= 0) acc
          else go(n-1, n*acc)
      
        go(n, 1)
      }
      

Exercise 2.1

• Write a recursive function to get the n-th Fibonacci number.
  1. The first two Fibonacci numbers are 0 and 1.
     • e.g. The sequence should look like 0, 1, 1, 2, 3, 5, ....
  2. The definition should use a local tail-recursive function.
  3. def fib(n: Int): Int should be used as the function signature.

First Attempt

object FibonacciModule {
  // @annotation.tailrec adding this here will make this compile error
  def fib(n: Int): Int = {
    def go(n: Int) = 
      if (n <= 1) n
      else go(n - 1) + go(n - 2)
    
    go(n)
  }

  def main(args: Array[String]): Unit = {
    println(fib(5))
  }
}

• The first attempt was basically me just writing a recursive Fibonacci algorithm like how I would with any language.
• I basically just emulated the factorial function that was discussed in the previous section.
• Of course, this will give the correct values, but it’s not really a tail-recursive function. Which means that it’s just going to be super slow for higher values of n.

Second Attempt

object FibonacciModule {
  @annotation.tailrec
  def fib(n: Int): Int = {
    def go(n: Int, curr: Int, next: Int) =
      if (n <= 0) then curr
      else go(n-1, next, curr+next)
    go(n, 0, 1)
  }

  def main(args: Array[String]): Unit = {
    @annotation.tailrec
    def loop(curr: Int, n: Int): Unit = {
      if (curr <= n) {
        val num = fib(curr)
        println(s"$curr: $num")
        go(curr+1, n)
      }
    }

    loop(0, 10)
  }
}

• I am not afraid to admit that I referenced the solution code for this after thinking about it for a while.
• The biggest paradigm shift in this was what I realized that I was not thinking of the loop counter variable as just a “loop counter variable” but as also the “index of the Fibonacci number”.
  • In the first attempt, the value n decreases as we get closer to the leaves of the recursion tree.
  • Intuitively this makes sense because the function fib(n: Int) is answering the question “What is the n-th Fibonacci number?”.
  • In this first attempt, it is okay that n has both meanings since the fib function does both: does the actual computation and communicates to users that it will answer the question “What is the n-th Fibonacci number?”.
• However, in the functional fib, there is a separation of concern between the fib function and the go function.
  • The fib function still answers the question “What is the n-th Fibonacci number?”
  • But the go function will now do the actual computation.
  • So in this way, the n passed into fib holds semantically different meaning than the n passed into the go function.
• So what question does go actually answer?

  • go(5, 0, 1)
    ├ go(4, 1, 1)
    │ ├ go(3, 1, 2)
    │ │ ├ go(2, 2, 3)
    │ │ │ ├ go(1, 3, 5)
    │ │ │ │ └ go(0, 5, 8)
    │ │ │ │   └ returns 5 since n <= 0
    │ │ │ └ returns 5 
    │ │ └ returns 5 
    │ └ returns 5 
    └ returns 5 
    

  • Drawing the execution out really helped.
  • Okay, the question that it answers would be: “Given that the first value in the sequence is curr and the second value in the sequence is next, what is the n-th Fibonacci number?”
    • This then makes sense as to why go(2, 2, 3) is 5, because the sequence that we are working with is “2, 3, 5”.
      • The 0th value is 2, the 1st value is 3, and the 2nd value is 5.
• The loop function in main seems to be a lot closer to the traditional for-loop.
  • I don’t quite know if this is how you’re supposed to write these loops. Especially since I’m counting up, which seems to be not what you’d want to do in recursive statements.
  • But I also don’t know how I would be able to print out the index of the Fibonacci number and the value itself without having some sort of current counter value and the end value.
• The second attempt runs much faster than the first attempt. Tried it up to n=46.

2.4.2 Writing our first higher-order function

• Next the program that was written in 2.1 will be modified so that when given a number, it can print out both the absolute value of the number and the factorial of another number.
• Previously MyModule only had to deal with making a given integer into its absolute value. Now it needs to be modified so that it can also give out the factorial of that number.
• We have seen the formatAbs function, but now we have the formatFactorial function.

  • object MyModule {
      // Definitions of abs(...) and factorial(...) are made up here
    
      ... 
    
      private def formatAbs(x: Int) = {
        val msg = "The absolute value of %d is %d."
        msg.format(x, abs(x))
      }
    
      private def formatFactorial(n: Int) = {
        val msg = "The factorial of %d is %d."
        msg.format(n, factorial(n))
      }
    
      def main(args: Array[String]): Unit = {
        println(formatAbs(-42))
        println(formatFactorial(7))
      }
    }
    

  • Taking a look at the definitions of formatAbs(n: Int) and formatFactorial(n: Int), they are almost identical.
  • These functions can be further generalized into a single function formatResult which accepts as an argument the function to apply to its argument

    • def formatResult(name: String, n: Int, f: Int => Int) = {
        val msg = "The %s of %d is %d."
        msg.format(name, n, f(n))
      }
      

  • Now the code looks like the following

    • object MyModule {
        // Definitions of abs(...) and factorial(...) are made up here
      
        ... 
      
        def formatResult(name: String, n: Int, f: Int => Int) = {
          val msg = "The %s of %d is %d."
          msg.format(name, n, f(n))
        }
      
        def main(args: Array[String]): Unit = {
          println(formatResult("absolute value", -42, abs))
          println(formatResult("factorial", 7, factorial))
        }
      }
      

• It is very common in FP to see HOFs having very short names (e.g. f, g, h) for their parameter functions.
  • This is because HOFs are (and should) be so general that they have no opinion on what the argument should actually do.
    • Recall, in this case that the “argument” is a function, so they do stuff.
  • All that the HOF knows is about the argument and its type.