Often when writing a function, we want it to be generic enough that it can operate in different ways for different inputs. Different languages will provide different ways to do this. Object-oriented solutions might include interfaces and polymorphism. Procedural languages might suggest template specialization or function pointers.
I’m going to talk about how functional programming languages use first-class functions to solve this problem in a satisfying way without any pointer syntax. Here’s some F#:
let rec filter fn lst =
match lst with
| [] -> []
| head::tail ->
if fn head then [head] @ filter fn tail
else filter fn tailWe’re defining a function named filter here which takes a boolean function and a list. The filter function will pass each element of the list to the function and eventually return a list of the elements for which the boolean function returns true. Let’s look at the result of passing some simple arguments.
let numbers = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
let isEven i =
i % 2 = 0
filter isEven numbers
[0; 2; 4; 6; 8]Usually when we see functions in the argument lists of other functions, we expect them to be glorified values. But in this case, isEven is not returning some value that gets glued to a parameter of filter. When a language has first-class functions, it’s perfectly fine to have functions themselves be the inputs or outputs of other functions. Here, isEven is itself an argument, and it operates on the head of each sub-list as we recursively cut our list down to one with zero elements.
In functional programming languages, it’s harder to write programs that aren’t reusable. If we want our filter to cut out any numbers that aren’t part of the Fibonacci sequence, we just write another boolean function and pass it instead.
let rec isFibHelper n x y =
if n = x then true
else if (y < 0) || (x > n) then false
else isFibHelper n y (x+y)
let isFib n =
if n < 0 then false
else isFibHelper n 0 1
filter isFib numbers
[0; 1; 2; 3; 5; 8]
filter isFib (filter isEven numbers)
[0; 2; 8]Because filter operates on a list, to filter a list of some other type we can just steal some documentation code for another boolean function.
let strings = ["abc"; "DEF"; "gHi"; "jkl"]
open System
let allLower s =
s |> String.forall Char.IsLower
filter allLower strings
["abc"; "jkl"]Functional programming is all about composition and modularity. You start with tiny Lego pieces and need to attach them until you have a gigantic ninja castle. In its most dogmatic form, that means sacrificing creature comforts like loops and mutable data that we use to quickly slap together solutions that can never be reused.
If you learned to write procedures or call constructors, I recommend giving one of these languages a try. It even makes recursion fun, so what’s not to like?
From the blog CS@Worcester – Tasteful Glues by tastefulglues and used with permission of the author. All other rights reserved by the author.
