Programming Praxis - Growable Arrays

Due to another conference (can’t they distribute them a bit more evenly around the year?) I won’t be here for the next three exercises.

In today’s Programming Praxis we’re going to implement a growable array, which is a data structure with logarithmic access where elements can be added without needing reallocation. Basically it’s little more than a binary tree. Let’s get started.

We’ll use a fairly standard binary tree for our data structure:

data Grow a = Empty | Grow { val :: a, l :: Grow a, r:: Grow a }

Next, we want a function that handles taking the correct branches, since we don’t want to have to repeat ourselves.

walk :: (Int -> Grow a -> b) -> Int -> Grow a -> b
walk f i = f (div i 2) . if even i then l else r

We also define another convenience function that handles updating the tree. Unfortunately Haskell doesn’t have first class records yet, so there is some duplication of logic here.

modify :: Grow a -> (Int -> Grow a -> Grow a) -> Int -> Grow a -> Grow a
modify d _ _ Empty         = d
modify _ f i g | even i    = g { l = walk f i g }
               | otherwise = g { r = walk f i g }

Now for the three functions we had to implement: get, put and hirem. Thanks to walk and modify, these are all fairly trivial.

get :: Int -> Grow a -> Maybe a
get _ Empty = Nothing
get 1 g     = Just $ val g
get i g     = walk get i g

put :: Int -> a -> Grow a -> Grow a
put 1 x Empty = Grow x Empty Empty
put 1 x g     = g { val = x }
put i x g     = modify (error "array out of bounds") (`put` x) i g

hirem :: Int -> Grow a -> Grow a
hirem 1 = const Empty
hirem i = modify Empty hirem i

And of course we have to test if we made any mistakes:

main :: IO ()
main = do let arr = foldl (flip (uncurry put)) Empty $ zip [1..]
                    ["alfa", "bravo", "charlie", "delta",
                     "echo", "foxtrot", "golf"]
          print $ get 7 arr
          print $ get 12 arr
          print . get 7 $ hirem (size arr) arr
       where size Empty = 0
             size g     = 1 + size (l g) + size (r g)

Looks like everything is working correctly. See you guys in two weeks!

About these ads

Tags: arrays, bonsai, code, data, growable, Haskell, kata, praxis, programming, structure