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) =&gt; a -&gt; [a] -&gt; Maybe Int
search _ [] = Nothing
search n h
  | elem == n = Just index
  | elem &lt; n = (+index) . (+1) &lt;$&gt; (search n $ drop (index+1) h)
  | otherwise = search n $ take index h
  where index = length h `quot` 2
        elem = h !! index
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) =&gt; a -&gt; [a] -&gt; Maybe Int
search _ [] = Nothing
search n xs
  | elem == n = Just index
  | elem &lt; n  = (+index) . (+1) &lt;$&gt; 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) =&gt; a -&gt; [a] -&gt; Maybe Int
search _ [] = Nothing
search n xs
  | elem == n = Just index
  | elem &lt; n  = (+index) . (+1) &lt;$&gt; search n bs
  where ...


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

search n xs = case elem `compare` n of
    EQ -&gt; Just index
    LT -&gt; (+index) . (+1) &lt;$&gt; 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) =&gt; a -&gt; [a] -&gt; Maybe Int
search n ys = go (length ys) ys
  where
    go _ [] = Nothing
    go l xs = ...