## 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!