The PFDS stack in Haskell, early pass
This post came from a short-lived blog I tried to run (tail-recursion.net) where I wanted to write up a short bit of code I'd written that week.
The first data type defined in chapter 2 of PFDS.
Its signature is defined as (in SML):
signature STACK =
sig
type a Stack
val empty :: a Stack
val isEmpty :: a Stack -> bool
val cons :: a x a Stack -> a Stack
val head :: a Stack -> a
val tail :: a Stack -> a Stack
end
The implementation is short and based on polymorphic lists.
module PFDS.Stack
(empty
,isEmpty
,cons
,head'
,tail'
,catenate
) where
type Stack a = [a]
empty :: Stack a
empty = []
isEmpty :: Stack a -> Bool
isEmpty [] = True
isEmpty _ = False
cons :: a -> Stack a -> Stack a
cons x xs = x : xs
head' :: Stack a -> a
head' [] = error "empty stack"
head' (x:_) = x
tail' :: Stack a -> [a]
tail' [] = error "empty stack"
tail' (_:xs) = xs
catenate :: Stack a -> Stack a -> Stack a
catenate [] [] = []
catenate [] (y:ys) = y : catenate [] ys
catenate (x:xs) y = x : catenate xs y
suffixes can simply create pointers to successive elements in the list, and only has to iterate through the list to do so.
For example:
[1,2,3,4] ->[(pointer to list starting at 0), (pointer to list
starting at 1)], etc...
suffixes :: Stack a -> Stack (Stack a)
suffixes [] = cons empty empty
suffixes (x:xs) = cons (cons x xs) $ suffixes xs
This is the same data type implemented in the previous snippet.
The untransformed code is available.