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

arraySearchBegin :: (Eq a) =&gt; [a] -&gt; [a] -&gt; b -&gt; 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) =&gt; [a] -&gt; [a] -&gt; b -&gt; 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) =&gt; [a] -&gt; [a] -&gt; Int -&gt; 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&gt; import Data.List
ghci&gt; 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 =&gt; [a] -&gt; [a] -&gt; Maybe Int
search hs ns = listToMaybe [ idx | (idx, hss) &lt;- zip [0..] tails hs
                                 , ns `isPrefixOf` hss
                           ]


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

import Data.List (isPrefixOf, tails, findIndex)

search :: Eq a =&gt; [a] -&gt; [a] -&gt; 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 -&gt; Bool) -&gt; [a] -&gt; Maybe Int, isPrefixOf by Eq a =&gt; [a] -&gt; [a] -&gt; Bool and tails by [a] -&gt; [[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.