programming, .NET, linux and others

Conway sequence in haskell

by Gregor Uhlenheuer on November 15, 2012

Inspired by a F# snippet on fssnip.net that generated a Conway sequence look-and-say sequence I chose to implement the same using haskell.

The Conway sequence is built by reading the input string/sequence from left to right and returning the number of repeated consecutive elements. Eg. 1211 is converted to 111221 which in turn is processed into 312211.

My pretty straight forward approach looks like the following:

module Conway (getConway) where

import Data.List (unfoldr)

-- | 'getConway' generates an inifinite Conway look-and-say sequence
-- (sequence A006715 in OEIS). See
-- http://en.wikipedia.org/wiki/Look-and-say_sequence
-- A simple use of 'getConway':
-- > (take 3 $ getConway "abc") == ["abc","1a1b1c","111a111b111c"]
getConway :: String -> [String]
getConway input =
    unfoldr (\seed -> Just(seed, getNext seed)) input
        grp x (Just l, c, lst) =
            if x == l then (Just l, (c+1), lst)
            else           (Just x, 1, (show c) ++ (l : lst))
        grp x (Nothing, _, _) = (Just x, 1, [])

        appendLast (a, b, c) =
            case a of
                Just chr  -> (show b) ++ chr : c
                otherwise -> c

        getNext = appendLast . foldr grp (Nothing, 0, [])

This post is tagged with haskell, programming and math