6
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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 = ...
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.