dikini.net

I've been looking more into haskell, as part of some personal projects. There I need some constant array like structures, that is ones which have integer indexing and there are some long winded reasons I'm not using a Map. As a first step I've decided look at haskell arrays, by writing some search functions. It is mostly a syntax exercise.

Administrivia and some data to play with - a sorted array of squares

import Data.Array

squares n = array (0,n) [(x,x*x) |x<-[0..n]]
s = squares 10

A binary search function, where b is the bounds of a subrange, within the array.

find b@(l,u) arr val =
    let  find' (l,u) arr val
             | l >  u                 = Nothing
             | l == u && arr!l == val = Just l    --
             | l == u                 = Nothing   --
             | val == arr!m = Just m
             | val <= arr!m = find' (l    , m) arr val
             | otherwise    = find' (m + 1, u) arr val
             where m = (u+l) `div` 2
         (l',u') = bounds arr
    in if (l' <= l) && (u <= u')
       then find' b arr val
       else Nothing

A sightly different, binary search function, always searching through the whole range of the array.

find arr val =
   let find' b@(lo,up) arr val = 
           case (compare lo up) of
             GT -> Nothing                      -- empty
             EQ -> case (compare (arr!lo) val) of
                      EQ -> Just lo             -- found
                      otherwise -> Nothing         -- is not in interval
             LT -> case (compare (arr!m) val) of
                      EQ -> Just m                  -- found
                      GT -> find' (lo, m) arr val   -- left
                      LT -> find' (m+1, up) arr val -- right
             where
                 m = (lo + up) `div` 2          
    in find' (bounds arr) arr val

Both functions should be safe - that is they should not cause out of bounds exceptions. For statically checked bounds checking look at Eliminating Array Bound Checking through Non-dependent types

note: changed the second listing. Will teach me pay attention what do I copy, or switch to some more literate blogging...