Binary Search in Haskell

Question

I have been trying to pick Haskell back up so I decided to try to implement binary search as practice. I am aware that binary search in Haskell in inefficient because Haskell's lists are implemented as linked lists, but I wanted to try it anyway. I would love to know how I could improve this or how it could be more idiomatic, thanks!

search :: (Ord a) => a -> [a] -> Maybe Int
search _ [] = Nothing
search n h
  | elem == n = Just index
  | elem < n = (+index) . (+1) <$> (search n $ drop (index+1) h)
  | otherwise = search n $ take index h
  where index = length h `quot` 2
        elem = h !! index

Answer 1

Since there is already a function called elem, I wouldn't call the element the same. There's no way that those two can get mistaken though, since their types differ. So you're safe at that point. However, you will still get a warning on -Wall.

Next, you call your list h. Lists are usually called xs (one x, may xses), which makes it a little bit harder to catch than it needs to be. We can also split the list into the three parts at the same time:

search :: (Ord a) => a -> [a] -> Maybe Int
search _ [] = Nothing
search n xs
  | elem == n = Just index
  | elem < n  = (+index) . (+1) <$> search n bs
  | otherwise = search n as
  where index = length xs `quot` 2
        (as,elem:bs) = splitAt index xs

This removes the need to traverse the list again just to get the correct init/tail, however it's harder to read, so it's up to you. Also, I really like to have the compiler yell at me if I forgot a case in my guards. For example, GHC will happily accept

search :: (Ord a) => a -> [a] -> Maybe Int
search _ [] = Nothing
search n xs
  | elem == n = Just index
  | elem < n  = (+index) . (+1) <$> search n bs
  where ...

even with warnings. With compare elem n, we get warnings:

search n xs = case elem `compare` n of
    EQ -> Just index
    LT -> (+index) . (+1) <$> search n bs
    -- third missing, GHC warns us 
  where ...

But that's more or less a personal preference. A major nitpick though is that you take the length of the list in every iteration. You can get rid of that if you write another function:

search :: (Ord a) => a -> [a] -> Maybe Int
search n ys = go (length ys) ys
  where
    go _ [] = Nothing
    go l xs = ...