miu.hs

{-# LANGUAGE Haskell2010, LambdaCase #-}

import Data.List (nub)

data Symbol = M | I | U deriving (Eq, Show)

apply = \case
  M : xs         -> [ M : xs ++ xs ]
  I : I : I : xs -> [ U : xs ]
  U : U : xs     -> [ xs ]
  I : []         -> [ I : U : [] ]
  xs             -> []

applyAll = \case
  []          -> []
  ss@(s : rs) -> apply ss ++ map (s :) (applyAll rs)

nextGen (curGen, start) = (oldGen, noDupes (start >>= applyAll))
 where
  noDupes = nub . filter (not . flip elem oldGen)
  oldGen  = start ++ curGen

enumerateAll start = concatMap snd (iterate nextGen ([], [start]))

main = mapM_ (putStrLn . map (head . show)) (enumerateAll [M, I])