Markov algorithms in Haskell

What follows are the basic definitions and the execution engine for Markov algorithms, written in Haskell. After the code I’ll show how to use it with some sample algorithms.

import Data.List

-- The parameters for a computational step
-- Each step is (theta, phi, b, a), following Knuth's notation
type StepParams = (String, String, Int, Int)

-- An algorithm is a sequence of steps
type Algorithm = [StepParams]

-- replace the first (leftmost) occurrence of string from with string to
replace :: Eq a => [a] -> [a] -> [a] -> [a]
replace []   to [] = to
replace _    _  [] = []
replace from to s@(c:cs)
    | isPrefixOf from s = to ++ (drop (length from) s)
    | otherwise = c : (replace from to cs)

-- The execution function
exec :: [StepParams] -> String -> String
exec ps input = execLoop (input, 0)
    where execLoop (word, step)
              | step == length ps = word
              | otherwise         = execLoop $ doStep (ps!!step) word
          doStep (theta, phi, b, a) word
              | isInfixOf theta word = (replace theta phi word, b)
              | otherwise            = (word, a)

Here are some algorithms. This calculates the absolute difference between numbers m and n, represented as strings with m ‘a’s and n ‘b’s, as suggested in the text. The output is formed with ‘c’s, the number of which will be the absolute value of m – n.

absDiff :: Algorithm
absDiff = [("ab", "" , 0, 1),
           ("a" , "c", 1, 2),
           ("b" , "c", 2, 3)]

We can execute this algorithm for some sample input with

exec absDiff "aaaabb"

Which should print “cc”.

And here is the algorithm for calculating the greatest common divisor of m and n, using the same convention for the input. The output will consist of ‘a’s. This is the answer to exercise 8 of Section 1.1.

mGcd :: Algorithm
mGcd = [("ab", "" , 1, 2),      -- 0
        (""  , "c", 0, 2),      -- 1
        ("a" , "b", 2, 3),      -- 2
        ("c" , "a", 3, 4),      -- 3
        ("b" , "b", 0, 5)]      -- 4

The name is mGcd (for Markov gcd) to avoid clashes with the Prelude’s gcd. Note also that in step 1 the string theta (which is empty) should always match, so the value of a is irrelevant. I put 2 there, Knuth used 0 in the answer. Now let’s define some auxiliary functions to help us actually use this with some significant numbers:

buildStr m n = (replicate m 'a') ++ (replicate n 'b')

interpretResult = length

markovGCD m n = interpretResult $ exec mGcd (buildString m n)

And now we can use it:

*Main> markovGCD 2166 6099
57

It takes quite a few seconds, but outputs the correct answer to exercise 4 of Section 1.1.