Look and say sequence (OCaml)
From LiteratePrograms
- Other implementations: C++ | dc | Eiffel | Haskell | J | Java | Lua | OCaml | Perl | PHP | Python | Ruby | Scala | sed | sh
This program is a code dump.
Code dumps are articles with little or no documentation or rearrangement of code. Please help to turn it into a literate program. Also make sure that the source of this code does consent to release it under the MIT or public domain license.
This is a simple OCaml program to generate look-and-say sequences such as the Conway sequence.
<<look_and_say_sequence.ml>>= (* computes the number of "v" items at the beginning of "xs" returns a pair of that number with the remainder of xs *) let count_span_eq v xs = let rec aux count = function x::xs when x = v -> aux (count+1) xs | xs -> count, xs in aux 0 xs (* does one iteration of look-and-say, i.e. "says" its argument *) let rec say_it = function [] -> [] | x::xs -> let c, zs = count_span_eq x xs in c+1 :: x :: say_it zs (* returns a list of "n" iterations of look-and-say *) let rec say_it_all s = function 0 -> [] | n -> s :: say_it_all (say_it s) (n-1)
Example:
# say_it_all [3] 10;; - : int list list = [[3]; [1; 3]; [1; 1; 1; 3]; [3; 1; 1; 3]; [1; 3; 2; 1; 1; 3]; [1; 1; 1; 3; 1; 2; 2; 1; 1; 3]; [3; 1; 1; 3; 1; 1; 2; 2; 2; 1; 1; 3]; [1; 3; 2; 1; 1; 3; 2; 1; 3; 2; 2; 1; 1; 3]; [1; 1; 1; 3; 1; 2; 2; 1; 1; 3; 1; 2; 1; 1; 1; 3; 2; 2; 2; 1; 1; 3]; [3; 1; 1; 3; 1; 1; 2; 2; 2; 1; 1; 3; 1; 1; 1; 2; 3; 1; 1; 3; 3; 2; 2; 1; 1; 3]]
| Download code |