okasaki

Okasaki's Purely Functional Data Structures
git clone git://git.jtobin.io/okasaki.git
Log | Files | Refs | LICENSE

Stack.hs (1091B)


      1 {-# OPTIONS_GHC -Wall #-}
      2 
      3 module Stack where
      4 
      5 import Prelude hiding (head, tail)
      6 
      7 data Stack a = Nil | Cons a (Stack a) deriving (Eq, Show)
      8 
      9 isEmpty :: Stack a -> Bool
     10 isEmpty Nil = True
     11 isEmpty _   = False
     12 
     13 empty :: Stack a
     14 empty = Nil
     15 
     16 cons :: a -> Stack a -> Stack a
     17 cons = Cons
     18 
     19 head :: Stack a -> Maybe a
     20 head Nil = Nothing
     21 head (Cons h _) = return h
     22 
     23 tail :: Stack a -> Maybe (Stack a)
     24 tail Nil = Nothing
     25 tail (Cons _ t) = return t
     26 
     27 fromList :: [a] -> Stack a
     28 fromList = foldr Cons Nil
     29 
     30 toList :: Stack a -> [a]
     31 toList Nil = []
     32 toList (Cons h t) = h : toList t
     33 
     34 append :: Stack a -> Stack a -> Stack a
     35 append Nil ys        = ys
     36 append (Cons h t) ys =
     37   let txs = append t ys
     38   in  cons h txs
     39 
     40 update :: Stack a -> Int -> a -> Maybe (Stack a)
     41 update Nil _ _ = Nothing
     42 update (Cons h t) j y
     43   | j < 0     = Nothing
     44   | j == 0    = return (Cons y t)
     45   | otherwise = do
     46       nt <- update t (pred j) y
     47       return (Cons h nt)
     48 
     49 -- exercise 2.1
     50 suffixes :: Stack a -> Stack (Stack a)
     51 suffixes Nil = Nil
     52 suffixes (Cons _ t) = Cons t (suffixes t)
     53 
     54 test :: Stack Int
     55 test = fromList [1..10]
     56