We’ve previously explored how to run Nix code, and basic Nix features: variables, conditions, “print/debug” “statement”, etc. But, we still haven’t saw anything analogue to loops, providing us with iteration. This, will be our subject for today, and will allow us to start writing something more substantial than a hello world.

I assume little to no experience in functional programming from the reader; I however assume familiarity with programming.

Note: I won’t bother with performances in general in this series: the focus is on correctness (well, hopefully…), and on developing an understanding of functional programming. But why can’t I still care about performances, and why do people often treat them as second-class citizens? I think there are two main reasons. In tutorials, focusing on performances adds noise, thus making the transmission of core concepts more difficult. Furthermore, in real life, they are to be treated cautiously:

optimizations have a cost: they can make the code more subtle, more complex, more difficult to write and maintain;
intuition can be wrong: you may think some function is slow and spend considerable time fixing it, but proper instrumentation/measurements may reveal unexpected bottlenecks.

Systematically improving performances locally, without proper instrumentation, is a great way to degrade the quality of a codebase.

Parenthesis aside, the code for this series is available on github.

Noon. Neighborhood of Moscow. oil on canvas (?) by Ivan Ivanovich Shishkin (Ива́н Ива́нович Ши́шкин, 1832-1898) through culture.ru gurneyjourney.blogspot.com – Public domain

Recursion

To iterate is human, to recurse divine. – L. Peter Deutsch

Functional programming favors the use of recursion over iteration, itself favored by imperative languages. Both approaches are theoretically equivalent, which means, all that can be expressed through recursion, can also be expressed iteratively, and reciprocally.

For most people, recursion is less intuitive than iteration; it seems that iteration is more natural, perhaps because it’s closer to everyday perception. There are exceptions though: some people are strangely fit for recursion.

We’ve saw before how to define basic functions:

#!/bin/nix-instantiate
let
	hw = w: "hello "+w;
in
	hw "reader"

"hello reader"

Defining and using recursive functions requires no more syntax than what precedes (e.g. no need for special keywords). Hopefully, you’re familiar with the factorial function:

#!/usr/bin/env -S nix-instantiate --eval
let
	fact = n: if n == 0 then 1 else n*fact(n - 1);
in
	fact 5

Exercise: Implement the Fibonacci sequence, mathematically defined as:

\[\begin{aligned} \phi(0) &&=\quad& 0 \\ \phi(1) &&=\quad& 1 \\ \phi(n\geq2) &&=\quad& \phi(n-1)+\phi(n-2) \\ \end{aligned}\]

Solution:[+]

Exercise: What happens when you compute (fact (fact 5))? How could you (theoretically) solve the issue?

Solution:[+]

Exercise: Implement a pair of mutually recursive functions odd and even, both taking an integer as input, and returning a boolean such that:

odd returns true when the number is odd, false otherwise;
and well, even returns true when the number is even, false otherwise.

Tip:[+]

Solution:[+]

Exercise: Implement the Ackermann–Péter function, mathematically defined as:

\[\begin{aligned} A(0,n) &&=\quad& n+1 \\ A(m+1,0) &&=\quad& A(m,1) \\ A(m+1,n+1) &&=\quad& A(m,A(m+1,n)) \\ \end{aligned}\]

Solution:[+]

Exercise: Try to display the computation of (ack 5 5). What is happening? Why were there no issues in the previous example?

Solution:[+]

Exercise: You may have heard of the “FizzBuzz”:

After a fair bit of trial and error I’ve discovered that people who struggle to code don’t just struggle on big problems, or even smallish problems (i.e. write an implementation of a linked list). They struggle with tiny problems.

So I set out to develop questions that can identify this kind of developer and came up with a class of questions I call “FizzBuzz Questions” named after a game children often play (or are made to play) in schools in the UK. An example of a Fizz-Buzz question is the following:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Most good programmers should be able to write out on paper a program which does this in under a couple of minutes. Want to know something scary? The majority of comp sci graduates can’t. I’ve also seen self-proclaimed senior programmers take more than 10-15 minutes to write a solution.

