[Haskell-cafe] Haskell KMP(Knuth-Morris-Pratt) algorithm

Hi, I read about some KMP implementation in Haskell including: [1] Richard Bird. ``Pearls of Functional algorithm design'' [2] http://twan.home.fmf.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell.details [3] http://www.haskell.org/haskellwiki/Runtime_compilation [4] LazyString version [1]

Re: [Haskell-cafe] Haskell KMP(Knuth-Morris-Pratt) algorithm

Hi, Here is Richard Bird's version for reference. I changed it a bit. data State a = E | S a (State a) (State a) matched (S (_, []) _ _) = True matched _ = False kmpSearch4 :: (Eq a) = [a] - [a] - [Int] kmpSearch4 ws txt = snd $ foldl tr (root, []) (zip txt [1..]) where root = build E ([],