dlist 0.7.1.2 → 0.8

raw patch · 6 files changed

+216/−61 lines, 6 filesdep ~QuickCheckdep ~basePVP ok

version bump matches the API change (PVP)

Dependency ranges changed: QuickCheck, base

API changes (from Hackage documentation)

Files

• ChangeLog.md +23/−3
• Data/DList.hs +71/−25
• LICENSE +1/−1
• README.md +54/−1
• dlist.cabal +12/−10
• tests/Main.hs +55/−21

@@ -2,6 +2,25 @@ Change Log ========== +Version 0.8 (2016-07-17) *Constitution Day in South Korea*+----------------------------------------------------------++#### New features++* Add pattern synonyms `Nil` and `Cons` for GHC >= 7.8+* Add `Semigroup` instance for GHC >= 8 (base >= 4.9)+* Use inflexible instance for `IsString` to improve support for overloaded+  strings ([Baldur Blöndal](https://github.com/Icelandjack))++#### Package changes++* Change QuickCheck upper bound from 2.9 to 2.10++#### Development changes++* Add `-Wall -Werror` testing+* Add testing for GHC 8.0.1 to Travis-CI+ Version 0.7.1.2 (2015-08-23) *International Day for the Remembrance of the Slave Trade and its Abolition* --------------------------------------------------------------------------------------------------------- @@ -20,9 +39,10 @@ Version 0.7.1 (2014-06-28) *100th Anniversary of the Assassination of Franz Ferdinand* -------------------------------------------------------------------------------------- -#### Package changes+#### New features -* Add `IsList` instance for GHC >= 7.8 ([Icelandjack](https://github.com/Icelandjack))+* Add `IsList` instance for GHC >= 7.8+  ([Baldur Blöndal](https://github.com/Icelandjack))  Version 0.7.0.1 (2014-03-24) *World Tuberculosis Day* -----------------------------------------------------@@ -34,7 +54,7 @@ Version 0.7 (2014-03-17) *St. Patrick's Day* -------------------------------------------- -#### Package changes+#### New features  * Add `NFData` instance (and `deepseq` dependency) * Add `IsString` instance

