Hello Daniel,

Regarding your solution, can I apply {-# SPECIALISE ... #-} statements to datatypes I define?
And if so, I am not able to import the datatypes to the module where binarySearch is.
The problem is that if I import them a circular dependency is detected and the compiler gives an error.
Is there a way of importing a datatype from another module do avoid this circular dependency?

Thank you,

Arnoldo

On Thu, Mar 18, 2010 at 10:48 PM, Daniel Fischer <daniel.is.fischer@web.de> wrote:
Am Donnerstag 18 März 2010 21:57:34 schrieb Daniel Fischer:
>
> Contrary to my expectations, however, using unboxed arrays is slower
> than straight arrays (in my tests).
>

However, a few {-# SPECIALISE #-} pragmas set the record straight.
Specialising speeds up both, boxed and unboxed arrays, significantly, but
now, for the specialised types, unboxed arrays are faster (note, however,
that when the code for the binary search is in the same module as it is
used, with optimisations, GHC will probably specialise it itself. If
binarySearch is not exported, AFAIK, you can delete "probably".).

{-# LANGUAGE BangPatterns #-}
module SATBinSearch (binarySearch) where

import Data.Array.IArray
import Data.Array.Base (unsafeAt)
import Data.Bits

{-# SPECIALISE binarySearch :: Double -> Array Int Double -> Int #-}
{-# SPECIALISE binarySearch :: Int -> Array Int Int -> Int #-}
{-# SPECIALISE binarySearch :: Bool -> Array Int Bool -> Int #-}
{-# SPECIALISE binarySearch :: Char -> Array Int Char -> Int #-}
{-# SPECIALISE binarySearch :: Float -> Array Int Float -> Int #-}
binarySearch :: Ord a => a -> Array Int a -> Int
binarySearch q a = go l h
     where
       (l,h) = bounds a
       go !lo !hi
           | hi < lo   = -(lo+1)
           | otherwise = case compare mv q of
                           LT -> go (m+1) hi
                           EQ -> m
                           GT -> go lo (m-1)
             where
               -- m = lo + (hi-lo) `quot` 2
               m = (lo .&. hi) + (lo `xor` hi) `shiftR` 1
               mv = a `unsafeAt` m

Use Data.Array.Unboxed and UArray if possible.
Now the bit-fiddling instead of arithmetics makes a serious difference,
about 20% for unboxed arrays, 17% for boxed arrays (Double), so I'd
recommend that.