Leonardo Random Access Lists

Leonardo.hs

module Leonardo where

data Leonardo a = Cons !Int !Int (Tree a) (Leonardo a) | Nil deriving Show
data Tree a = Bin a (Tree a) (Tree a) | Tip a deriving Show

cons :: a -> Leonardo a -> Leonardo a
cons a (Cons i j bs (Cons j' k cs zs))
  | j == j' = Cons k (next j k) (Bin a bs cs) zs
cons a rs = Cons 1 1 (Tip a) rs

size :: Leonardo a -> Int
size (Cons _ i _ as) = i + size as
size Nil = 0

-- 1,1,3,5,9,15,25
next :: Int -> Int -> Int
next p q = p+q+1

prev :: Int -> Int -> Int
prev p q = q-p-1

prev2 :: Int -> Int -> Int
prev2 p q = 2*p-q

(!) :: Leonardo a -> Int -> a
Nil ! i = undefined
Cons j k a as ! i
  | i < k = go i (prev j k) j a
  | otherwise = as ! (i - k)
  where
    go 0 _ _ (Tip a) = a
    go 0 _ _ (Bin a _ _) = a
    go i j k (Bin _ l r)
      | i <= j    = go (i-1)  (prev2 j k) (prev j k) l
      | otherwise = go (i-j-1) (prev j k) j r