In functional programming, functions are first class values. It means that functions can be returned as values, and one can pass functions as arguments. In this chapter, we will start with recursive functions and gradually move to higher order functions, functions that take other functions as arguments. Our goal is to be able to write functions that are correct and tested. Haskell is a lazy language. We can take advantage of this fact, and write interesting and compact functions to take advantage of its laziness.

We will start with recursive functions, and see how recursion works. We will then move to tail recursive functions. We will explore a useful worker pattern while working with tail recursion. Next we will take advantage of laziness while calculating Fibonacci numbers recursively.

We will then work with maps and filters, which are very useful in many situations...

In this recipe, we will calculate fibonacci numbers by writing a simple recursive function. Fibonacci numbers are the numbers appearing in the fibonacci sequence.

Fibonacci numbers are calculated as follows:

F_n = F_n-1 + F_n-2

We need to provide the first two seed fibonacci numbers in the sequence so that we can calculate the next set of fibonacci numbers. We will seed the sequence with 0 and 1. Our sequence will look like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ....

We will start indexing with 0. Hence, the 0^th fibonacci number is 0, 1^st fibonacci number is 1, .. 5^th fibonacci number is 5 ... and so on.

Create a new project, fibonacci, using stack with the simple template...

In the previous recipe, we saw implementation using a simple recursive definition. In this recipe, we will use a commonly found recursive function implementation pattern called worker pattern.

The list does not have random access. We have to access elements of a list sequentially to be able to do something with it. When reversing a list, we need to remember this fact.

Create a new project, reverse, using Stack and the simple template. Also, build the project:

      stack new reverse simple
      stack build

In this recipe, we will continue working with recursive functions. In addition to recursion, we will introduce higher order functions. Higher order functions are functions that take other functions as an argument. Higher order functions introduce a layer of abstraction over other functions. If you see a certain pattern repeated over and over again, then you might have hit a situation that can be abstracted as a higher order function.

Though provided by default by Haskell's Prelude module, we will write our own version of two important higher order functions, map and filter.

Using stack, create a new project, map-filter, using the simple template. Change to the project folder and...

So far, we have seen a simple recursion; recursion using worker pattern. Haskell adds laziness to the mix. We can use laziness to our advantage while working with recursion.

In this recipe, we will again calculate the fibonacci number. However, this time, we will do it with infinite lists. By taking advantage of Haskell's laziness to evaluate an expression only when it is required, we can really create a linear time algorithm (O(n)) for the fibonacci number.

Create a new project, fibonacci-infinite, by running Stack. Change into the project directory and build it using Stack:

      stack new fibonacci-infinite simple
      stack build

In this recipe, we will look at two of the most important high-order functions, called foldr and foldl. These functions carry out the following activities:

• Abstract iterative process over a collection such as a list
• Give a way to work with each of the elements within the collection
• Give a way to summarize elements and combine them with user-supplied values

Depending on the way elements are combined, the functions are called foldr (fold right) or foldl (fold left). Many higher order functions such as map or filter can be expressed in terms of foldr or foldl.

In this recipe, we will write sum and product functions to calculate the sum and product of numbers in the input list respectively. We will also use folds to implement map and filter.

In this recipe, we will write a pseudo-quick sort using recursion. We call it pseudo-quick sort because it looks deceptively such as quick sort, but does not have a performance anywhere near it.

Use Stack to create a new project, pseudo-qsort, with the simple template and build it, after changing directory to the project folder:

      > stack new pseudo-qsort simple
      > stack build

1. Open src/Main.hs and write the qsort implementation. The qsort involves the following:
   • Choosing an element of the list to be sorted
   • Using...

In this recipe, we will implement merge sort. The merge sort that we are implementing is bottoms-up merge sort. In bottoms-up merge sort, we start by sorting pairs of elements in the list. Then, gradually, we start merging them in pairs, until we have only one left.

Use Stack to create a new project, merge-sort, with the simple template and build it, after changing the directory to the project folder:

      > stack new merge-sort simple
      > stack build

1. Open src/Main.hs; we will implement merge sort here...

In this recipe, we will look at a prime number calculator called Eratosthenes Sieve. It is an old algorithm for finding prime numbers. The prime numbers are found by crossing out composite numbers. The sieve works as follows:

1. Start with 2, a known prime. Strike out all the numbers that are multiples of 2.
2. Start with the next unmarked number, which will be the next prime (since it is not divided by any prime before). Repeat the procedure of marking all the multiples.
3. Repeat the procedure.

For more information, visit https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

Create a new project, eratosthenes, using the simple Stack template. Change into the project directory and build...