When writing any non-trivial amount of code, we usually factor out the common logic or patterns to improve modularity, facilitate code reuse and avoid repeating ourselves. Recursion schemes is just about that. With recursion schemes you can factor out the recursion patterns in your code, so that you don’t need to write the same types of recursion over and over again. This may sound a little magical to those who aren’t familiar with recursion schemes, but it really isn’t.
This post contains some notes on chapter 5 (Strictness and laziness) of the Functional Programming in Scala book (a.k.a The Red Book). The chapter covers the basics of non-strict and lazy evaluation in Scala, as well as an implementation of
Stream, a lazy version of
Fixed-point combinator is a really cool thing. It allows us to encode recursion in lambda calculus, which doesn’t have built-in support for recursion. Computerphile recently made a video featuring professor Graham Hutton, author of the book “Programming in Haskell”, giving a brief introduction to the Y combinator.
Trampoline is a way to make non-tail recursive functions stack-safe. Its Scala implementation is explained by Rúnar Bjarnason in his paper, Stackless Scala With Free Monads, and his book, Functional Programming in Scala. Rúnar’s (old) blog also has a post illustrating the idea. In this post I’d like to apply this technique on a few simple, concrete examples, and show step-by-step how it works on these examples and why it is able to make them stack-safe.
Arrow is a useful typeclass for modeling something that behave like functions, e.g,.
A => B,
A => M[B] (also known as
F[A] => B, etc. So useful, that Haskell provides a
proc notation for composing and combining
Arrows, similar as the
do notation for sequencing monadic operations. The
proc notation comes in really handy, since without it,
Arrows have to be used point-free, which impairs readability.
Scala is such a wonderful language, it’s impossible not to create a blog and share great things about it.