Transliteration into Haskell brings type-safety into it, and cuts it down to 7 lines: import Prelude hiding (seq) seq l r s = concatMap r (l s) alt l

Transliteration into Haskell brings type-safety into it, and cuts it down to 7 lines: import Prelude hiding (seq) seq l r s = concatMap r (l s) alt l r s = l s ++ r s star e s = s : seq e (star e) s plus e = seq e (star e) char c (x:xs) | x == c = [xs] | otherwise = [] char _ _ = [] example = seq (char 'c') $ seq (plus (alt (char 'a') (char 'd'))) (char 'r') main = do line <- getLine mapM_ (putStrLn . ("Match with remainder: "++)) (example line) (Note the original implementation failed to reuse itertools.chain, in Haskell I just use (++)).