dlist 0.2 → 0.3
raw patch · 4 files changed
+87/−25 lines, 4 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
+ Data.DList: maybeReturn :: (MonadPlus m) => Maybe a -> m a
Files
- Data/DList.hs +30/−7
- README +1/−0
- dlist.cabal +7/−5
- tests/Properties.hs +49/−13
Data/DList.hs view
@@ -1,7 +1,7 @@ ----------------------------------------------------------------------------- -- | -- Module : Data.DList--- Copyright : (c) Don Stewart 2006+-- Copyright : (c) Don Stewart 2006-2007 -- License : BSD-style (see the file LICENSE) -- -- Maintainer : dons@cse.unsw.edu.au@@ -34,6 +34,9 @@ ,foldr -- :: (a -> b -> b) -> b -> DList a -> b ,map -- :: (a -> b) -> DList a -> DList b + -- * MonadPlus+ , maybeReturn+ ) where import Prelude hiding (concat, foldr, map, head, tail)@@ -51,36 +54,46 @@ -- | Converting a normal list to a dlist fromList :: [a] -> DList a fromList = DL . (++)+{-# INLINE fromList #-} -- | Converting a dlist back to a normal list toList :: DList a -> [a] toList = ($[]) . unDL+{-# INLINE toList #-} -- | Create a difference list containing no elements empty :: DList a empty = DL id+{-# INLINE empty #-} -- | Create difference list with given single element singleton :: a -> DList a singleton = DL . (:)+{-# INLINE singleton #-} -- | /O(1)/, Prepend a single element to a difference list+infixr `cons` cons :: a -> DList a -> DList a cons x xs = DL ((x:) . unDL xs)+{-# INLINE cons #-} -- | /O(1)/, Append a single element at a difference list+infixl `snoc` snoc :: DList a -> a -> DList a snoc xs x = DL (unDL xs . (x:))+{-# INLINE snoc #-} --- | Appending difference lists+-- | /O(1)/, Appending difference lists append :: DList a -> DList a -> DList a append xs ys = DL (unDL xs . unDL ys)+{-# INLINE append #-} --- | Concatenate difference lists+-- | /O(spine)/, Concatenate difference lists concat :: [DList a] -> DList a concat = List.foldr append empty+{-# INLINE concat #-} --- | /O(length dl)/, List elimination, head, tail+-- | /O(length dl)/, List elimination, head, tail. list :: b -> (a -> DList a -> b) -> DList a -> b list null cons dl = case toList dl of@@ -93,7 +106,7 @@ -- | Return the tail of the list tail :: DList a -> DList a-tail = list (error "Data.DList.tail: empty list") (curry snd) +tail = list (error "Data.DList.tail: empty list") (curry snd) -- | Unfoldr for difference lists unfoldr :: (b -> Maybe (a, b)) -> b -> DList a@@ -105,11 +118,12 @@ -- | Foldr over difference lists foldr :: (a -> b -> b) -> b -> DList a -> b foldr f b = List.foldr f b . toList+{-# INLINE foldr #-} --- | Map over difference lists+-- | Map over difference lists. map :: (a -> b) -> DList a -> DList b map f = foldr (cons . f) empty-+{-# INLINE map #-} instance Monoid (DList a) where mempty = empty@@ -117,6 +131,7 @@ instance Functor DList where fmap = map+ {-# INLINE fmap #-} instance Monad DList where m >>= k@@ -126,10 +141,18 @@ -- = List.foldr append empty . List.map k . toList $ m -- = List.foldr (append . k) empty . toList $ m = foldr (append . k) empty m+ {-# INLINE (>>=) #-} return x = singleton x+ {-# INLINE return #-}+ fail s = empty+ {-# INLINE fail #-} instance MonadPlus DList where mzero = empty mplus = append++-- Use this to convert Maybe a into DList a, or indeed into any other MonadPlus instance.+maybeReturn :: MonadPlus m => Maybe a -> m a+maybeReturn = maybe mzero return
README view
@@ -8,6 +8,7 @@ Running the testsuite: $ cd tests && runhaskell Properties.hs+ $ cd tests && ghc --make -O2 -ddump-simpl-stats Properties.hs -o prop && ./prop Author: Don Stewart
dlist.cabal view
@@ -1,12 +1,14 @@ Name: dlist-Version: 0.2-Description: Differences lists: lists supporting efficient append+Version: 0.3+Synopsis: Differences lists+Description: Differences lists: a list-like type supporting O(1) append Category: Data-Synopsis: Differences lists: lists supporting efficient append License: BSD3 License-file: LICENSE Author: Don Stewart -Maintainer: <dons@cse.unsw.edu.au>+Maintainer: dons@cse.unsw.edu.au Build-Depends: base-ghc-options: -O+Ghc-options: -O2 Exposed-modules: Data.DList+Homepage: http://www.cse.unsw.edu.au/~dons/dlist.html+extra-source-files: README tests/Properties.hs tests/Parallel.hs
tests/Properties.hs view
@@ -1,7 +1,9 @@ -import qualified Prelude as P-import Prelude hiding (concat,map,head,tail)-import Data.List hiding (concat,map,head,tail)+import qualified Prelude as P+import qualified Data.List as P (unfoldr)+import Prelude hiding (concat,map,head,tail,foldr,map)+import Data.List hiding (concat,map,head,tail,unfoldr,foldr,map)+import Text.Show.Functions import Parallel import Data.DList@@ -29,14 +31,48 @@ prop_tail xs = not (null xs) ==> (P.tail xs) == (toList . tail . fromList) xs where _ = xs :: T -main = pRun 2 500 [ ("model", pDet prop_model)- , ("empty", pDet prop_empty)- , ("singleton", pDet prop_singleton)- , ("cons", pDet prop_cons)- , ("snoc", pDet prop_snoc)- , ("append", pDet prop_append)- , ("concat", pDet prop_concat)- , ("head", pDet prop_head)- , ("tail", pDet prop_tail)- ]+prop_unfoldr f x n = n >= 0 ==> take n (P.unfoldr f x)+ == take n (toList $ unfoldr f x)+ where _ = x :: Int+ _ = f :: Int -> Maybe (Int,Int) +prop_foldr f x xs = (P.foldr f x xs) == (foldr f x (fromList xs))+ where _ = x :: Int+ _ = f :: Int -> Int -> Int++prop_map f xs = (P.map f xs) == (toList $ map f (fromList xs))+ where _ = f :: Int -> Int++prop_map_fusion f g xs = (P.map f . P.map g $ xs)+ == (toList $ map f . map g $ fromList xs)+ where _ = f :: Int -> Int++--+-- run 8 threads simultaneously+--+main = pRun 8 300+ [ ("model", pDet prop_model)+ , ("empty", pDet prop_empty)+ , ("singleton", pDet prop_singleton)+ , ("cons", pDet prop_cons)+ , ("snoc", pDet prop_snoc)+ , ("append", pDet prop_append)+ , ("concat", pDet prop_concat)+ , ("head", pDet prop_head)+ , ("tail", pDet prop_tail)+ , ("unfoldr", pDet prop_unfoldr)+ , ("foldr", pDet prop_foldr)+ , ("map", pDet prop_map)+ , ("map fusion",pDet prop_map)+ ]+++------------------------------------------------------------------------+--+-- missing QC instances+--++instance Arbitrary a => Arbitrary (Maybe a) where+ arbitrary = do a <- arbitrary ; elements [Nothing, Just a]+ coarbitrary Nothing = variant 0+ coarbitrary _ = variant 1 -- ok?