In Generating 2D random fractal terrains with C# I implemented 1D midpoint displacement in an imperative language. Since I’m currently making my way through Robert Pickering‘s Foundations of F#, in this post I want to redo it in F#.
The first step along the way is the maxDisplacements function that, given a number of splits of line segments, returns a list of maximum displacements. Here list comprehension comes in handy as a way to generate maximum displacements where the next is half of that of the previous, starting with 0.5:
let maxDisplacements n = [for i in 1 .. n -> 2.0**(float)(-i)]
Next is the composeCoordinates function whose job it is to infer the x coordinates from the y coordinates. When splitting line segments, as defined later by the split function, only y coordinates need to be dealt with. But for displaying the result as a list of points, e.g., as input to a graphing program, composeCoordinates generates the (x, y) coordinate pairs given a list of y coordinates. Again list comprehension is used to uniformly distribute the x coordinates in the range 0 to 1. Next, the x and y coordinates are fused using the build-in zip function, i.e., [x1; x2] and [y1; y2] become [(x1, y1); (x2, y2)].
let composeCoordinates (ys : list<float>) =
let dx = 1.0 / (float)(ys.Length - 1)
let xs = [for x in 0 .. ys.Length - 1 -> (float)x * dx]
List.zip xs ys
Now for the crux of the fractal generation process: the split function. As is customary with functional languages, looping is done using recursion and split is no exception. Passing in a list of y coordinates, a maximum displacement as generated by maxDisplacements, and a random number generator, split is defined as:
let rec split (ys : list<float>) displacement (random : Random) =
match ys with
| a :: b :: tail ->
let m = b - a / 2.0
let r = random.NextDouble() * displacement
a :: a + m + r :: split (b :: tail) displacement random
| a -> a
Using pattern matching, an if-then-else construct on steroids, split examines its input of y coordinates to determine if the inductive or the base case of the recursive implementation needs to be invoked. The first pattern matches a list starting with elements a and b following by zero or more elements. In case this pattern matches, a new list is returned. It’s composed of the original a element, a new displaced element, the original b element, and split applied to the original list with its first element removed. Removing one element at a time, at some point only one element is left in the list in which case the base case is invoked. When this happens, all the original line segments have been split in two.
Finally, the main function ties together the previous ones. Given an initial line segment, the number of times to apply split to it, and a random number generator, the actual splitting is done using the build-in fold_left function. fold_left is an example of fun with folds and a function that is itself recursively defined to make looping implicit.
let main() =
let initial = [0.0; 0.0]
let splits = 8
let r = new Random()
let ys = List.fold_left (fun s d -> split s d r) initial (maxDisplacements splits)
print_any (composeCoordinates ys)
While initially hard to grog, the use of fold_left becomes clearer when applied to a list of integers to compute their product. Of the three arguments to fold_left the first is a function defined by a lambda expression (here the predefined multiplication operator is also applicable but less explicit). The second argument is the initial value of an accumulator. And finally, the third argument is the list to work on.
List.fold_left (fun x y -> x * y) 1 [1;2;3] List.fold_left (*) 1 [1;2;3]
What fold_left does is recursively call itself passing along the first argument as is. The second argument is the new value of the accumulator, computed by passing to the function of the first argument the original value of the accumulator and the first element of the list. That way it’s up to the function passed as the first argument to decide what operation to apply to the elements in the list. The third argument is the original list with the first element removed. The recursive chain of calls with their arguments then takes on this form:
List.fold_left (fun 1 1 -> 1 * 1) 1 [1;2;3] List.fold_left (fun 1 2 -> 1 * 2) 1 [2;3] List.fold_left (fun 2 3 -> 2 * 3) 2 [3]
Within the main function the first argument to fold_left is a lambda expression that applies the split function to a list. The second argument, the accumulator, isn’t a scalar like with the product example, but a list of line segments to be passed to split. Finally, the third argument is the maximum displacement list. And so for the original line segment to be split n times, n maximum displacements must be provided by the maxDisplacements function.