module Nested where

data Fork t = Fork t t
  deriving (Show, Eq)

data RandList t = Nil
                | Zero  (RandList (Fork t))
                | One t (RandList (Fork t))
  deriving (Show, Eq)

cons :: a -> RandList a -> RandList a
cons x  Nil         = One x Nil
cons x1 (Zero ds)   = One x1 ds
cons x1 (One x2 ds) = Zero (cons (Fork x1 x2) ds)

front :: RandList a -> (a, RandList a)
front Nil = error "Empty RandList"
front (One x Nil) = (x,  Nil)
front (One x ds)  = (x,  Zero ds)
front (Zero ds)   = (x1, One x2 ds')
  where (Fork x1 x2, ds') = front ds

find :: Int -> RandList a -> a
find 0 Nil = error "Not found"
find 0 (One x _)  = x
find i (One _ ds) = find (i-1) (Zero ds)
find i (Zero ds)  = if i`mod`2 == 0 then x else y
  where (Fork x y) = find (i`div`2) ds

fromList :: [a] -> RandList a
fromList = foldr cons Nil