First Class Functions :1 Fold, Map, Iter

Note: I am primarily presenting these 3 articles in F#. The main reason for this is that I am being asked about F# a great deal lately. The same principles of higher order functions will apply to other languages (like OCaml and Haskell). Also, the #light directive is used on all of the following code. You can use this yourself by placing #light at the top of your code files, or type #light into the interactive shell before entering any code. This indicates to the compiler that the code should be parsed by indentation (and thus whitespace should not be ignored) :End Note

Last time we transformed an imperative program into its functional counterpart. In the process we found some patterns we were able to extract to maximize the generality of our approach. Namely, higher order functions like the combinator fold were found to be valuable. In this post, we will take a look at three combinators – iter, map and fold – in order to gain a better understanding of their broad applicability. And it is broad. An entire tutorial could have been dedicated to the surprising capabilities of the fold combinator alone. Again, all of the F# code below can be plugged into an interactive session.

Iter

First let’s look at the iter combinator. It is very simple, it takes as arguments a function which takes an element and returns unit (unit being no meaningful result), and it takes the list/array/seq as its final argument.

Now let’s create something with iter. I will create a simple windows form, and include a list on it. We will use a List type for this, but thanks to the inclusion of iter in libraries with Arrays and Seq types we could have used those as well. That opens up possibilities like applying it to recordsets, files and a number of other .Net objects easily.

#light
open System.Windows.Forms

// Create the names list
let names = ["Arthur Dent";"Ford Prefect";"Slartibartfast"]

// The list control
let listControl =
  // Create the ListBox()
  let dlist = new ListBox()
  // Iterate through the names list, adding each one to the box using "iter"
  List.iter (fun n -> ignore (dlist.Items.Add(n)) ) names
  // return the list box  (which will bind it as the value of listControl
  dlist

// Create a form, add the list box control, set the location and show the form

let form = new Form(Text = "List Manipulation",Height=400,Width=400)
let namebox = listControl
form.Controls.Add(namebox)
namebox.Location <- new System.Drawing.Point(10,10)

// For interactive session
do form.Show()

Our form above first opens the Windows.Forms namespace. It then creates a list called names. It declares the listControl which iterates over the names list. The form value creates the form with its controls and then the Show method is called. The focus here is on the List.iter call in listControl. The first argument is a function (an anonymous function created with the fun notation – also sometimes called a lambda expression). The anonymous function takes an argument and adds it to the list control. The result of the Add call is passed to ignore, which takes any type and returns unit. This is done because our lambda expression has to return unit (but ListBox.Items.Add actually returns something). The final argument is the names list.There is also a version of iter which will include the index of the element it is acting on called iteri. We will not dive into this, but we will be using this type of function when we create something with map.

Map

map is similar to iter in that it takes a function and applies it to every element of a list/array/seq. However map is expected to return something meaningful. It is expected to return a value that replaces the current element in the new list, which map returns. As a quick example, if I had an array of integers and wanted to increase each element of the array by one I could write

> Array.map ((+) 1) [|1;2;3|]

In F# interactive mode the following would be returned

 val it : int array = [|2; 3; 4|]

Let’s use our new found combinator to add something to our form. In this case I will use the mapi combinator (the modified map which accepts an integer representing the location the current element is in the list). I will use map to enumerate each of the names, and then write that to the list using iter. This represents a very powerful aspect of these combinators, using them in combination! The full listing now with map is below. The call to map is now the second let expression in the listControl function. Like iter, it uses an anonymous function and then passes the names list to it. The resulting list (enumlist) is then used in the call to iter.

#light
open System.Windows.Forms

// Create the names list
let names = ["Arthur Dent";"Ford Prefect";"Slartibartfast"]

// The list control
let listControl =
  // Create the ListBox()
  let dlist = new ListBox()
  // map the list into an enumerated list
  let enumlist = List.mapi (fun i n -> i.ToString() + ": " + n) names
  // Iterate through the names list, adding each one to the box using "iter"
  List.iter (fun n -> ignore (dlist.Items.Add(n)) ) enumlist
  // return the list box  (which will bind it as the value of listControl
  dlist

// Create a form, add the list box control, set the location and show the form

let form = new Form(Text = "List Manipulation",Height=400,Width=400)
let namebox = listControl
form.Controls.Add(namebox)
namebox.Location <- new System.Drawing.Point(10,10)

// For interactive Session
do form.Show()

Fold

Fold has a number of implementations, but before getting into that let’s just introduce its basic purpose. Fold applies a function to each element of a list while keeping an accumulating argument. At the point the entire list has been traversed fold returns the accumulated argument. The simplest example I can imagine is summation.
Note, the function in this form doesn’t exist by default in F# … I will explain the F# version shortly.
This would return
To make it painfully simple, the reduction steps that you can imagine for the above calculation are …

Let’s look at an application of fold in a language (like F#). There are two directions from which you can fold a list. For example, fold_left folds the list starting with the left most element and fold_right folds the list starting from the right most element. This would matter if the computation you were using did not commute (unlike + which we will use in most of our examples for simplicity).

Let’s see what it looks like to calculate the mean of an integer list using fold_left.

let mean () =
     let eventspace = [for i in 10 .. 10 .. 100 -> i *i]
     let sum = List.fold_left (+) 0 eventspace
     let size  = float (List.length eventspace)
     (float sum) / size

Now, let’s get back to our form example. We created a list, we enumerated everyone’s name with mapi and then we used iter to write the names to the list. Now let’s compute something for fold. As an example, we will grab the longest name and write it to a label.

#light

open System.Windows.Forms

open System.Drawing

let names = ["Arthur Dent"; "Ford Prefect"; "Slartibartfast"]

let listControl =
  let dlist = new ListBox()
  let enumlist = List.mapi (fun i n -> i.ToString() + ": " + n) names
  List.iter (fun n-> ignore (dlist.Items.Add(n))) enumlist
  dlist

let form = new Form(Text = "List Manipulation",Height=400,Width=400)
let label = new Label()
label.Text <- "The longest name is: " +
  (names |>
   List.fold1_left (fun name cand -> if(name.Length>cand.Length) then name else cand))
label.Width <- 200
label.Location <- new Point(150,20)
form.Controls.Add(label)
form.Controls.Add(listControl)
listControl.Location <- new System.Drawing.Point(10,10)

// Note: For interactive Session
form.Show()

The code added to the form function creates the label. Then the label’s Text attribute is populated with a string and the result of the fold function. Again an anonymous function is used which checks the length of two strings and returns the longest one.The final form looks like:

While this only a very basic introduction, hopefully you will be able to use higher order functions in basic processing tasks at this point. If your experience is anything like mine,
in time you will be using them to compose very powerful abstractions of your programs. At an advanced level they even allow you to create APIs that look more like little languages than a series of method calls. I frequently use combinators in this way, as well as to parameterize the context of large computations. Next time I will address some simple approaches to concurrency using higher order functions.