packages feed

EdisonAPI 1.2.2.1 → 1.3.3.2

raw patch · 8 files changed

Files

+ CHANGES.md view
@@ -0,0 +1,118 @@+# Edison++Changelog of EdisonAPI and EdisonCore.++[Latest CHANGES.md](https://github.com/robdockins/edison/blob/master/CHANGES.md)++## 1.3.3.2+* Compatibility with GHC 9.10 and 9.12++## 1.3.3.1+* Remove mtl dependency (removed unnecessary imports which were incompatible with mtl 2.3)+* Fix implementation of little-endian PatriciaTrees++## 1.3.3+* Updates to handle MonadFail changes in GHC 8.x+* Updates to fix compile issues in GHC 9++## 1.3.2.1+* Fix compile problems on GHC 7.10++## 1.3.2+* Add Semigroup instances for all types that previously had Monoid instances.+* Remove use of depreciated functions in Data.Edison.Assoc.StandardMap++## 1.3.1+* Remove Arbitrary and Coarbitrary instances for Data.Set+     and Data.Map.  These are now provided by QuickCheck >= 2.8.2++## 1.3+* Updates to compile with GHC 7.10+    - Added Applicative and Alternative instances as required+    - Disambiguate the types of some operations+    - Resolve namespace clashes+* Added stack.yaml file to build with stack++## 1.2.2+  * Update edison-core to use QuickCheck version 2.*+  * Likewise update the test suite++## 1.2.1.3+* Minor fix to the StandardMap module to handle the API change in GHC 6.10++## 1.2.1.2+* Build system changes to remove mostly-superfulous dependency on+    haskell98, and to force dependence on the 1.x branch of QuickCheck.++## 1.2.1.1+* Build system changes to make GHC 6.8 and cabal >= 1.2.2 happy++## 1.2.1+* New sequence implementation based on Finger Trees+* Add the 'Measured' class to the Data.Edison.Prelude+* Addition of methods to EnumSet to project to a bit-encoded word and to+    create an EnumSet from a bit-encoded word+* Additional minor changes to EnumSet+* Fix a boneheaded mistake I made where I claimed most of Edison was+    licensed under BSD3, when it is in fact licensed under the MIT license.+    The practical differences are minor, and I hope this will not cause too+    many problems.++## 1.2.0.1+* Change use more efficient operations for StandardSet.{filterGT,filterLT}+    and StandardMap.{filterLE,filterGE,partitionLE_GT,partitionLT_GE}++## 1.2 final+* Fix documentation for sequences to reflect correct+    time complexities++## 1.2rc4+* introduce strict/strictWith operations for all APIs+* add Ord* instances for PatriciaLoMap and TernaryTrie+* add David F. Place's EnumSet implementation+* complete the FiniteMap unit test coverage and fix a bunch+    of bugs in finite map implementations+* add 'symmetricDifference' to Collection and+    Associated Collection APIs+* add Ord instances for data structures+* add Monoid instances for data structures+++## 1.2rc3+* introduce the ambiguous/unambiguous concept and document+    all API operations+* factor out methods which "mirror" superclass methods and+    make them alises instead+* add lookupAndDelete* methods to associated collections+* change the type of adjustOrDelete* in associated collections+* rename subset/subsetEq to properSubset/subset+* add matching Read and Show instances for all concrete datastructures+* add properSubmap{By} submap{By} and sameMap{By} to the+    associated collection API+* add Eq instances for concrete associated collections+* break out the test suite into a separate sub-package+++## 1.2rc2+* add strict variants of all folds and reduces+* reverse argument orders to 'rcons' and 'lookup*' in Sequence+* add symbolic operators for lcons, rcons, append, and lookup+    from the Sequence API+* add symbolic operators for subsetEq, difference, intersection+    and union from the set API+* rename 'single' to 'singleton' in all APIs+* reaame 'intersect' to 'intersection' in Collection and+    Associated Collection APIs+* add 'adjustOrInsert' to the Associated Collection API+++## 1.2rc1+* modules re-organized into a hierarchy+* user's guide distributed throughout source code as Haddock comments+* use cabal for build system+* add Data.Edison module to re-export typeclasses+* reorder 'lookup*' and 'find*' methods for+    Collections and Associated Collections+* add 'unsafeMapMonotonic' to main Collection API+* organize QuickCheck properties into a full test suite+* add a 'structuralInvariant' method to all APIs, for unit testing
EdisonAPI.cabal view
@@ -1,27 +1,35 @@ Build-type:     Simple Name:           EdisonAPI-Version:        1.2.2.1-License:        OtherLicense+Cabal-Version:  >= 1.10+Version:        1.3.3.2+License:        MIT License-File:   COPYRIGHT Author:         Chris Okasaki Maintainer:     robdockins AT fastmail DOT fm-Synopsis:       A library of efficent, purely-functional data structures (API)+Synopsis:       A library of efficient, purely-functional data structures (API) Category:       Data Structures-Homepage:	http://rwd.rdockins.name/edison/home/+Homepage:       https://github.com/robdockins/edison Stability:      Stable Description:    Edison is a library of purely functional data structures written by    Chris Okasaki.  It is named after Thomas Alva Edison and for the-   mnemonic value EDiSon (Efficent Data Structures).+   mnemonic value EDiSon (Efficient Data Structures).    Edison provides several families of abstractions, each with    multiple implementations.  The main abstractions provided by Edison are:    Sequences such as stacks, queues, and dequeues;    Collections such as sets, bags and heaps; and    Associative Collections such as finite maps and priority queues-   where the priority and element are distinct.+    where the priority and element are distinct.+Extra-Source-Files: CHANGES.md -Hs-Source-Dirs: src-Exposed-modules:+Source-Repository head+  Type: git+  Location: https://github.com/robdockins/edison/+  Subdir: edison-api++Library+  Hs-Source-Dirs: src+  Exposed-modules:      Data.Edison      Data.Edison.Prelude      Data.Edison.Sym@@ -30,11 +38,13 @@      Data.Edison.Coll.Utils      Data.Edison.Seq      Data.Edison.Seq.ListSeq-Build-Depends:-     base >= 2.0 && < 5,-     mtl >= 1.0-Extensions:+  Build-Depends:+     base >= 4.12 && < 4.22+  if impl(ghc < 8.0)+    build-depends: fail < 5+  Default-Language: Haskell2010+  Default-Extensions:      MultiParamTypeClasses      FunctionalDependencies      UndecidableInstances-Ghc-Options: -funbox-strict-fields -fwarn-incomplete-patterns+  Ghc-Options: -funbox-strict-fields -fwarn-incomplete-patterns
src/Data/Edison.hs view
@@ -143,7 +143,7 @@ --   information.  Unless otherwise stated, these are amortized time complexities, assuming --   persistent usage of the datastructure.  Much of this data comes from: -----   Martin Holters. /Efficent Data Structures in a Lazy Functional Language/.  Master's Thesis.+--   Martin Holters. /Efficient Data Structures in a Lazy Functional Language/.  Master's Thesis. --   Chalmers University of Technology, Sweden. 2003. -- --   /Notes on unsafe functions:/
src/Data/Edison/Assoc.hs view
@@ -44,7 +44,7 @@     FiniteMap(..),     OrdFiniteMap, -    -- * Specilizations of submap operations+    -- * Specializations of submap operations     submap,     properSubmap,     sameMap,@@ -71,6 +71,8 @@  import Prelude hiding (null,map,lookup,foldr,foldl,foldr1,foldl1,filter) +import qualified Control.Monad.Fail as Fail+ import Data.Edison.Prelude  import Data.Edison.Seq(Sequence)@@ -212,7 +214,7 @@   --   --   This function is /ambiguous/ at finite relation types if the key appears   --   more than once in the finite relation.  Otherwise, it is /unambiguous/.-  lookupM        :: (Monad rm) => k -> m a -> rm a+  lookupM        :: (Fail.MonadFail rm) => k -> m a -> rm a    -- | Return all elements bound by the given key in an unspecified order.   --@@ -236,7 +238,7 @@   --   --   This function is /ambiguous/ at finite relation types if the key appears   --   more than once in the finite relation.  Otherwise, it is /unambiguous/.-  lookupAndDeleteM :: (Monad rm) => k -> m a -> rm (a, m a)+  lookupAndDeleteM :: (Fail.MonadFail rm) => k -> m a -> rm (a, m a)    -- | Find all elements bound by the given key; return a sequence containing   --   all such bound elements in an unspecified order and the collection@@ -395,7 +397,7 @@   --   --   This function is /ambiguous/ at finite relation types if the finite relation   --   contains more than one minimum key.  Otherwise it is /unambiguous/.-  minView            :: (Monad rm) => m a -> rm (a, m a)+  minView            :: (Fail.MonadFail rm) => m a -> rm (a, m a)    -- | Find the binding with the minimum key and return its element. Signals   --   an error if the associative collection is empty.  Which element is chosen@@ -426,7 +428,7 @@   --   --   This function is /ambiguous/ at finite relation types if the finite relation   --   contains more than one minimum key.  Otherwise it is /unambiguous/.-  maxView            :: (Monad rm) => m a -> rm (a, m a)+  maxView            :: (Fail.MonadFail rm) => m a -> rm (a, m a)    -- | Find the binding with the maximum key and return its element.  Signals   --   an error if the associative collection is empty.  Which element is chosen@@ -777,7 +779,7 @@   --   minimum key exists in the relation.  Furthermore, it is /ambiguous/   --   with respect to the actual key observed unless the @Eq@ instance on   --   keys corresponds to indistinguisability.-  minViewWithKey  :: (Monad rm) => m a -> rm ((k, a), m a)+  minViewWithKey  :: (Fail.MonadFail rm) => m a -> rm ((k, a), m a)    -- | Find the binding with the minimum key in an associative collection and   --   return the key and the element.  Signals an error if the associative@@ -800,7 +802,7 @@   --   maximum key exists in the relation.  Furthermore, it is /ambiguous/   --   with respect to the actual key observed unless the @Eq@ instance on   --   keys corresponds to indistinguisability.-  maxViewWithKey  :: (Monad rm) => m a -> rm ((k, a), m a)+  maxViewWithKey  :: (Fail.MonadFail rm) => m a -> rm ((k, a), m a)    -- | Find the binding with the maximum key in an associative collection and   --   return the key and the element.  Signals an error if the associative
src/Data/Edison/Coll.hs view
@@ -97,6 +97,7 @@ ) where  import Prelude hiding (null,foldr,foldl,foldr1,foldl1,lookup,filter)+import qualified Control.Monad.Fail as Fail import Data.Monoid  import Data.Edison.Prelude@@ -104,7 +105,7 @@ import Data.Edison.Seq.ListSeq()  --- | The empty collection.  Equivalant to @mempty@ from+-- | The empty collection.  Equivalent to @mempty@ from --   the @Monoid@ instance. -- --   This function is always /unambiguous/.@@ -112,7 +113,7 @@ empty = mempty  -- | Merge two collections.  For sets, it is unspecified which element is---   kept in the case of duplicates.  Equivalant to @mappend@ from the+--   kept in the case of duplicates.  Equivalent to @mappend@ from the --   @Monoid@ instance. -- --   This function is /ambiguous/ at set types if the sets are not disjoint.@@ -215,7 +216,7 @@   --   datastructure is infinite in size or contains exceptions or non-termination   --   in the structure itself, then @strict@ will result in bottom.  Operationally,   --   this function walks the datastructure forcing any closures.  In many-  --   collections, the collction \"shape\" depends on the value of the elemnts;+  --   collections, the collction \"shape\" depends on the value of the elements;   --   in such cases, the values of the elements will be forced to the extent   --   necessary to force the structure of the collection, but no further.   --@@ -421,7 +422,7 @@   --   This function is /ambiguous/ at bag types, when more than one   --   element equivalent to the given item is in the bag.  Otherwise   --   it is /unambiguous/.-  lookupM    :: (Monad m) => a -> c -> m a+  lookupM    :: (Fail.MonadFail m) => a -> c -> m a    -- | Return a sequence containing all elements in the collection equal to   --   the given element in an unspecified order.@@ -504,7 +505,7 @@   --   --   This function is /ambiguous/ at bag types, if more than one minimum   --   element exists in the bag.  Otherwise, it is /unambiguous/.-  minView    :: (Monad m) => c -> m (a, c)+  minView    :: (Fail.MonadFail m) => c -> m (a, c)    -- | Return the minimum element in the collection.  If there are multiple   --   copies of the minimum element, it is unspecified which is chosen.@@ -523,7 +524,7 @@   --   --   This function is /ambiguous/ at bag types, if more than one maximum   --   element exists in the bag.  Otherwise, it is /unambiguous/.-  maxView    :: (Monad m) => c -> m (a, c)+  maxView    :: (Fail.MonadFail m) => c -> m (a, c)    -- | Return the maximum element in the collection.  If there are multiple   --   copies of the maximum element, it is unspecified which is chosen.
src/Data/Edison/Prelude.hs view
@@ -10,14 +10,19 @@ --   This module is a central depository of common definitions --   used throughout Edison. +{-# LANGUAGE GeneralizedNewtypeDeriving #-}+ module Data.Edison.Prelude ( -- * Hashing classes   Hash (..) , UniqueHash , ReversibleHash (..) , Measured (..)+-- * Pure MonadFail+,  runFail_ ) where +import Control.Monad.Fail import Data.Monoid  -- | This class represents hashable objects. If obeys the @@ -62,3 +67,14 @@ --   the computation. class (Monoid v) => Measured v a | a -> v where   measure :: a -> v++-- From Agda source code: src/full/Agda/Utils/Fail.hs+-- | A pure MonadFail.+newtype Fail a = Fail { runFail :: Either String a }+  deriving (Functor, Applicative, Monad)++instance MonadFail Fail where+  fail = Fail . Left++runFail_ :: Fail a -> a+runFail_ = either error id . runFail
src/Data/Edison/Seq.hs view
@@ -58,6 +58,7 @@                        zip,zip3,zipWith,zipWith3,unzip,unzip3,null)  import Control.Monad+import qualified Control.Monad.Fail as Fail import Data.Monoid  import Data.Edison.Prelude@@ -221,7 +222,7 @@   --   This function is always /unambiguous/.   --   --   Default running time: @O( 1 )@-  lview     :: (Monad m) => s a -> m (a, s a)+  lview     :: (Fail.MonadFail m) => s a -> m (a, s a)    -- | Return the first element of a sequence.   --   Signals an error if the sequence is empty.@@ -249,7 +250,7 @@   --   This function is always /unambiguous/.   --   --   Default running time: @O( 1 )@-  lheadM    :: (Monad m) => s a -> m a +  lheadM    :: (Fail.MonadFail m) => s a -> m a     -- | Delete the first element of the sequence.   --   Signals error if sequence is empty.@@ -277,7 +278,7 @@   --   This function is always /unambiguous/.   --   --   Default running time: @O( 1 )@-  ltailM    :: (Monad m) => s a -> m (s a)+  ltailM    :: (Fail.MonadFail m) => s a -> m (s a)    -- | Separate a sequence into its last (rightmost) element and the   --   remaining sequence.  Calls 'fail' if the sequence is empty.@@ -291,7 +292,7 @@   --   This function is always /unambiguous/.   --   --   Default running time: @O( n )@-  rview     :: (Monad m) => s a -> m (a, s a)+  rview     :: (Fail.MonadFail m) => s a -> m (a, s a)    -- | Return the last (rightmost) element of the sequence.   --   Signals error if sequence is empty.@@ -319,7 +320,7 @@   --   This function is always /unambiguous/.   --   --   Default running time: @O( n )@-  rheadM    :: (Monad m) => s a -> m a+  rheadM    :: (Fail.MonadFail m) => s a -> m a    -- | Delete the last (rightmost) element of the sequence.   --   Signals an error if the sequence is empty.@@ -347,7 +348,7 @@   --   This function is always /unambiguous/.   --   --   Default running time: @O( n )@-  rtailM    :: (Monad m) => s a -> m (s a)+  rtailM    :: (Fail.MonadFail m) => s a -> m (s a)    -- | Returns 'True' if the sequence is empty and 'False' otherwise.   -- @@ -948,7 +949,7 @@   --   This function is always /unambiguous/.   --   --   Default running time: @O( i )@-  lookupM   :: (Monad m) => Int -> s a -> m a+  lookupM   :: (Fail.MonadFail m) => Int -> s a -> m a    -- | Return the element at the given index, or the   --   default argument if the index is out of bounds.  All indexes are@@ -1250,7 +1251,7 @@   --   --   This function is always /unambiguous/.   ---  --   Default running time: unbounded (forcing element closures can take arbitrairly long)+  --   Default running time: unbounded (forcing element closures can take arbitrarily long)   strictWith :: (a -> b) -> s a -> s a    -- | A method to facilitate unit testing.  Returns 'True' if the structural
src/Data/Edison/Seq/ListSeq.hs view
@@ -37,12 +37,12 @@     moduleName ) where -import Prelude hiding (concat,reverse,map,concatMap,foldr,foldl,foldr1,foldl1,+import Prelude hiding (concat,reverse,map,concatMap,foldr,foldl,foldr1,foldl1,foldl',                        filter,takeWhile,dropWhile,lookup,take,drop,splitAt,                        zip,zip3,zipWith,zipWith3,unzip,unzip3,null)-import qualified Control.Monad.Identity as ID+import qualified Control.Monad.Fail as Fail import qualified Prelude-import Data.Edison.Prelude+import Data.Edison.Prelude ( runFail_ ) import qualified Data.List import Data.Monoid import qualified Data.Edison.Seq as S ( Sequence(..) ) @@ -54,16 +54,16 @@ lcons          :: a -> [a] -> [a] rcons          :: a -> [a] -> [a] append         :: [a] -> [a] -> [a]-lview          :: (Monad rm) => [a] -> rm (a, [a])+lview          :: (Fail.MonadFail rm) => [a] -> rm (a, [a]) lhead          :: [a] -> a-lheadM         :: (Monad rm) => [a] -> rm a+lheadM         :: (Fail.MonadFail rm) => [a] -> rm a ltail          :: [a] -> [a]-ltailM         :: (Monad rm) => [a] -> rm [a]-rview          :: (Monad rm) => [a] -> rm (a, [a])+ltailM         :: (Fail.MonadFail rm) => [a] -> rm [a]+rview          :: (Fail.MonadFail rm) => [a] -> rm (a, [a]) rhead          :: [a] -> a-rheadM         :: (Monad rm) => [a] -> rm a+rheadM         :: (Fail.MonadFail rm) => [a] -> rm a rtail          :: [a] -> [a]-rtailM         :: (Monad rm) => [a] -> rm [a]+rtailM         :: (Fail.MonadFail rm) => [a] -> rm [a] null           :: [a] -> Bool size           :: [a] -> Int concat         :: [[a]] -> [a]@@ -92,7 +92,7 @@ copy           :: Int -> a -> [a] inBounds       :: Int -> [a] -> Bool lookup         :: Int -> [a] -> a-lookupM        :: (Monad m) => Int -> [a] -> m a+lookupM        :: (Fail.MonadFail m) => Int -> [a] -> m a lookupWithDefault :: a -> Int -> [a] -> a update         :: Int -> a -> [a] -> [a] adjust         :: (a -> a) -> Int -> [a] -> [a]@@ -252,7 +252,7 @@   | i >= 0    = not (null (drop i xs))   | otherwise = False -lookup i xs = ID.runIdentity (lookupM i xs)+lookup i xs = runFail_ (lookupM i xs)  lookupM i xs   | i < 0 = fail "ListSeq.lookup: not found"