Implement such a FizzBuzz program.

Tip:[+]

Solution:[+]

The Forest Clearing, 1896, oil on canvas (119×171cm) by Ivan Ivanovich Shishkin (Ива́н Ива́нович Ши́шкин, 1832-1898) through wikimedia.org – Public domain

Partial application/currying

Consider again the Ackermann–Péter function. What do you think (ack 0) is? Well, let’s try it out. Let’s try to “print” it using toString:

#!/usr/bin/env -S nix-instantiate --eval
with builtins;
let
	ack = m: n:
		if m == 0 then
			n + 1
		else if n == 0 then
			ack (m - 1) 1
		else
			ack (m - 1) (ack m (n - 1))
	;
	a = (ack 0 1);
	b = (ack 0);
	c = (b 1);
in
	"(ack 0)=${toString b}; ((ack 0) 1)=${toString c};"
	+"(ack 0 1)=${toString a}"

error:
       … while calling the 'toString' builtin
         at ./nix/rec/ack-curry.nix:16:13:
           15| in
           16|       "(ack 0)=${toString b}; ((ack 0) 1)=${toString c};"
             |             ^
           17|         +"(ack 0 1)=${toString a}"

       … while evaluating the first argument passed to builtins.toString

       error: cannot coerce a function to a string: «lambda ack @ ./nix/rec/ack-curry.nix:4:11»

Well, it failed. But it nevertheless answered our question: (ack 0) is a function.

Exercise: There’s a typeOf e function in the builtins package, which returns a string corresponding of the expression e. Try to use it instead of relying on an error message to check that (ack 0) indeed is a function.

Tip:[+]

Solution:[+]

But which function is (ack 0) exactly? Well, it’s the function which takes an integer n as argument, and returns ack 0 n. This technique is commonly referred to as partial application: the function ack requires two arguments to be completely applied, but only one is provided, so the function is said to have been partially applied.

The process is often called “currying”: while both terms are often used interchangeably, strictly speaking they aren’t equivalent (you may want to refer to the related Wikipedia page for more).

We’ll soon see more example of partial application/currying, in this article and in this series. As a curiosity, I’ll leave you with the following archetypal example: you don’t need understand it to proceed further:

#!/usr/bin/env -S nix-instantiate --eval
with builtins;
let
	apply = f: l: foldl' (x: y: x y) f l;
	concat = x: y: z: (x + y + z);
in
	apply concat ["hello" " " "world"]

"hello world"

Note: builtins.foldl' is an, efficient, strict implementation of foldl on Nix’s lists. I’ll progressively explain that previous sentence in detail in this series, starting with foldl.

`fold`: a first encounter

In functional programming, there are a few famous functions, and fold (you may also find it sometimes called reduce) must be one of the most prominent first class citizen (pun intended). It’s generally used on lists, and we’ll soon study it in such a context in a later article, but we can find ways to make it work on some sequences of integers.

From now on, forget everything you know about Nix’s lists and lists in general. Consider the following warm-up exercise:

Exercise: Write a program sum which takes an integer as input, and returns the sum of integers from 1 to \(n\), or:

\[\begin{aligned} (\text{sum}\ n) = \sum_{i=1}^n i = 1 + 2 + ... + n \end{aligned}\]

Bonus: Can you find a way to write that program without using recursion (or loops, or any form of iteration)?

Tip:[+]

Solution:[+]

Exercise: Now let’s try to factorize sum and fact by introducing a new function, foldln f s n, where n is integer marking the end of our integer sequence. Try to understand what f and s represent, and implement foldln; use it to re-implement sum and fact to check your results.

Tip:[+]

Solution:[+]

There are a few noteworthy elements in that last exercise:

partial application: note that fact is built as a partial application of foldln, by comparison with sum. Obviously, this is arbitrary, and just to highlight how partial application can occur in practice.
Contrary to what I’ve been doing so far (except for the FizzBuzz exercise) I’ve used an auxiliary function, defined in the scope on the main function, which progressively fills an accumulator at every step of the iteration. This is a common pattern in functional programming. Note that we could have done without it. There are good reasons for using it though, but we won’t focus on them: I just think it’s useful to get familiar with the pattern. For the curious, you may find details in the following video:

