Array Search in Haskell

Question

I currently try to learn some Haskell to improve my overall programming skills. To practice, I implement the C course exercises that I very familiar with. One is this:

Write a function that finds an array (needle) inside of another array (haystack). Return the index where the first match starts. If it cannot be found, return -1.

So in C, this is implemented using a couple of loops:

int array_find(char *hay, char *nee, int hay_len, int nee_len) {
    int hay_idx, nee_idx;
    for (hay_idx = 0; hay_idx < hay_len - nee_len; hay_idx++) {
        for (nee_idx = 0; nee_idx < nee_len; nee_idx++) {
            if (hay[hay_idx + nee_idx] != nee[nee_idx]) {
                break;
            }
        }
        if (nee_idx == nee_len) {
            return hay_idx;
        }
    }

    return -1;
}

The following is my attempt in Haskell. I made comments which probably state the obvious for Haskell experts but it should make my reasoning clear.

-- Public function, searches the haystack for a needle and returns the index
-- (zero-based).
arraySearch :: (Eq a) => [a] -> [a] -> Maybe Int
arraySearch h n = arraySearchNext (arraySearchBegin h n 0) h n 0

-- Searches the haystack starting from the next position if the last search has
-- failed.
arraySearchNext :: (Eq a) => Maybe Int -> [a] -> [a] -> Int -> Maybe Int
-- The previous search has found something, so that is the first occurence of
-- the needle.
arraySearchNext (Just i) _ _ _ = Just i
-- The previous search has not given us anything but we are out of haystack.
-- Therefore nothing could be found.
arraySearchNext Nothing [] _ _ = Nothing
-- The previous search has not found anything but there is some haystack left.
-- We will try the search again by shifting by one and then shift again.
arraySearchNext Nothing (h:hs) n i =
    arraySearchNext (arraySearchBegin hs n (i + 1)) hs n (i + 1)

-- Looks whether the needle can be found at the beginning of the haystack.
arraySearchBegin :: (Eq a) => [a] -> [a] -> Int -> Maybe Int
-- In case we managed to finish the needle, we must have found something.
arraySearchBegin _ [] i = Just i
-- In case the haystack is empty, but the needle is not (pattern above), we
-- have not found anything.
arraySearchBegin [] _ _ = Nothing
-- There is still some haystack and needle left. If the first element each
-- matches, we must go on. Otherwise this won't be a match.
arraySearchBegin (h:hs) (n:ns) i
    | h == n        = arraySearchBegin hs ns i
    | otherwise     = Nothing

main = print $ arraySearch [1..10] [5..6]

Since there are so many lines and I have a bunch of helper functions, I wonder whether there is some better way‽

Answer 1

You use explicit recursion, which is fun, but not always necessary. arraySearchBegin can be expressed with zipWith and and, for example:

arraySearchBegin :: (Eq a) => [a] -> [a] -> b -> Maybe b
arraySearchBegin hs ns k
  | and (zipWith (==) hs ns) = Just k
  | otherwise                = Nothing

But that's still to explicit. Data.List contains isPrefixOf, which is exactly what we need:

import Data.List (isPrefixOf)

arraySearchBegin :: (Eq a) => [a] -> [a] -> b -> Maybe b
arraySearchBegin hs ns k
  | ns `isPrefixOf` hs = Just k
  | otherwise          = Nothing

That being said, arraySearchBegin's name is misleading. [a] is a linked list, not an array. We should probably rename it, but we won't use it in the final variant of arraySearch.

Next, we don't need the Maybe Int in arraySearchNext:

arraySearchNext :: (Eq a) => [a] -> [a] -> Int -> Maybe Int
arraySearchNext []         ns _ = Nothing
arraySearchNext hss@(_:hs) ns i
  | ns `isPrefixOf` hss = Just i
  | otherwise           = arraySearchNext hs ns (i + 1)

We can stop as soon as our needle is a prefix of our haystack. However, we're basically checking all tails of hss here. And there is again a function in Data.List that yields those tails for us:

ghci> import Data.List
ghci> tails [1..5]
[[1,2,3,4,5],[2,3,4,5],[3,4,5],[4,5],[5],[]]

We therefore just check which one is the first list in tails haystack that can be prefixed by needle. If we zip the indexes with the tails we're able to write arraySearch as a list comprehension:

import Data.Maybe (listToMaybe)
import Data.List (isPrefixOf, tails)

search :: Eq a => [a] -> [a] -> Maybe Int
search hs ns = listToMaybe [ idx | (idx, hss) <- zip [0..] tails hs
                                 , ns `isPrefixOf` hss
                           ]

But Data.List contains findIndex :: (a -> Bool) -> [a] -> Maybe Int, which brings us to:

import Data.List (isPrefixOf, tails, findIndex)

search :: Eq a => [a] -> [a] -> Maybe Int
search hs ns = findIndex (ns `isPrefixOf`) (tails hs)

This however needs knowledge of the standard library. So how do you find those functions if you don't know them yet? Welcome to Hoogle. We can find findIndex by searching for (a -> Bool) -> [a] -> Maybe Int, isPrefixOf by Eq a => [a] -> [a] -> Bool and tails by [a] -> [[a]].

If we didn't have any of those helpers, your code would be fine, except for the strange explicit result in arraySearchNext's first argument. That was too complex, as you will stop as soon as you find a Just either way.