## Friday, 19 February 2010

### Morris sequences

The Morris sequence, also known as the "see and say" or "look and say" sequence, is a sequence of sequences of integers where each subsequent sequence is a run-length encoding of the previous sequence. In other words, a run of identical integers in the previous sequence is encoded as two new elements in the next sequence: a number of repetitions and the repeated element itself.

Tony Lee posed the construction of an elegant F# program to generate the Morris sequence as an interesting challenge on Stack Overflow. Our proposed solution is as follows:

```> let next (xs: ResizeArray<_>) =
let ys = ResizeArray()
let add n x =
if n > 0 then
ys.Add n
ys.Add x
let mutable n = 0
let mutable x = 0
for i=0 to xs.Count-1 do
let x' = xs.[i]
if x=x' then
n <- n + 1
else
add n x
n <- 1
x <- x'
add n x
ys;;
val next : ResizeArray<int> -> System.Collections.Generic.List<int>

> let morris =
Seq.unfold (fun xs -> Some((xs :> seq<int>), next xs)) (ResizeArray [1]);;
val morris : seq<seq<int>>

> morris;;
val it : seq<seq<int>> =
seq [seq [1]; seq [1; 1]; seq [2; 1]; seq [1; 2; 1; 1]; ...]```

This solution is orders of magnitude faster than the other presented on Stack Overflow at the time of writing. The style wraps a low-level imperative solution for generating each subsequence in a high-level purely functional sequence. However, our solution is not as lazy as the original and, consequently, computes more than necessary when only the start of a subsequence is required.

#### 1 comment:

Anonymous said...

Hello! nice blog!