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‽