# Binary Search in Haskell

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  ## 1 Answer 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 = ...