{- -------------------------------------------------------------
This module demonstrates two different, but compatible, views
of sequences, one modelled after our definitions in lecture
and based on set-theoretic ideas, and the other more directly
on Haskell's algebraic data type definition of lists from the
Prelude. The two implementations are provided as instances of
an abstract sequence type class (called here Seq) which
provides for a useful set of functions.
WU CS 465: LLC (Spr 2013); Fritz Ruehr
------------------------------------------------------------- -}
module Sequences where
----------------------------------------
-- An abstract account of sequences (i.e., this is the functionality
-- that any proposed implementation should provide).
-- Note the lack of axioms relating the functions: what should they be?
class Seq s where
empty :: s a
sing :: a -> s a
join :: s a -> s a -> s a
rev :: s a -> s a
smap :: (a -> b) -> s a -> s b
len :: s a -> Int
(#) :: s a -> Int -> a
----------------------------------------
-- The "mathematical" definition of sequences from lecture, as ordered
-- pairs of a length and a function on naturals less than that length.
data SetSeq a = Seq (Int, Int -> a)
instance Seq SetSeq where
empty = Seq (0, undefined)
sing a = Seq (1, \i -> if i == 0 then a else undefined)
join (Seq (k,f)) (Seq (j,g))
= Seq (k+j, \i -> if i < k then f i else g (i-k))
rev (Seq (k,f)) = Seq (k, \i -> f (k-i-1))
smap h (Seq (k,f)) = Seq (k, h . f)
len (Seq (k,_)) = k
(#) (Seq (_,f)) = f
instance Show a => Show (SetSeq a) where
show (Seq (k,f)) = delim "|" "," "|" (map (show . f) [0..k-1])
----------------------------------------
-- Orindary Haskell lists as sequences;
-- implicitly, we have from the Prelude:
--
-- data [a] = [] | (:) a [a]
--
-- Or, in more traditional syntax:
--
-- data List a = Nil | Cons a (List a)
instance Seq [] where
empty = []
sing = (:[])
join = (++)
rev = reverse
smap = map
len = length
(#) = (!!)
----------------------------------------
-- build converts from a Prelude list to any Seq instance
build :: Seq s => [a] -> s a
build = foldr join empty . map sing
test = build [1..5] :: SetSeq Int
long :: Seq s => s Int
long = build [1..100]
----------------------------
-- utility functions for display of SetSeq's
delim l c r xs = l ++ concat (sperse c xs) ++ r
sperse p [] = []
sperse p [x] = [x]
sperse p (x:xs) = x : p : sperse p xs
----------------------------------------------------------------
-- exploring some other ideas below:
-- induction / folds on SetSeqs
foldrss f u (Seq (n,g)) = fh 0
where fh m = if m==n then u else f (g m) (fh (m+1))
foldlss f u (Seq (n,g)) = fh 0 u
where fh m a = if m==n then a else fh (m+1) (f a (g m))