{- ------------------------------------------------------------- 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))