32 lines
837 B
Haskell
32 lines
837 B
Haskell
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
|