I am trying to learn more Haskell and decided to implement binary search.
I have read (in Programming Pearls) that even experienced programmers generally get
binary search wrong on their first try in procedural programming
languages. Apparently, it took nearly 20 years for the published
literature to generate a correct binary search algorithm.
So, given how clean quicksort appears in Haskell, I figured that
binarySearch would also be less likely to have bugs in Haskell as well.
Ideally I would be unlikely to have an error if it compiled.
It took me a while to figure out how to think it in Haskell and here is
what I came up with:
> binarySearch :: (Integral a, Ix a, Ord b) => Array a b -> b -> Bool
> binarySearch ar val = impl ar (bounds ar) val
> where impl ar (low,high) val | low==high = ar!low == val
> | ar!index == val = True
> | ar!index < val = impl ar (index,high) val
> | ar!index > val = impl ar (low,index) val
> where index = getMiddle low high
> where getMiddle low high=div
>(high+low) 2
This code has a bug. It fails to terminate if the item is not in the list
because getMiddle rounds down e.g. [(3,3),(4,7)] 4 just recurses.
The way to avoid this type of error in C is to use preconditions and loop
invariants. However these are concepts associated with weakly typed
procedural languages.
Which leads to two major questions and one minor question:
1. how I should have approached this problem in Haskell in a manner
more likely to avoid this type of error? e.g. in a manner more
likely to generate a compiler error if my code is incorrect?
2. how would I have found/fixed such an error in a more complex function
w/o assertions and w/o print statements?
3. Is it possible to perform bSearch on a list? i.e. the first time the
code is called on the list, an array is generated. The function
should then cache the array so that there is no array conversion the second time?
Should I have created some balance tree instead of an array?
-Alex-
PS the fix for this code is that you need to add or subtract 1 from index
when you narrow the range
___________________________________________________________________
S. Alexander Jacobson i2x Media
1-212-697-0184 voice 1-212-697-1427 fax
