For many types of problems, two or more for-loops are nested to iterate over multiple dimensions. In this article, we look at how to do this recursively in F#.

As before, examples are kept simple by design. A solution using imperative programming is also included for reference.

1. Article example: point2D and rectangle

1.1 Types

These types are intended as a simple 2D extension of what was shown in my previous article: Recursion 1.

type point2D = P of int * int
type rectangle = R of int * int
// (width, height)

1.2 Example task

We want to write a function points of type rectangle -> Set<point2D> that finds the set of points in a rectangle, including points on the edges.

I.e. points with a rectangle of width \(2\) and height \(1\) has the result:

$$\{ (0,0); (0, 1); (1, 0); (1, 1); (2, 0); (2, 1) \}$$

2. Iterative solution

In F#, the easiest way to compute this set is most likely to use set comprehension. Here is this solution in F# code:

let points_2D (R(width, height)) =
    set [ for x in 0..width do
          for y in 0..height -> P(x, y) ]

Using this function produces the expected result. In F# Interactive:

points_2D (R (2, 1))
// val it: Set<point2D> =
//   set [P (0, 0); P (0, 1); P (1, 0); P (1, 1); P (2, 0); P (2, 1)]

3. Recursion problems and challenges

For reasons that we will cover, this task is hard to build a nice recursive solution for. Even for otherwise seasoned programmers who are new to F#.

3.1 Initial attempts at 2D recursion

Consider the following proposal for a recursive points function. I wrote this to resemble a possible first attempt at solving the task recursively:

let points_2D_rec (R(width, height)) =
    let rec widthAxis y =
        let rec heightAxis x =
            function
            | 0 -> Set.singleton (P (x, 0))
            | y -> Set.add (P (x, y)) (heightAxis x (y-1))
        function
        | 0 -> heightAxis 0 y
        | x -> Set.union (heightAxis y x) (widthAxis x (y-1))
    widthAxis width height

I had been deliberately trying to nest the inner functions as if they were for-loops. The example above was in fact my third attempt at this. Below is my actual first attempt:

let rec points_2D_rec2 =
    let rec column x =
        function
        | 0 -> Set.singleton (P (x, 0))
        | y -> Set.add (P (x, y)) (column x (y-1))
    function
    | R (0, y) -> column 0 y
    | R (x, y) -> Set.union (column x y) (points_2D_rec2 (R ((x-1), y)))

This attempt even throws an obscure warning when compiled.

3.2 Problems and challenges

There are multiple problems with these nested solutions that make them hard to work with.

  1. The components and variables of these two proposals seem to be all over the place.
  2. The main expression of the outer function, which is the one to nest the inner function, is away from its declaration. This problem deteriorates further if more dimensions are needed.
  3. It is somewhat difficult to make out ways to re-arrange these functions to solve related problems. I.e. to change the order or extent of traversal in each dimension.
  4. The outer function deals with the variable for the inner function unnecessarily.

3.3 Moving forward

All of this is to say that it is possible to deal with points in a way that makes the code easier to build, understand, and change.

  1. The components and structure within the function should clearly reflect a sound breakdown of the problem. This includes naming in terms of the problem domain to reflect this.
  2. Each recursive function introduces its own variable(s).
  3. Where the inner function needs variable(s) of the outer function(s), function currying is applied.

4. Non-tail recursive solution

Following these principles for moving forward with poly-dimensional recursive problems, here is a proposed solution:

let points_2D_rec3 (R(width, height)) =
    // A single column of points. 
    let rec column x = 
        function
        | 0 -> Set.singleton (P (x, 0))
        | y -> Set.add (P (x, y)) (column x (y-1))
    
    // Columns of points form a plane of points. 
    let rec plane = 
        function
        | 0 -> column 0 height
        | x -> Set.union (column x height) (plane (x-1))
    
    // Value of points_2D_rec3. 
    plane width
  • It is now far more clear how the problem has been deconstructed.
    • The first function deals with the set of points in a single column.
    • The second combines multiple columns to form the set of points in the plane of the rectangle.
  • It is now far more clear how to change or extend the function.
    • Each dimension of the problem can be dealt with on its own. I.e. to change where to start, end, and which direction to go in.
    • Problems with more dimensions, i.e. building points_3D, take more inner functions as required. Extend downwards instead of inwards.
    • This is a not a tail recursive solution. To add tail recursion, redesign each inner function around using an accumulator.

5. Exercises

Using what can be gathered from the previous article on recursion and on the type system, as well as other good resources on F#, I propose the following tasks as exercises to further develop your F# proficiency:

  1. Build points_3D dealing with the types point3D and box.
  2. Create a tail recursive version of points_2D using accumulators. Afterwards, try the same with continuation functions.
  3. Create a function called points_2D_fold which applies a folder-function to each point. Use this to build a function which returns the set of points in the normal way.
  4. Add an offset to points_2D by which all the points are to be shifted. This is akin to the rectangle being located elsewhere in the 2D plane.