{-# LANGUAGE GADTs #-} module Problem1.Deep where import qualified Prelude as P import Prelude(Int,(+),(-),max,min,(<),(<=),(==),(&&),Bool,Show,String, (!!), otherwise, div) import qualified Problem1.Shallow as V import qualified Problem1.Shallow_Instances () ---------------- -- Problem 1(c) type Ix = P.Int type Length = P.Int type Vector = D data D a where FromList :: [a] -> D a FromV :: V.V a -> D a (:++) :: D a -> D a -> D a -- primitive (++) :: D a -> D a -> D a (++) = (:++) length :: Vector a -> Length length (xs :++ ys) = length xs + length ys length (FromList xs) = P.length xs length (FromV v) = V.length v drop :: Ix -> Vector a -> Vector a drop i (xs :++ ys) | i <= l = drop i xs :++ ys | otherwise = drop (i-l) ys where l = length xs drop i (FromList xs) = FromList (P.drop i xs) drop i (FromV v) = FromV (V.drop i v) take :: Ix -> Vector a -> Vector a take i (xs :++ ys) | i <= l = take i xs | otherwise = xs :++ take (i-l) ys where l = length xs take i (FromList xs) = FromList (P.take i xs) take i (FromV v) = FromV (V.take i v) -- Derived operations: splitAt :: Ix -> Vector a -> (Vector a, Vector a) splitAt i v = (take i v, drop i v) -- -------------------------------------------------------------- -- For completeness (not asked for in exam question): fromFun :: Length -> (Ix -> a) -> Vector a fromFun l f = FromV (V.V l f) fromList :: [a] -> Vector a fromList = FromList index :: Vector a -> Ix -> a index (xs :++ ys) i | i<l = index xs i | otherwise = index ys (i-l) where l = length xs index (FromList xs) i = xs P.!! i index (FromV v) i = V.index v i head :: Vector a -> a head xs = index xs 0 tail :: Vector a -> Vector a tail = drop 1 ---------------------------------------------------------------- -- Not part of the exam question, but needed in pratice toList :: Vector a -> [a] toList (FromList xs) = xs toList (FromV v) = V.toList v toList (v :++ w) = toList v P.++ toList w