@@ -1,16 +1,16 @@ {-# OPTIONS_GHC -O2 #-} {-# OPTIONS_HADDOCK prune #-} {-# LANGUAGE CPP #-}-{-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE TypeFamilies #-} -- For the IsList and IsString instances+ #if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708--- For the IsList instance:-{-# LANGUAGE TypeFamilies #-}+{-# LANGUAGE PatternSynonyms, ViewPatterns #-} #endif  ----------------------------------------------------------------------------- -- | -- Module      :  Data.DList--- Copyright   :  (c) 2006-2009 Don Stewart, 2013-2014 Sean Leather+-- Copyright   :  (c) 2006-2009 Don Stewart, 2013-2016 Sean Leather -- License     :  See LICENSE file -- -- Maintainer  :  sean.leather@gmail.com@@ -21,30 +21,40 @@ -- ----------------------------------------------------------------------------- -module Data.DList (+module Data.DList -   DList+#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 800+  ( DList(Nil, Cons)+#else+  ( DList+#endif    -- * Construction-  ,fromList      -- :: [a] -> DList a-  ,toList        -- :: DList a -> [a]-  ,apply         -- :: DList a -> [a] -> [a]+  , fromList+  , toList+  , apply    -- * Basic functions-  ,empty         -- :: DList a-  ,singleton     -- :: a -> DList a-  ,cons          -- :: a -> DList a -> DList a-  ,snoc          -- :: DList a -> a -> DList a-  ,append        -- :: DList a -> DList a -> DList a-  ,concat        -- :: [DList a] -> DList a-  ,replicate     -- :: Int -> a -> DList a-  ,list          -- :: b -> (a -> DList a -> b) -> DList a -> b-  ,head          -- :: DList a -> a-  ,tail          -- :: DList a -> DList a-  ,unfoldr       -- :: (b -> Maybe (a, b)) -> b -> DList a-  ,foldr         -- :: (a -> b -> b) -> b -> DList a -> b-  ,map           -- :: (a -> b) -> DList a -> DList b+  , empty+  , singleton+  , cons+  , snoc+  , append+  , concat+  , replicate+  , list+  , head+  , tail+  , unfoldr+  , foldr+  , map +#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708 && __GLASGOW_HASKELL__ < 800+  -- * Pattern Synonyms+  , pattern Nil+  , pattern Cons+#endif+   ) where  import Prelude hiding (concat, foldr, map, head, tail, replicate)@@ -62,6 +72,10 @@ import Control.Applicative(Applicative(..)) #endif +#if MIN_VERSION_base(4,9,0)+import Data.Semigroup (Semigroup(..))+#endif+ #ifdef __GLASGOW_HASKELL__  import Text.Read (Lexeme(Ident), lexP, parens, prec, readPrec, readListPrec,@@ -111,6 +125,22 @@ toList      = ($[]) . unDL {-# INLINE toList #-} +#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708+-- | A unidirectional pattern synonym using 'toList' in a view pattern and+-- matching on @[]@+#if __GLASGOW_HASKELL__ >= 710+pattern Nil :: DList a+#endif+pattern Nil <- (toList -> [])++-- | A unidirectional pattern synonym using 'toList' in a view pattern and+-- matching on @x:xs@ such that you have the pattern @Cons x xs@+#if __GLASGOW_HASKELL__ >= 710+pattern Cons :: a -> [a] -> DList a+#endif+pattern Cons x xs <- (toList -> x:xs)+#endif+ -- | Apply a dlist to a list to get the underlying list with an extension -- -- > apply (fromList xs) ys = xs ++ ys@@ -223,7 +253,8 @@     {-# INLINE fmap #-}  instance Applicative DList where-    pure  = return+    pure  = singleton+    {-# INLINE pure #-}     (<*>) = ap  instance Alternative DList where@@ -240,7 +271,7 @@     = foldr (append . k) empty m   {-# INLINE (>>=) #-} -  return x = singleton x+  return   = pure   {-# INLINE return #-}    fail _   = empty@@ -283,7 +314,11 @@   rnf = rnf . toList   {-# INLINE rnf #-} -instance IsString (DList Char) where+-- This is _not_ a flexible instance to allow certain uses of overloaded+-- strings. See tests/OverloadedStrings.hs for an example and+-- https://git.haskell.org/ghc.git/commitdiff/b225b234a6b11e42fef433dcd5d2a38bb4b466bf+-- for the same change made to the IsString instance for lists.+instance a ~ Char => IsString (DList a) where   fromString = fromList   {-# INLINE fromString #-} @@ -296,3 +331,14 @@   {-# INLINE toList #-} #endif +#if MIN_VERSION_base(4,9,0)+instance Semigroup (DList a) where+  (<>) = append+  {-# INLINE (<>) #-}+  stimes n x+    | n < 0     = error "Data.DList.stimes: negative multiplier"+    | otherwise = rep n+    where+      rep 0 = empty+      rep i = x <> rep (pred i)+#endif

@@ -1,4 +1,4 @@-Copyright (c) 2006-2009 Don Stewart, 2013-2014 Sean Leather+Copyright (c) 2006-2009 Don Stewart, 2013-2016 Sean Leather  All rights reserved. 

@@ -1,6 +1,59 @@+# Difference Lists in Haskell+ [![Build Status](https://travis-ci.org/spl/dlist.png?branch=master)](https://travis-ci.org/spl/dlist) [![Hackage](https://budueba.com/hackage/dlist)](https://hackage.haskell.org/package/dlist) +## Summary+ 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.+See [ChangeLog.md](./ChangeLog.md) for recent changes.++## References++### Research++1. A novel representation of lists and its application to the function+   “reverse.” John Hughes. Information Processing Letters. Volume 22, Issue 3.+   1986-03. Pages 141-144.+  [[PDF](http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf)]++   This is the original source for a representation of lists as first-class functions.++### Basic Introduction++1. [Difference list](https://en.wikipedia.org/wiki/Difference_list). Wikipedia.++2. [Difference lists](https://wiki.haskell.org/Difference_list). Haskell.org Wiki.++3. [What is a DList?](https://stackoverflow.com/questions/3352418/what-is-a-dlist).+   Stack Overflow.++### Blogs and Discussion++1. [Using Difference Lists](http://logicaltypes.blogspot.com/2008/08/using-difference-lists.html).+   Douglas M. Auclair. 2008-08-13.++2. [A Sort of Difference](https://archive.is/20140131124629/http://web.archive.org/web/20080918101635/comonad.com/reader/2008/a-sort-of-difference/).+   Edward Kmett. 2008-09-18.++3. [Reference for technique wanted](http://thread.gmane.org/gmane.comp.lang.haskell.cafe/82827).+   Richard O'Keefe, et al. 2010-10-31.++4. [24 Days of Hackage: dlist](https://ocharles.org.uk/blog/posts/2012-12-14-24-days-of-hackage-dlist.html).+   Oliver Charles. 2012-12-14.++5. [Constructing a list in a Monad](https://www.joachim-breitner.de/blog/620-Constructing_a_list_in_a_Monad).+   Joachim Breitner. 2013-11-13.++6. [Demystifying DList](http://h2.jaguarpaw.co.uk/posts/demystifying-dlist/).+   ([On Reddit](https://www.reddit.com/r/haskell/comments/1w5duf/demystifying_dlist/)).+   Tom Ellis. 2014-01-24.++7. [keepEquals with Difference Lists](http://logicaltypes.blogspot.com/2014/06/keepequals-with-difference-lists.html),+   Douglas M. Auclair. 2014-06-21.++### Books++1. [Chapter 13. Data Structures](http://book.realworldhaskell.org/read/data-structures.html).+   Real World Haskell. 2008-12-05.

@@ -1,5 +1,5 @@ name:                   dlist-version:                0.7.1.2+version:                0.8 synopsis:               Difference lists description:   Difference lists are a list-like type supporting O(1) append. This is@@ -10,19 +10,20 @@ license-file:           LICENSE author:                 Don Stewart maintainer:             Sean Leather <sean.leather@gmail.com>-copyright:              2006-2009 Don Stewart, 2013-2014 Sean Leather+copyright:              2006-2009 Don Stewart, 2013-2016 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,-                        GHC==7.8.4,-                        GHC==7.10.2+tested-with:            GHC==7.0.4+                        GHC==7.2.2+                        GHC==7.4.2+                        GHC==7.6.3+                        GHC==7.8.4+                        GHC==7.10.3+                        GHC==8.0.1  source-repository head   type:                 git@@ -32,9 +33,9 @@   build-depends:                         base >= 4 && < 5,                         deepseq >= 1.1 && < 2-  ghc-options:          -Wall   extensions:           CPP   exposed-modules:      Data.DList+  ghc-options:          -Wall  test-suite test   type:                 exitcode-stdio-1.0@@ -43,4 +44,5 @@   build-depends:        dlist,                         base,                         Cabal,-                        QuickCheck >= 2.7 && < 2.9+                        QuickCheck >= 2.7 && < 2.10+  ghc-options:          -Wall

@@ -1,10 +1,13 @@ {-# OPTIONS_GHC -Wall #-} {-# LANGUAGE CPP #-} #if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708--- For the IsList test:-{-# LANGUAGE OverloadedLists #-}+{-# LANGUAGE OverloadedLists #-} -- For the IsList test+#if __GLASGOW_HASKELL__ == 708+{-# LANGUAGE PatternSynonyms #-} -- For pattern synonym use only in GHC 7.8 #endif+#endif + --------------------------------------------------------------------------------  module Main (main) where@@ -18,6 +21,13 @@  import Data.DList +import OverloadedStrings (testOverloadedStrings)++#if MIN_VERSION_base(4,9,0)+import Data.Semigroup (Semigroup(..))+import Data.List.NonEmpty (NonEmpty(..))+#endif+ --------------------------------------------------------------------------------  eqWith :: Eq b => (a -> b) -> (a -> b) -> a -> Bool@@ -92,35 +102,59 @@     test_fromList x = x == fromList [1,2,3]     test_toList [1,2,3] = True     test_toList _       = False++prop_patterns :: [Int] -> Bool+prop_patterns xs = case fromList xs of+  Nil       -> xs == []+  Cons y ys -> xs == (y:ys)+  _         -> False #endif +#if MIN_VERSION_base(4,9,0)+prop_Semigroup_append :: [Int] -> [Int] -> Bool+prop_Semigroup_append xs ys = xs <> ys == toList (fromList xs <> fromList ys)++prop_Semigroup_sconcat :: NonEmpty [Int] -> Bool+prop_Semigroup_sconcat xs = sconcat xs == toList (sconcat (fmap fromList xs))++prop_Semigroup_stimes :: Int -> [Int] -> Bool+prop_Semigroup_stimes n xs = stimes n xs == toList (stimes n (fromList xs))+#endif+ --------------------------------------------------------------------------------  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)+  [ ("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) #if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 708-  , ("IsList",        property prop_IsList)+  , ("IsList",            property prop_IsList)+  , ("patterns",          property prop_patterns) #endif+#if MIN_VERSION_base(4,9,0)+  , ("Semigroup <>",      property prop_Semigroup_append)+  , ("Semigroup sconcat", property prop_Semigroup_sconcat)+  , ("Semigroup stimes",  property prop_Semigroup_stimes)+#endif   ]  --------------------------------------------------------------------------------  main :: IO ()-main = quickCheck $ conjoin $ List.map (uncurry label) props-+main = do+  testOverloadedStrings+  quickCheck $ conjoin $ List.map (uncurry label) props