dlist 0.5 → 0.6
raw patch · 9 files changed
+301/−316 lines, 9 filesdep +Cabaldep +QuickCheckdep +dlistdep ~basenew-uploader
Dependencies added: Cabal, QuickCheck, dlist
Dependency ranges changed: base
Files
- ChangeLog.md +32/−0
- Data/DList.hs +118/−40
- LICENSE +1/−1
- README +0/−15
- README.md +5/−0
- dlist.cabal +38/−29
- tests/Main.hs +107/−0
- tests/Parallel.hs +0/−148
- tests/Properties.hs +0/−83
+ ChangeLog.md view
@@ -0,0 +1,32 @@++Change Log+==========++Version 0.6 (2013-11-29) *Black Friday*+---------------------------------------++#### Development changes++* Maintenance and development taken over by Sean Leather+* Migrate repository from http://code.haskell.org/~dons/code/dlist/ to+ https://github.com/spl/dlist++#### Package changes++* Stop supporting `base < 2`+* Fix tests and use `cabal test`+* Add scripts for running `hpc`+* Update documentation++#### New features++* New type class instances: `Eq`, `Ord`, `Read`, `Show`, `Alternative`,+ and `Foldable`+* New function `apply` to use instead of `unDL`++#### Deprecations++* Deprecate DList constructor and record selector to make it abstract+ (see [#4](https://github.com/spl/dlist/issues/4))+* Deprecate `maybeReturn` which is not directly relevant to dlists+
Data/DList.hs view
@@ -1,24 +1,29 @@+{-# OPTIONS_GHC -Wall -O2 #-}+{-# OPTIONS_HADDOCK prune #-}+{-# LANGUAGE CPP #-}+ ----------------------------------------------------------------------------- -- | -- Module : Data.DList--- Copyright : (c) Don Stewart 2006-2007--- License : BSD-style (see the file LICENSE)+-- Copyright : (c) Don Stewart 2006-2009, (c) Sean Leather 2013+-- License : See LICENSE file ----- Maintainer : dons@cse.unsw.edu.au--- Stability : experimental--- Portability : portable (Haskell 98)+-- Maintainer : sean.leather@gmail.com+-- Stability : stable+-- Portability : portable ----- Difference lists: a data structure for O(1) append on lists.+-- Difference lists: a data structure for /O(1)/ append on lists. -- ----------------------------------------------------------------------------- module Data.DList ( - DList(..) -- abstract, instance Monoid, Functor, Applicative, Monad, MonadPlus+ DList(..) -- * Construction ,fromList -- :: [a] -> DList a ,toList -- :: DList a -> [a]+ ,apply -- :: DList a -> [a] -> [a] -- * Basic functions ,empty -- :: DList a@@ -35,33 +40,40 @@ ,foldr -- :: (a -> b -> b) -> b -> DList a -> b ,map -- :: (a -> b) -> DList a -> DList b - -- * MonadPlus- , maybeReturn+ ,maybeReturn ) where import Prelude hiding (concat, foldr, map, head, tail, replicate) import qualified Data.List as List-import Control.Monad+import Control.Monad as M import Data.Monoid+import Data.Function (on) -#ifdef APPLICATIVE_IN_BASE-import Control.Applicative(Applicative(..))+import Data.Foldable (Foldable)+import qualified Data.Foldable as F++#ifdef __GLASGOW_HASKELL__+import Text.Read (Lexeme(Ident), lexP, parens, prec, readPrec, readListPrec,+ readListPrecDefault) #endif --- | A difference list is a function that given a list, returns the--- original contents of the difference list prepended at the given list+import Control.Applicative(Applicative(..), Alternative, (<|>))+import qualified Control.Applicative (empty)++-- | A difference list is a function that, given a list, returns the original+-- contents of the difference list prepended to the given list. ----- This structure supports /O(1)/ append and snoc operations on lists,--- making it very useful for append-heavy uses, such as logging and--- pretty printing.+-- This structure supports /O(1)/ append and snoc operations on lists, making it+-- very useful for append-heavy uses (esp. left-nested uses of 'List.++'), such+-- as logging and pretty printing. ----- For example, using DList as the state type when printing a tree with--- the Writer monad+-- Here is an example using DList as the state type when printing a tree with+-- the Writer monad: -- -- > import Control.Monad.Writer -- > import Data.DList--- > +-- > -- > data Tree a = Leaf a | Branch (Tree a) (Tree a) -- > -- > flatten_writer :: Tree x -> DList x@@ -71,88 +83,122 @@ -- > flatten (Branch x y) = flatten x >> flatten y -- newtype DList a = DL { unDL :: [a] -> [a] }+{-# DEPRECATED DL "It will be removed in dlist-v0.7 (see <https://github.com/spl/dlist/issues/4 #4>)." #-}+{-# DEPRECATED unDL "It will be removed in dlist-v0.7. Use 'apply' instead." #-} --- | Converting a normal list to a dlist+-- | Convert a list to a dlist fromList :: [a] -> DList a fromList = DL . (++) {-# INLINE fromList #-} --- | Converting a dlist back to a normal list+-- | Convert a dlist to a list toList :: DList a -> [a] toList = ($[]) . unDL {-# INLINE toList #-} --- | Create a difference list containing no elements+-- | Apply a dlist to a list to get the underlying list with an extension+--+-- > apply (fromList xs) ys = xs ++ ys+apply :: DList a -> [a] -> [a]+apply = unDL++-- | Create a dlist containing no elements empty :: DList a empty = DL id {-# INLINE empty #-} --- | Create difference list with given single element+-- | Create dlist with a single element singleton :: a -> DList a singleton = DL . (:) {-# INLINE singleton #-} --- | /O(1)/, Prepend a single element to a difference list+-- | /O(1)/. Prepend a single element to a dlist 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+-- | /O(1)/. Append a single element to a dlist infixl `snoc` snoc :: DList a -> a -> DList a snoc xs x = DL (unDL xs . (x:)) {-# INLINE snoc #-} --- | /O(1)/, Appending difference lists+-- | /O(1)/. Append dlists append :: DList a -> DList a -> DList a append xs ys = DL (unDL xs . unDL ys) {-# INLINE append #-} --- | /O(spine)/, Concatenate difference lists+-- | /O(spine)/. Concatenate dlists concat :: [DList a] -> DList a concat = List.foldr append empty {-# INLINE concat #-} --- | /O(n)/, Create a difference list of the given number of elements+-- | /O(n)/. Create a dlist of the given number of elements replicate :: Int -> a -> DList a replicate n x = DL $ \xs -> let go m | m <= 0 = xs | otherwise = x : go (m-1) in go n {-# INLINE replicate #-} --- | /O(length dl)/, List elimination, head, tail.+-- | /O(n)/. List elimination for dlists list :: b -> (a -> DList a -> b) -> DList a -> b list nill consit dl = case toList dl of [] -> nill (x : xs) -> consit x (fromList xs) --- | Return the head of the list+-- | /O(n)/. Return the head of the dlist head :: DList a -> a-head = list (error "Data.DList.head: empty list") const+head = list (error "Data.DList.head: empty dlist") const --- | Return the tail of the list+-- | /O(n)/. Return the tail of the dlist tail :: DList a -> DList a-tail = list (error "Data.DList.tail: empty list") (flip const)+tail = list (error "Data.DList.tail: empty dlist") (flip const) --- | Unfoldr for difference lists+-- | /O(n)/. Unfoldr for dlists unfoldr :: (b -> Maybe (a, b)) -> b -> DList a unfoldr pf b = case pf b of Nothing -> empty Just (a, b') -> cons a (unfoldr pf b') --- | Foldr over difference lists+-- | /O(n)/. 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.+-- | /O(n)/. Map over difference lists. map :: (a -> b) -> DList a -> DList b map f = foldr (cons . f) empty {-# INLINE map #-} +instance Eq a => Eq (DList a) where+ (==) = (==) `on` toList++instance Ord a => Ord (DList a) where+ compare = compare `on` toList++-- The Read and Show instances were adapted from Data.Sequence.++instance Read a => Read (DList a) where+#ifdef __GLASGOW_HASKELL__+ readPrec = parens $ prec 10 $ do+ Ident "fromList" <- lexP+ dl <- readPrec+ return (fromList dl)+ readListPrec = readListPrecDefault+#else+ readsPrec p = readParen (p > 10) $ \r -> do+ ("fromList", s) <- lex r+ (dl, t) <- reads s+ return (fromList dl, t)+#endif++instance Show a => Show (DList a) where+ showsPrec p dl = showParen (p > 10) $+ showString "fromList " . shows (toList dl)+ instance Monoid (DList a) where mempty = empty mappend = append@@ -161,12 +207,14 @@ fmap = map {-# INLINE fmap #-} -#ifdef APPLICATIVE_IN_BASE instance Applicative DList where pure = return (<*>) = ap-#endif +instance Alternative DList where+ empty = empty+ (<|>) = append+ instance Monad DList where m >>= k -- = concat (toList (fmap k m))@@ -187,6 +235,36 @@ mzero = empty mplus = append --- Use this to convert Maybe a into DList a, or indeed into any other MonadPlus instance.+instance Foldable DList where+ fold = mconcat . toList+ {-# INLINE fold #-}++ foldMap f = F.foldMap f . toList+ {-# INLINE foldMap #-}++ foldr f x = List.foldr f x . toList+ {-# INLINE foldr #-}++ foldl f x = List.foldl f x . toList+ {-# INLINE foldl #-}++ foldr1 f = List.foldr1 f . toList+ {-# INLINE foldr1 #-}++ foldl1 f = List.foldl1 f . toList+ {-# INLINE foldl1 #-}++-- CPP: foldl', foldr' added to Foldable in 7.6.1+-- http://www.haskell.org/ghc/docs/7.6.1/html/users_guide/release-7-6-1.html+#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 706+ foldl' f x = List.foldl' f x . toList+ {-# INLINE foldl' #-}++ foldr' f x = F.foldr' f x . toList+ {-# INLINE foldr' #-}+#endif+ maybeReturn :: MonadPlus m => Maybe a -> m a maybeReturn = maybe mzero return+{-# DEPRECATED maybeReturn "It will be removed in dlist-v0.7." #-}+
LICENSE view
@@ -1,4 +1,4 @@-Copyright Don Stewart 2006.+Copyright (c) Don Stewart 2006-2009, (c) Sean Leather 2013 All rights reserved.
− README
@@ -1,15 +0,0 @@-DLists: a Haskell list type supporting O(1) append and snoc--Build instructions:-- $ runhaskell Setup.lhs configure --prefix=$HOME- $ runhaskell Setup.lhs build- $ runhaskell Setup.lhs install--Running the testsuite:- $ cd tests && runhaskell Properties.hs- $ cd tests && ghc --make -O2 -ddump-simpl-stats Properties.hs -o prop && ./prop--Author:- Don Stewart- http://www.cse.unsw.edu.au/~dons
+ README.md view
@@ -0,0 +1,5 @@+[](https://travis-ci.org/spl/dlist)++The Haskell `dlist` package defines a list-like type supporting O(1) append and snoc operations.++See the [ChangeLog.md](https://github.com/spl/dlist/blob/master/ChangeLog.md) file for recent changes.
dlist.cabal view
@@ -1,31 +1,40 @@-Name: dlist-Version: 0.5-Synopsis: Differences lists-Description: - Differences lists: a list-like type supporting O(1) append.- This is particularly useful for efficient logging and pretty- printing, (e.g. with the Writer monad), where list append - quickly becomes too expensive.-Category: Data-License: BSD3-License-file: LICENSE-Author: Don Stewart -Maintainer: dons@galois.com-Copyright: 2006-9 Don Stewart-Homepage: http://code.haskell.org/~dons/code/dlist/-extra-source-files: README tests/Properties.hs tests/Parallel.hs-build-type: Simple-cabal-version: >= 1.2+name: dlist+version: 0.6+synopsis: Difference lists+description:+ Difference lists are a list-like type supporting O(1) append. This is+ particularly useful for efficient logging and pretty printing (e.g. with the+ Writer monad), where list append quickly becomes too expensive.+category: Data+license: BSD3+license-file: LICENSE+author: Don Stewart+maintainer: Sean Leather <sean.leather@gmail.com>+copyright: 2006-2009 Don Stewart, 2013 Sean Leather+homepage: https://github.com/spl/dlist+bug-reports: https://github.com/spl/dlist/issues+extra-source-files: README.md,+ ChangeLog.md+build-type: Simple+cabal-version: >= 1.9.2+tested-with: GHC==7.0.4, GHC==7.2.2, GHC==7.4.2, GHC==7.6.3 -flag applicative-in-base+source-repository head+ type: git+ location: git://github.com/spl/dlist.git -Library- Build-Depends: base- Ghc-options: -O2 -Wall- Extensions: CPP- Exposed-modules: Data.DList- if flag(applicative-in-base)- build-depends: base >= 2.0 && < 5- cpp-options: -DAPPLICATIVE_IN_BASE- else- build-depends: base < 2.0+library+ build-depends: base >= 2 && < 5+ ghc-options: -Wall+ extensions: CPP+ exposed-modules: Data.DList++test-suite test+ type: exitcode-stdio-1.0+ main-is: Main.hs+ hs-source-dirs: tests+ build-depends: dlist,+ base,+ Cabal,+ QuickCheck >= 2.6 && < 2.7+
+ tests/Main.hs view
@@ -0,0 +1,107 @@+{-# OPTIONS_GHC -Wall #-}++--------------------------------------------------------------------------------++module Main (main) where++--------------------------------------------------------------------------------++import Prelude hiding (concat, foldr, head, map, replicate, tail)+import qualified Data.List as List+import Text.Show.Functions ()+import Test.QuickCheck++import Data.DList++--------------------------------------------------------------------------------++eqWith :: Eq b => (a -> b) -> (a -> b) -> a -> Bool+eqWith f g x = f x == g x++eqOn :: Eq b => (a -> Bool) -> (a -> b) -> (a -> b) -> a -> Property+eqOn c f g x = c x ==> f x == g x++--------------------------------------------------------------------------------++prop_model :: [Int] -> Bool+prop_model = eqWith id (toList . fromList)++prop_empty :: Bool+prop_empty = ([] :: [Int]) == (toList empty :: [Int])++prop_singleton :: Int -> Bool+prop_singleton = eqWith (:[]) (toList . singleton)++prop_cons :: Int -> [Int] -> Bool+prop_cons c = eqWith (c:) (toList . cons c . fromList)++prop_snoc :: [Int] -> Int -> Bool+prop_snoc xs c = xs ++ [c] == toList (snoc (fromList xs) c)++prop_append :: [Int] -> [Int] -> Bool+prop_append xs ys = xs ++ ys == toList (fromList xs `append` fromList ys)++prop_concat :: [[Int]] -> Bool+prop_concat = eqWith List.concat (toList . concat . List.map fromList)++-- The condition reduces the size of replications and thus the eval time.+prop_replicate :: Int -> Int -> Property+prop_replicate n =+ eqOn (const (n < 100)) (List.replicate n) (toList . replicate n)++prop_head :: [Int] -> Property+prop_head = eqOn (not . null) List.head (head . fromList)++prop_tail :: [Int] -> Property+prop_tail = eqOn (not . null) List.tail (toList . tail . fromList)++prop_unfoldr :: (Int -> Maybe (Int, Int)) -> Int -> Int -> Property+prop_unfoldr f n =+ eqOn (const (n >= 0)) (take n . List.unfoldr f) (take n . toList . unfoldr f)++prop_foldr :: (Int -> Int -> Int) -> Int -> [Int] -> Bool+prop_foldr f x = eqWith (List.foldr f x) (foldr f x . fromList)++prop_map :: (Int -> Int) -> [Int] -> Bool+prop_map f = eqWith (List.map f) (toList . map f . fromList)++prop_map_fusion :: (Int -> Int) -> (a -> Int) -> [a] -> Bool+prop_map_fusion f g =+ eqWith (List.map f . List.map g) (toList . map f . map g . fromList)++prop_show_read :: [Int] -> Bool+prop_show_read = eqWith id (read . show)++prop_read_show :: [Int] -> Bool+prop_read_show x = eqWith id (show . f . read) $ "fromList " ++ show x+ where+ f :: DList Int -> DList Int+ f = id++--------------------------------------------------------------------------------++props :: [(String, Property)]+props =+ [ ("model", property prop_model)+ , ("empty", property prop_empty)+ , ("singleton", property prop_singleton)+ , ("cons", property prop_cons)+ , ("snoc", property prop_snoc)+ , ("append", property prop_append)+ , ("concat", property prop_concat)+ , ("replicate", property prop_replicate)+ , ("head", property prop_head)+ , ("tail", property prop_tail)+ , ("unfoldr", property prop_unfoldr)+ , ("foldr", property prop_foldr)+ , ("map", property prop_map)+ , ("map fusion", property (prop_map_fusion (+1) (+1)))+ , ("read . show", property prop_show_read)+ , ("show . read", property prop_read_show)+ ]++--------------------------------------------------------------------------------++main :: IO ()+main = quickCheck $ conjoin $ List.map (uncurry label) props+
− tests/Parallel.hs
@@ -1,148 +0,0 @@--------------------------------------------------------------------------------- |--- Module : Test.QuickCheck.Parallel--- Copyright : (c) Don Stewart 2006--- License : BSD-style (see the file LICENSE)--- --- Maintainer : dons@cse.unsw.edu.au--- Stability : experimental--- Portability : non-portable (uses Control.Exception, Control.Concurrent)------ A parallel batch driver for running QuickCheck on threaded or SMP systems.--- See the /Example.hs/ file for a complete overview.-----module Parallel (- module Test.QuickCheck,- pRun,- pDet,- pNon- ) where--import Test.QuickCheck-import Data.List-import Control.Concurrent-import Control.Exception hiding (evaluate)-import System.Random-import System.IO (hFlush,stdout)-import Text.Printf--type Name = String-type Depth = Int-type Test = (Name, Depth -> IO String)---- | Run a list of QuickCheck properties in parallel chunks, using--- 'n' Haskell threads (first argument), and test to a depth of 'd'--- (second argument). Compile your application with '-threaded' and run--- with the SMP runtime's '-N4' (or however many OS threads you want to--- donate), for best results.------ > import Test.QuickCheck.Parallel--- >--- > do n <- getArgs >>= readIO . head--- > pRun n 1000 [ ("sort1", pDet prop_sort1) ]------ Will run 'n' threads over the property list, to depth 1000.----pRun :: Int -> Int -> [Test] -> IO ()-pRun n depth tests = do- chan <- newChan- ps <- getChanContents chan- work <- newMVar tests-- forM_ [1..n] $ forkIO . thread work chan-- let wait xs i- | i >= n = return () -- done- | otherwise = case xs of- Nothing : xs -> wait xs $! i+1- Just s : xs -> putStr s >> hFlush stdout >> wait xs i- wait ps 0-- where- thread :: MVar [Test] -> Chan (Maybe String) -> Int -> IO ()- thread work chan me = loop- where- loop = do- job <- modifyMVar work $ \jobs -> return $ case jobs of- [] -> ([], Nothing)- (j:js) -> (js, Just j)- case job of- Nothing -> writeChan chan Nothing -- done- Just (name,prop) -> do- v <- prop depth- writeChan chan . Just $ printf "%d: %-25s: %s" me name v- loop----- | Wrap a property, and run it on a deterministic set of data-pDet :: Testable a => a -> Int -> IO String-pDet a n = mycheck Det defaultConfig- { configMaxTest = n- , configEvery = \n args -> unlines args } a---- | Wrap a property, and run it on a non-deterministic set of data-pNon :: Testable a => a -> Int -> IO String-pNon a n = mycheck NonDet defaultConfig- { configMaxTest = n- , configEvery = \n args -> unlines args } a--data Mode = Det | NonDet----------------------------------------------------------------------------mycheck :: Testable a => Mode -> Config -> a -> IO String-mycheck Det config a = do- let rnd = mkStdGen 99 -- deterministic- mytests config (evaluate a) rnd 0 0 []--mycheck NonDet config a = do- rnd <- newStdGen -- different each run- mytests config (evaluate a) rnd 0 0 []--mytests :: Config -> Gen Result -> StdGen -> Int -> Int -> [[String]] -> IO String-mytests config gen rnd0 ntest nfail stamps- | ntest == configMaxTest config = do done "OK," ntest stamps- | nfail == configMaxFail config = do done "Arguments exhausted after" ntest stamps- | otherwise = do- case ok result of- Nothing ->- mytests config gen rnd1 ntest (nfail+1) stamps- Just True ->- mytests config gen rnd1 (ntest+1) nfail (stamp result:stamps)- Just False ->- return ( "Falsifiable after "- ++ show ntest- ++ " tests:\n"- ++ unlines (arguments result)- )- where- result = generate (configSize config ntest) rnd2 gen- (rnd1,rnd2) = split rnd0--done :: String -> Int -> [[String]] -> IO String-done mesg ntest stamps =- return ( mesg ++ " " ++ show ntest ++ " tests" ++ table )- where- table = display- . map entry- . reverse- . sort- . map pairLength- . group- . sort- . filter (not . null)- $ stamps-- display [] = ".\n"- display [x] = " (" ++ x ++ ").\n"- display xs = ".\n" ++ unlines (map (++ ".") xs)-- pairLength xss@(xs:_) = (length xss, xs)- entry (n, xs) = percentage n ntest- ++ " "- ++ concat (intersperse ", " xs)-- percentage n m = show ((100 * n) `div` m) ++ "%"--forM_ = flip mapM_
− tests/Properties.hs
@@ -1,83 +0,0 @@--import qualified Prelude as P-import qualified Data.List as P (unfoldr)-import Prelude hiding (concat,map,head,tail,foldr,map,replicate)-import Data.List hiding (concat,map,head,tail,unfoldr,foldr,map,replicate)-import Text.Show.Functions--import Parallel-import Data.DList--type T = [Int]--prop_model x = (toList . fromList $ (x :: T)) == id x--prop_empty = ([] :: T) == (toList empty :: T)--prop_singleton c = ([c] :: T) == toList (singleton c)--prop_cons c xs = (c : xs :: T) == toList (cons c (fromList xs))--prop_snoc xs c = (xs ++ [c] :: T) == toList (snoc (fromList xs) c)--prop_append xs ys = (xs ++ ys :: T) == toList (append (fromList xs) (fromList ys))--prop_concat zss = (P.concat zss) == toList (concat (P.map fromList zss))- where _ = zss :: [T]--prop_replicate n x = (P.replicate n x :: T) == toList (replicate n x)--prop_head xs = not (null xs) ==> (P.head xs) == head (fromList xs)- where _ = xs :: T--prop_tail xs = not (null xs) ==> (P.tail xs) == (toList . tail . fromList) xs- where _ = xs :: T--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)- , ("replicate", pDet prop_replicate)- , ("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?- -}