{-# 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 (Show, Eq, Ord, Typeable, Data)
fromList :: [a] -> SizedList a
fromList xs = N (length xs) xs
toList :: SizedList a -> [a]
toList (N _ xs) = xs
empty :: SizedList a
empty = N 0 []
singleton :: a -> SizedList a
singleton x = N 1 [x]
cons :: a -> SizedList a -> SizedList a
cons x (N n xs) = N (succ n) $ x : xs
append :: SizedList a -> SizedList a -> SizedList a
append (N m xs) (N n ys) = N (m + n) $ xs ++ ys
head :: SizedList a -> a
head (N n xs) = case xs of
x : _ | n > 0 -> x
_ -> error "SizedList.head: empty list"
tail :: SizedList a -> SizedList a
tail (N n xs) = case xs of
_ : r | n > 0 -> N (pred n) r
_ -> error "SizedList.tail: empty list"
null :: SizedList a -> Bool
null (N n _) = n == 0
size :: SizedList a -> Int
size (N n _) = n
reverse :: SizedList a -> SizedList a
reverse (N n xs) = N n (List.reverse xs)
take :: Int -> SizedList a -> SizedList a
take i original@(N n xs)
| i <= 0 = empty
| i >= n = original
| otherwise = N i $ List.take i xs
drop :: Int -> SizedList a -> SizedList a
drop i original@(N n xs)
| i <= 0 = original
| i >= n = empty
| otherwise = N (n - i) $ List.drop i xs
map :: (a -> b) -> SizedList a -> SizedList b
map f (N n xs) = N n (List.map f xs)