Been a while since I played around in OCaml, so I think I might play around with sequences. They’re a feature I think I’d like, but never really had a good opportunity to cut my teeth on.
To whet the appetite for weird control flow, let’s talk about recursion and generators in Python.
If you don’t know, recursion is where a function includes a call to itself with different parameters, in order to calculate some end result. A common pattern with recursion is a base case and a recursive step. The idea is that the recursive step always moves towards the base case.
def factorial(n):
if n == 0:
# Base case.
return 1
else:
# Recursive step.
return n * factorial(n - 1)
# factorial(5) => 5 * factorial(4) => 5 * 4 * factorial(3) => ...
# 5 * 4 * 3 * 2 * 1 * 1 => 120
So if recursion starts at the top and works down, what happens if we start from the bottom and work up?
def factorial_inner(current, multiply, timer):
if timer == 0:
return current
else:
return factorial_inner(current * multiply, multiply + 1, timer - 1)
def factorial(n):
return factorial_inner(1, 1, n)
This is generative recursion: instead of starting from an original value and working down towards a known value, we start at a known value and append to it in a known way.
In this form it’s a bit wild, we could really use the help of generators.
Generators
Generators are great. Instead of writing a list, you write a function which can get the
next element in a list. Python allows this using the yield keyword, followed by making an
instance of the function:
def ones():
while True:
yield 1
one_maker = ones()
print(next(one_maker)) # 1
print(next(one_maker)) # 1
print(next(one_maker)) # 1
print(next(one_maker)) # 1
print(next(one_maker)) # 1
The function essentially “pauses” right after yield.
Using this, we can make an ✨ infinite ✨ stream of factorials:
def factorials(n=1):
acc = 1
while True:
yield acc
acc *= n
n += 1
Build an instance of this and every time you ask for a factorial, it will give you the next
one in the sequence. You can then use itertools to grab things from the sequence in a
specific way.
You don’t need to make infinite generators, they can be finite and will just drop off at the end. This is great for forcing an order of operations. You simply cannot do things out of order.
...
from itertools import islice
for val in islice(factorials(), 5):
print(val, end=' ')
# or
print([val for val in islice(factorials(), 5)], sep=', ')
# 1, 1, 2, 6, 24
But we’ve been working in the niche language of Python. Let’s gracelessly segue to something much more ubiquitous: OCaml.
Sequences in OCaml
Sequences are remarkably unweird. Generators are definitely weird: we put the execution of a function on ‘pause’, and then we can ‘resume’ it any time we want, and everything continues as if nothing happened? I can’t even make a best guess as to how it’s implemented.
Sequences are dead simple: if the sequence type was called T, T contains:
- a value, and
- a function which returns a
T
...which doesn’t sound dead simple, but it really is. Imagine a phone number and when you call it someone on the other end of the line gives you a piece of information, alongside another phone number, which gives you the next information when you call it (and another phone number, etc). This process repeats itself until you call someone and they say “Nah I don’t have anything for you”, and then your sequence is done.
We’ll name these options Cons and Nil, and define the type in OCaml:
type 'a node =
| Nil
| Cons of 'a * (unit -> 'a node)
OCaml actually defines sequences differently, where Cons is of 'a * 'a t and 'a t is defined as unit -> 'a node. Don’t ask me why.
Ok cool, let’s play around with it. To actually get the values out I’ll whip up a pair of functions for the head and tail of the list, and I’ll just fail if we run into Nil.
let hd = function
| Nil -> failwith "Headless"
| Cons (h, _) -> h
let tl = function
| Nil -> failwith "No tails?"
| Cons (_, t) -> t
and I’ll write a quick tester for this
let x = Cons (1, fun () -> Nil)
let y = Cons (1, fun () -> Cons (2, fun () -> Nil))
let () =
print_string "Testing... ";
assert (hd x = 1);
assert (tl y () |> hd = 2);
print_endline "yay!"
Testing... yay!
Hell yes.
That second assert is kinda fancy, could’ve just done assert (hd (tl y ()) = 2);.
Recursive generation
Writing out these sequences is a bit of a pain, and getting the elements isn’t great either. I think I’m going to write something to help extract elements, and then we can start building things.
let rec take n sequence = match n with
| 0 -> []
| _ -> match sequence with
| Nil -> []
| Cons (h, t) -> h :: take (n - 1) (t ())
Now I need something to extract. Let’s start with lots of 1s:
let rec ones = Cons (1, fun () -> ones)
let () =
print_string "Testing again... ";
assert (take 3 ones = [1; 1; 1]);
print_endline "yay!"
Testing again... yay!
Brilliant.
More things
More stdlib vibes:
let rec repeat1 value = Cons (value, fun () -> repeat1 value)
let rec repeat values = match values with
| [] -> Nil
| h :: t -> Cons (h, fun () -> repeat (t @ [h]))
let () =
print_string "Test 3... ";
assert (take 5 (repeat [1; 2; 3]) = [1; 2; 3; 1; 2]);
print_endline "yay!"
For repeat we are giving a value, then passing that same value into the back of the queue
for the next go-around.
Test 3... yay!
And it’d be nice to be able to merge sequences together, and manipulate them too:
let rec zipWith concat left right = match (left, right) with
| (Nil, _) | (_, Nil) -> Nil
| (Cons (h1, t1), Cons (h2, t2))
-> Cons ((concat h1 h2), fun () -> zipWith concat (t1 ()) (t2 ()))
let rec map f sequence = match sequence with
| Nil -> Nil
| Cons (h, t) -> Cons (f h, fun () -> map f (t ()))
...
assert (take 5 (zipwith
String.cat
(repeat ["a"; "b"; "c"])
(repeat ["x"; "y"])
) = ["ax"; "by"; "cx"; "ay"; "bx"]);
assert (take 3 (map
string_of_int
ones
) = ["1"; "1"; "1"]);
...
I’m sure you can just close your eyes and imagine the tests passing.
Something slightly funnier
I think we have all the bits and pieces we need to make something I saw while watching a Kevlin Henney talk.
let fizzes = repeat [""; ""; "fizz"]
let buzzes = repeat [""; ""; ""; ""; "buzz"]
let strings = zipWith String.cat fizzes buzzes
let counting =
let rec aux n = Cons (n, fun () -> aux (n + 1)) in
aux 1
let numbers = map string_of_int counting
let fizzbuzzes = zipWith max strings numbers
let () =
print_string "Crescendo... ";
assert (take 6 fizzbuzzes = ["1"; "2"; "fizz"; "4"; "buzz"; "fizz"]);
print_endline "you did it!"
Crescendo... you did it!
Excellent.
Sequences are a wonderful problem to think around
Being able to compose and deconstruct infinite lists is a real treat for the mind. Sometimes sequences and generators can feel like a solution looking for a problem, but creating an arbitrary amount of data can be pretty ergonomic.
Another use-case is when you don’t know how much you’ll need. I’ve had tasks in the past where I need to search through a massive amount of permutations until I find something “good enough”, where the number of permutations reaches into the teens-of-digits. Without a generator this would be an absolute nightmare to solve.
Regardless, I’d recommend giving one of these patterns a shot, they exist in so many popular programming languages and they can give a new perspective on solving problems.