{-# LANGUAGE DeriveDataTypeable #-} {- | Module : ./Common/Lib/SizedList.hs Description : lists with their size similar to Data.Edison.Seq.SizedSeq Copyright : C. Maeder DFKI Bremen 2008 License : GPLv2 or higher, see LICENSE.txt Maintainer : Christian.Maeder@dfki.de Stability : experimental Portability : portable a list plus its length for a more efficient history implementation. Parts of the implementation is stolen from Data.Edison.Seq.SizedSeq -} module Common.Lib.SizedList ( SizedList , fromList , toList , empty , singleton , cons , append , head , tail , null , size , reverse , take , drop , map ) where import Prelude hiding (null, head, tail, reverse, take, drop, map) import Data.Data import qualified Data.List as List data SizedList a = N !Int [a] deriving (Int -> SizedList a -> ShowS [SizedList a] -> ShowS SizedList a -> String (Int -> SizedList a -> ShowS) -> (SizedList a -> String) -> ([SizedList a] -> ShowS) -> Show (SizedList a) forall a. Show a => Int -> SizedList a -> ShowS forall a. Show a => [SizedList a] -> ShowS forall a. Show a => SizedList a -> String forall a. (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a showList :: [SizedList a] -> ShowS $cshowList :: forall a. Show a => [SizedList a] -> ShowS show :: SizedList a -> String $cshow :: forall a. Show a => SizedList a -> String showsPrec :: Int -> SizedList a -> ShowS $cshowsPrec :: forall a. Show a => Int -> SizedList a -> ShowS Show, SizedList a -> SizedList a -> Bool (SizedList a -> SizedList a -> Bool) -> (SizedList a -> SizedList a -> Bool) -> Eq (SizedList a) forall a. Eq a => SizedList a -> SizedList a -> Bool forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a /= :: SizedList a -> SizedList a -> Bool $c/= :: forall a. Eq a => SizedList a -> SizedList a -> Bool == :: SizedList a -> SizedList a -> Bool $c== :: forall a. Eq a => SizedList a -> SizedList a -> Bool Eq, Eq (SizedList a) Eq (SizedList a) => (SizedList a -> SizedList a -> Ordering) -> (SizedList a -> SizedList a -> Bool) -> (SizedList a -> SizedList a -> Bool) -> (SizedList a -> SizedList a -> Bool) -> (SizedList a -> SizedList a -> Bool) -> (SizedList a -> SizedList a -> SizedList a) -> (SizedList a -> SizedList a -> SizedList a) -> Ord (SizedList a) SizedList a -> SizedList a -> Bool SizedList a -> SizedList a -> Ordering SizedList a -> SizedList a -> SizedList a forall a. Eq a => (a -> a -> Ordering) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> Bool) -> (a -> a -> a) -> (a -> a -> a) -> Ord a forall a. Ord a => Eq (SizedList a) forall a. Ord a => SizedList a -> SizedList a -> Bool forall a. Ord a => SizedList a -> SizedList a -> Ordering forall a. Ord a => SizedList a -> SizedList a -> SizedList a min :: SizedList a -> SizedList a -> SizedList a $cmin :: forall a. Ord a => SizedList a -> SizedList a -> SizedList a max :: SizedList a -> SizedList a -> SizedList a $cmax :: forall a. Ord a => SizedList a -> SizedList a -> SizedList a >= :: SizedList a -> SizedList a -> Bool $c>= :: forall a. Ord a => SizedList a -> SizedList a -> Bool > :: SizedList a -> SizedList a -> Bool $c> :: forall a. Ord a => SizedList a -> SizedList a -> Bool <= :: SizedList a -> SizedList a -> Bool $c<= :: forall a. Ord a => SizedList a -> SizedList a -> Bool < :: SizedList a -> SizedList a -> Bool $c< :: forall a. Ord a => SizedList a -> SizedList a -> Bool compare :: SizedList a -> SizedList a -> Ordering $ccompare :: forall a. Ord a => SizedList a -> SizedList a -> Ordering $cp1Ord :: forall a. Ord a => Eq (SizedList a) Ord, Typeable, Typeable (SizedList a) Constr DataType Typeable (SizedList a) => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SizedList a -> c (SizedList a)) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SizedList a)) -> (SizedList a -> Constr) -> (SizedList a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SizedList a))) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SizedList a))) -> ((forall b. Data b => b -> b) -> SizedList a -> SizedList a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r) -> (forall u. (forall d. Data d => d -> u) -> SizedList a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> SizedList a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a)) -> Data (SizedList a) SizedList a -> Constr SizedList a -> DataType (forall d. Data d => c (t d)) -> Maybe (c (SizedList a)) (forall b. Data b => b -> b) -> SizedList a -> SizedList a (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SizedList a -> c (SizedList a) (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SizedList a) forall a. Data a => Typeable (SizedList a) forall a. Data a => SizedList a -> Constr forall a. Data a => SizedList a -> DataType forall a. Data a => (forall b. Data b => b -> b) -> SizedList a -> SizedList a forall a u. Data a => Int -> (forall d. Data d => d -> u) -> SizedList a -> u forall a u. Data a => (forall d. Data d => d -> u) -> SizedList a -> [u] forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SizedList a) forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SizedList a -> c (SizedList a) forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (SizedList a)) forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SizedList a)) forall a. Typeable a => (forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> a -> c a) -> (forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c a) -> (a -> Constr) -> (a -> DataType) -> (forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c a)) -> (forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a)) -> ((forall b. Data b => b -> b) -> a -> a) -> (forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r) -> (forall u. (forall d. Data d => d -> u) -> a -> [u]) -> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u) -> (forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> (forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> a -> m a) -> Data a forall u. Int -> (forall d. Data d => d -> u) -> SizedList a -> u forall u. (forall d. Data d => d -> u) -> SizedList a -> [u] forall r r'. (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r forall (m :: * -> *). Monad m => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) forall (m :: * -> *). MonadPlus m => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) forall (c :: * -> *). (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SizedList a) forall (c :: * -> *). (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SizedList a -> c (SizedList a) forall (t :: * -> *) (c :: * -> *). Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (SizedList a)) forall (t :: * -> * -> *) (c :: * -> *). Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SizedList a)) $cN :: Constr $tSizedList :: DataType gmapMo :: (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) $cgmapMo :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) gmapMp :: (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) $cgmapMp :: forall a (m :: * -> *). (Data a, MonadPlus m) => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) gmapM :: (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) $cgmapM :: forall a (m :: * -> *). (Data a, Monad m) => (forall d. Data d => d -> m d) -> SizedList a -> m (SizedList a) gmapQi :: Int -> (forall d. Data d => d -> u) -> SizedList a -> u $cgmapQi :: forall a u. Data a => Int -> (forall d. Data d => d -> u) -> SizedList a -> u gmapQ :: (forall d. Data d => d -> u) -> SizedList a -> [u] $cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> SizedList a -> [u] gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r $cgmapQr :: forall a r r'. Data a => (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r $cgmapQl :: forall a r r'. Data a => (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> SizedList a -> r gmapT :: (forall b. Data b => b -> b) -> SizedList a -> SizedList a $cgmapT :: forall a. Data a => (forall b. Data b => b -> b) -> SizedList a -> SizedList a dataCast2 :: (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SizedList a)) $cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (SizedList a)) dataCast1 :: (forall d. Data d => c (t d)) -> Maybe (c (SizedList a)) $cdataCast1 :: forall a (t :: * -> *) (c :: * -> *). (Data a, Typeable t) => (forall d. Data d => c (t d)) -> Maybe (c (SizedList a)) dataTypeOf :: SizedList a -> DataType $cdataTypeOf :: forall a. Data a => SizedList a -> DataType toConstr :: SizedList a -> Constr $ctoConstr :: forall a. Data a => SizedList a -> Constr gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SizedList a) $cgunfold :: forall a (c :: * -> *). Data a => (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (SizedList a) gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SizedList a -> c (SizedList a) $cgfoldl :: forall a (c :: * -> *). Data a => (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> SizedList a -> c (SizedList a) $cp1Data :: forall a. Data a => Typeable (SizedList a) Data) fromList :: [a] -> SizedList a fromList :: [a] -> SizedList a fromList xs :: [a] xs = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N ([a] -> Int forall (t :: * -> *) a. Foldable t => t a -> Int length [a] xs) [a] xs toList :: SizedList a -> [a] toList :: SizedList a -> [a] toList (N _ xs :: [a] xs) = [a] xs empty :: SizedList a empty :: SizedList a empty = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N 0 [] singleton :: a -> SizedList a singleton :: a -> SizedList a singleton x :: a x = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N 1 [a x] cons :: a -> SizedList a -> SizedList a cons :: a -> SizedList a -> SizedList a cons x :: a x (N n :: Int n xs :: [a] xs) = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N (Int -> Int forall a. Enum a => a -> a succ Int n) ([a] -> SizedList a) -> [a] -> SizedList a forall a b. (a -> b) -> a -> b $ a x a -> [a] -> [a] forall a. a -> [a] -> [a] : [a] xs append :: SizedList a -> SizedList a -> SizedList a append :: SizedList a -> SizedList a -> SizedList a append (N m :: Int m xs :: [a] xs) (N n :: Int n ys :: [a] ys) = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N (Int m Int -> Int -> Int forall a. Num a => a -> a -> a + Int n) ([a] -> SizedList a) -> [a] -> SizedList a forall a b. (a -> b) -> a -> b $ [a] xs [a] -> [a] -> [a] forall a. [a] -> [a] -> [a] ++ [a] ys head :: SizedList a -> a head :: SizedList a -> a head (N n :: Int n xs :: [a] xs) = case [a] xs of x :: a x : _ | Int n Int -> Int -> Bool forall a. Ord a => a -> a -> Bool > 0 -> a x _ -> String -> a forall a. HasCallStack => String -> a error "SizedList.head: empty list" tail :: SizedList a -> SizedList a tail :: SizedList a -> SizedList a tail (N n :: Int n xs :: [a] xs) = case [a] xs of _ : r :: [a] r | Int n Int -> Int -> Bool forall a. Ord a => a -> a -> Bool > 0 -> Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N (Int -> Int forall a. Enum a => a -> a pred Int n) [a] r _ -> String -> SizedList a forall a. HasCallStack => String -> a error "SizedList.tail: empty list" null :: SizedList a -> Bool null :: SizedList a -> Bool null (N n :: Int n _) = Int n Int -> Int -> Bool forall a. Eq a => a -> a -> Bool == 0 size :: SizedList a -> Int size :: SizedList a -> Int size (N n :: Int n _) = Int n reverse :: SizedList a -> SizedList a reverse :: SizedList a -> SizedList a reverse (N n :: Int n xs :: [a] xs) = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N Int n ([a] -> [a] forall a. [a] -> [a] List.reverse [a] xs) take :: Int -> SizedList a -> SizedList a take :: Int -> SizedList a -> SizedList a take i :: Int i original :: SizedList a original@(N n :: Int n xs :: [a] xs) | Int i Int -> Int -> Bool forall a. Ord a => a -> a -> Bool <= 0 = SizedList a forall a. SizedList a empty | Int i Int -> Int -> Bool forall a. Ord a => a -> a -> Bool >= Int n = SizedList a original | Bool otherwise = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N Int i ([a] -> SizedList a) -> [a] -> SizedList a forall a b. (a -> b) -> a -> b $ Int -> [a] -> [a] forall a. Int -> [a] -> [a] List.take Int i [a] xs drop :: Int -> SizedList a -> SizedList a drop :: Int -> SizedList a -> SizedList a drop i :: Int i original :: SizedList a original@(N n :: Int n xs :: [a] xs) | Int i Int -> Int -> Bool forall a. Ord a => a -> a -> Bool <= 0 = SizedList a original | Int i Int -> Int -> Bool forall a. Ord a => a -> a -> Bool >= Int n = SizedList a forall a. SizedList a empty | Bool otherwise = Int -> [a] -> SizedList a forall a. Int -> [a] -> SizedList a N (Int n Int -> Int -> Int forall a. Num a => a -> a -> a - Int i) ([a] -> SizedList a) -> [a] -> SizedList a forall a b. (a -> b) -> a -> b $ Int -> [a] -> [a] forall a. Int -> [a] -> [a] List.drop Int i [a] xs map :: (a -> b) -> SizedList a -> SizedList b map :: (a -> b) -> SizedList a -> SizedList b map f :: a -> b f (N n :: Int n xs :: [a] xs) = Int -> [b] -> SizedList b forall a. Int -> [a] -> SizedList a N Int n ((a -> b) -> [a] -> [b] forall a b. (a -> b) -> [a] -> [b] List.map a -> b f [a] xs)