Challenge: implement binary search. Do not use library functions. Do not write or run tests, not even manually. Asking the compiler for correctness is allowed, but nothing more. Not even looking up pseudocode for binarysearch.

Can you do it?



@musicmatze I'm not sure what it would mean to not use library functions. This uses just the Prelude, ( and therefore linked-lists under the hood, which is silly but would technically work)

indexOf :: Ord a => [a] -> a -> Maybe Int
indexOf [] _ = Nothing
indexOf xs y =
let i = (length xs) `div` 2
choice LT = indexOf (take i xs) y
choice EQ = Just i
choice GT = indexOf (drop (i + 1) xs) y
in choice $ compare y (xs !! i)

And.... It doesn't work because the top-level index isn't tracked down into the recursion.

Sign in to participate in the conversation
Mastodon for Tech Folks

This Mastodon instance is for people interested in technology. Discussions aren't limited to technology, because tech folks shouldn't be limited to technology either!