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!