マルコフアルゴリズム

markov.hs

import Control.Applicative
import Data.List (stripPrefix, intercalate)

sub :: Eq a => [a] -> [a] -> [a] -> Maybe [a]
sub from to s = (to ++) <$> stripPrefix from s <|> rec s
  where
    rec [] = Nothing
    rec (x:xs) = (x :) <$> sub from to xs

step :: [(String,String)] -> String -> Maybe String
step [] _ = Nothing
step ((from,to):rs) s = sub from to s <|> step rs s

run :: [(String,String)] -> String -> [String]
run rs s = s : maybe [] (run rs) (step rs s)

bin :: [(String,String)]
bin = [ ("|0", "0||")
      , ("1", "0|")
      , ("0", "")
      ]

main = do
  let s = "101"
  putStrLn $ intercalate " -> " $ run bin s