text: Today’s Programming Praxis problem marks the end of the string search series. In this final entry, we have to implement the Rabin-Karp search algorithm. Let’s see what we can do.
  First some imports:
  import Data.Char import Data.List
  We need the ascii values of the characters in the string, and since the hash values we’re going to be using can get quite large, we’re going to use Integers.
  asciis :: String -> [Integer] asciis = map (fromIntegral . ord)
  The hash function treats the list of ascii values as a base 256 number.
  hash :: Num a => [a] -> a hash = sum . zipWith (*) (iterate (* 256) 1) . reverse
  For the algorithm, we need the hashes of all the pattern-length substrings of the search string.
  hashes :: Int -> String -> [Integer] hashes p xs = scanl (\s (f,t) -> 256*s - 256^p*f + t) (hash $ take p ascs) . zip ascs $ drop p ascs where ascs = asciis xs
  With those helper functions defined, the search algorithm becomes fairly straightforward:
  rabinKarp :: String -> Maybe Int -> String -> Maybe Int rabinKarp p s = lookup (hash $ asciis p) . drop (maybe 0 id s) . flip zip [0..] . hashes (length p)
  And as before, we run our algorithm through the test suite:
  test :: (String -> Maybe Int -> String -> Maybe Int) -> IO () test f = do assertEqual (f "" Nothing "Hello World") (Just 0) assertEqual (f "He" Nothing "Hello World") (Just 0) assertEqual (f "od" Nothing "Bonsai Code") (Just 8) assertEqual (f "ef" Nothing "Bonsai Code") (Nothing) assertEqual (f "" (Just 1) "Hello World") (Just 1) assertEqual (f "He" (Just 1) "Hello World") (Nothing) assertEqual (f "od" (Just 1) "Bonsai Code") (Just 8) assertEqual (f "ef" (Just 1) "Bonsai Code") (Nothing) where assertEqual a b = print (a == b, a, b) main :: IO () main = test rabinKarp
  Everything’s working correctly. Not bad for 6 lines of code.
  Tags: bonsai, code, Haskell, karp, kata, praxis, programming, rabin, search, string