Exercise: Write a program sumsquare n (via foldln, of course!) which takes an integer n as input, and returns the sum of the squares of integers from 1 to n:

\[\begin{aligned} (\text{sumsquare}\ n) = \sum_{i=1}^n i^2 = 1^2 + 2^2 + ... + n^2 \end{aligned}\]

Solution:[+]

Now let’s talk a little about why did we named this function foldln:

fold is the standard name for the pattern captured by that function;
the l stands for left: there’s a right variant:

\[\begin{aligned} (\text{foldrn}\ \phi\ s\ n) = (\phi\ 1\ (\phi\ 2\ (...\ (\phi\ n\ s)\ ...))) \end{aligned}\]

finally, the n stands for natural number (\(\mathbb{N}\)), as we’re working on a sequence of natural numbers.

Exercise: Implement foldrn; find an example where foldln and foldrn would give different output on the same input.

Solution:[+]

Exercise: Write the following programs:

sumfib n which sums the first n terms of the fibonacci sequence;
sumfact n, which sums the factorials of the integers from 1 to n;
sumr m n which sums the integers between m and n, included;
sumeven n and sumodd n, which respectively sums even and odd numbers between 1 and n.

Identify generic patterns underlying all those functions, that is, implement them using a handful of generic functions.

Tip:[+]

Solution:[+]

Note: Don’t hesitate to spend time toying with recursive functions, foldln & cie, until they become second nature. Recursivity in functional programming languages is as fundamental as while/for loops in imperative languages, so you want to make sure to understand it adequately. fold encompasses a key pattern to recursively go through structured data is also something definitely worth studying extensively.

We’ll revisit all of this in later articles anyway.

Bee families in the forest (Пасека в лесу, 1876), oil on canvas (?) by Ivan Ivanovich Shishkin (Ива́н Ива́нович Ши́шкин, 1832-1898) through wikiart.org – Public domain

Eratosthenes’ sieve

Finally, to conclude and progressively transition with the following article on closures, let me show you again the last example from the section on partial application/currying. Now that we’ve covered fold, even though only on some integer sequences, you may find it less cryptic:

#!/usr/bin/env -S nix-instantiate --eval
with builtins;
let
	apply = f: l: foldl' (x: y: x y) f l;
	concat = x: y: z: (x + y + z);
in
	apply concat ["hello" " " "world"]

"hello world"

The key idea is as follow: our accumulator is now a function, and we’re progressively building the final function by creating intermediate partial applications, until we’ve exhausted the list of arguments.

Exercise: Eratosthenes’ sieve computes prime numbers up to a certain fixed integer. Have a look at the Wikipedia page, and use it to implement a function sieve n which prints (trace) whether a given number is prime or not. Your implementation must rely on foldln & friends. Do not use lists or sets.

Tip:[+]

Solution:[+]

Note: In that last exercise, because of how sieve is implemented, it’s not very hard for us to perform computations via foldlnp such as computing the sum of the squares of all prime numbers between 0 and 100.

Exercise: You may want to give it a quick shot; there’s a subtle adjustment to perform for our previous version to work as expected.

Solution:[+]

It’s okay if you’re a bit befuddled by what’s happening here: we’re going to spend the next article studying this peculiar idea of closure in greater depth.

Evening (Вечер, 1871), oil on canvas (71×142cm) by Ivan Ivanovich Shishkin (Ива́н Ива́нович Ши́шкин, 1832-1898) through wikimedia.org – Public domain

In the series:

On Nix's language: Introduction (1/6)

On Nix's language: Recursive functions (2/6)

Comments

By email, at mathieu.bivert chez:

On Nix's Language: Recursive Functions

Table Of Contents

In the series:

Recursion

Partial application/currying

`fold`: a first encounter

Eratosthenes’ sieve

In the series:

Comments

Recursion

Partial application/currying

fold: a first encounter

Eratosthenes’ sieve

In the series:

Comments

`fold`: a first encounter