lattices 1.2.1.1 → 1.3

raw patch · 10 files changed

+306/−24 lines, 10 filesdep +deepseqdep +ghc-primdep +hashabledep ~basenew-uploaderPVP ok

version bump matches the API change (PVP)

Dependencies added: deepseq, ghc-prim, hashable, unordered-containers

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• Algebra/Enumerable.hs +10/−0
• Algebra/Lattice.hs +59/−2
• Algebra/Lattice/Dropped.hs +56/−0
• Algebra/Lattice/Levitated.hs +60/−1
• Algebra/Lattice/Lifted.hs +55/−0
• Algebra/PartialOrd.hs +15/−1
• CHANGELOG.md +8/−0
• LICENSE +1/−1
• README.md +5/−0
• lattices.cabal +37/−19

@@ -1,3 +1,13 @@+{-# LANGUAGE Safe #-}+----------------------------------------------------------------------------+-- |+-- Module      :  Algebra.Enumerable+-- Copyright   :  (C) 2010-2015 Maximilian Bolingbroke+-- License     :  BSD-3-Clause (see the file LICENSE)+--+-- Maintainer  :  Oleg Grenrus <oleg.grenrus@iki.fi>+--+---------------------------------------------------------------------------- module Algebra.Enumerable (     Enumerable(..), universeBounded,     Enumerated(..)

@@ -1,13 +1,31 @@ {-# LANGUAGE FlexibleInstances #-}+{-# LANGUAGE Trustworthy #-}+----------------------------------------------------------------------------+-- |+-- Module      :  Algebra.Lattice+-- Copyright   :  (C) 2010-2015 Maximilian Bolingbroke+-- License     :  BSD-3-Clause (see the file LICENSE)+--+-- Maintainer  :  Oleg Grenrus <oleg.grenrus@iki.fi>+--+-- In mathematics, a lattice is a partially ordered set in which every+-- two elements have a unique supremum (also called a least upper bound+-- or @join@) and a unique infimum (also called a greatest lower bound or+-- @meet@).+--+-- In this module lattices are defined using `meet` and `join` operators,+-- as it's constructive one.+--+---------------------------------------------------------------------------- module Algebra.Lattice (     -- * Unbounded lattices     JoinSemiLattice(..), MeetSemiLattice(..), Lattice,     joinLeq, joins1, meetLeq, meets1,-    +     -- * Bounded lattices     BoundedJoinSemiLattice(..), BoundedMeetSemiLattice(..), BoundedLattice,     joins, meets,-    +     -- * Fixed points of chains in lattices     lfp, lfpFrom, unsafeLfp,     gfp, gfpFrom, unsafeGfp,@@ -21,12 +39,17 @@ import qualified Data.Map as M import qualified Data.IntMap as IM +import Data.Hashable+import qualified Data.HashSet as HS+import qualified Data.HashMap.Lazy as HM  -- | A algebraic structure with element joins: <http://en.wikipedia.org/wiki/Semilattice> --+-- @ -- Associativity: x `join` (y `join` z) == (x `join` y) `join` z -- Commutativity: x `join` y == y `join` x -- Idempotency:   x `join` x == x+-- @ class JoinSemiLattice a where     join :: a -> a -> a @@ -40,9 +63,11 @@  -- | A algebraic structure with element meets: <http://en.wikipedia.org/wiki/Semilattice> --+-- @ -- Associativity: x `meet` (y `meet` z) == (x `meet` y) `meet` z -- Commutativity: x `meet` y == y `meet` x -- Idempotency:   x `meet` x == x+-- @ class MeetSemiLattice a where     meet :: a -> a -> a @@ -57,12 +82,16 @@ -- | The combination of two semi lattices makes a lattice if the absorption law holds: -- see <http://en.wikipedia.org/wiki/Absorption_law> and <http://en.wikipedia.org/wiki/Lattice_(order)> --+-- @ -- Absorption: a `join` (a `meet` b) == a `meet` (a `join` b) == a+-- @ class (JoinSemiLattice a, MeetSemiLattice a) => Lattice a where  -- | A join-semilattice with some element |bottom| that `join` approaches. --+-- @ -- Identity: x `join` bottom == x+-- @ class JoinSemiLattice a => BoundedJoinSemiLattice a where     bottom :: a @@ -72,7 +101,9 @@  -- | A meet-semilattice with some element |top| that `meet` approaches. --+-- @ -- Identity: x `meet` top == x+-- @ class MeetSemiLattice a => BoundedMeetSemiLattice a where     top :: a @@ -116,6 +147,19 @@     bottom = IS.empty  --+-- HashSet+--++instance (Eq a, Hashable a) => JoinSemiLattice (HS.HashSet a) where+    join = HS.union++instance (Eq a, Hashable a) => MeetSemiLattice (HS.HashSet a) where+    meet = HS.intersection++instance (Eq a, Hashable a) => BoundedJoinSemiLattice (HS.HashSet a) where+    bottom = HS.empty++-- -- Maps -- @@ -144,6 +188,19 @@  instance JoinSemiLattice v => BoundedJoinSemiLattice (IM.IntMap v) where     bottom = IM.empty++--+-- HashMaps+--++instance (Eq k, Hashable k) => JoinSemiLattice (HM.HashMap k v) where+    join = HM.union++instance (Eq k, Hashable k) => MeetSemiLattice (HM.HashMap k v) where+    meet = HM.intersection++instance (Eq k, Hashable k) => BoundedJoinSemiLattice (HM.HashMap k v) where+    bottom = HM.empty  -- -- Functions

@@ -1,9 +1,42 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE Trustworthy #-}+----------------------------------------------------------------------------+-- |+-- Module      :  Algebra.Lattice.Dropped+-- Copyright   :  (C) 2010-2015 Maximilian Bolingbroke, 2015 Oleg Grenrus+-- License     :  BSD-3-Clause (see the file LICENSE)+--+-- Maintainer  :  Oleg Grenrus <oleg.grenrus@iki.fi>+--+---------------------------------------------------------------------------- module Algebra.Lattice.Dropped (     Dropped(..)   ) where +#ifndef MIN_VERSION_base+#define MIN_VERSION_base(x,y,z) 1+#endif+ import Algebra.Lattice +#if MIN_VERSION_base(4,8,0)+#else+import Data.Monoid (Monoid(..))+import Data.Foldable+import Data.Traversable+#endif++import Control.Applicative+import Control.DeepSeq+import Data.Data+import Data.Hashable+import GHC.Generics+ -- -- Dropped --@@ -12,6 +45,29 @@ -- As a bonus, the top will be an absorbing element for the join. data Dropped a = Top                | Drop a+  deriving ( Eq, Ord, Show, Read, Data, Typeable, Generic+#if __GLASGOW_HASKELL__ >= 706+           , Generic1+#endif+           )++instance Functor Dropped where+  fmap _ Top      = Top+  fmap f (Drop a) = Drop (f a)++instance Foldable Dropped where+  foldMap _ Top      = mempty+  foldMap f (Drop a) = f a++instance Traversable Dropped where+  traverse _ Top      = pure Top+  traverse f (Drop a) = Drop <$> f a++instance NFData a => NFData (Dropped a) where+  rnf Top      = ()+  rnf (Drop a) = rnf a++instance Hashable a => Hashable (Dropped a)  instance JoinSemiLattice a => JoinSemiLattice (Dropped a) where     Top    `join` _      = Top

@@ -1,9 +1,42 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE Trustworthy #-}+----------------------------------------------------------------------------+-- |+-- Module      :  Algebra.Lattice.Levitated+-- Copyright   :  (C) 2010-2015 Maximilian Bolingbroke, 2015 Oleg Grenrus+-- License     :  BSD-3-Clause (see the file LICENSE)+--+-- Maintainer  :  Oleg Grenrus <oleg.grenrus@iki.fi>+--+---------------------------------------------------------------------------- module Algebra.Lattice.Levitated (     Levitated(..)   ) where +#ifndef MIN_VERSION_base+#define MIN_VERSION_base(x,y,z) 1+#endif+ import Algebra.Lattice +#if MIN_VERSION_base(4,8,0)+#else+import Data.Monoid (Monoid(..))+import Data.Foldable+import Data.Traversable+#endif++import Control.Applicative+import Control.DeepSeq+import Data.Data+import Data.Hashable+import GHC.Generics+ -- -- Levitated --@@ -14,7 +47,33 @@ data Levitated a = Top                  | Levitate a                  | Bottom+  deriving ( Eq, Ord, Show, Read, Data, Typeable, Generic+#if __GLASGOW_HASKELL__ >= 706+           , Generic1+#endif+           )+instance Functor Levitated where+  fmap _ Bottom       = Bottom+  fmap _ Top          = Top+  fmap f (Levitate a) = Levitate (f a) +instance Foldable Levitated where+  foldMap _ Bottom       = mempty+  foldMap _ Top          = mempty+  foldMap f (Levitate a) = f a++instance Traversable Levitated where+  traverse _ Bottom       = pure Bottom+  traverse _ Top          = pure Top+  traverse f (Levitate a) = Levitate <$> f a++instance NFData a => NFData (Levitated a) where+  rnf Top          = ()+  rnf Bottom       = ()+  rnf (Levitate a) = rnf a++instance Hashable a => Hashable (Levitated a)+ instance JoinSemiLattice a => JoinSemiLattice (Levitated a) where     Top        `join` _          = Top     _          `join` Top        = Top@@ -37,4 +96,4 @@ instance MeetSemiLattice a => BoundedMeetSemiLattice (Levitated a) where     top = Top -instance BoundedLattice a => BoundedLattice (Levitated a) where+instance Lattice a => BoundedLattice (Levitated a) where

@@ -1,9 +1,41 @@+{-# LANGUAGE CPP #-}+{-# LANGUAGE DeriveDataTypeable #-}+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE Trustworthy #-}+----------------------------------------------------------------------------+-- |+-- Module      :  Algebra.Lattice.Lifted+-- Copyright   :  (C) 2010-2015 Maximilian Bolingbroke, 2015 Oleg Grenrus+-- License     :  BSD-3-Clause (see the file LICENSE)+--+-- Maintainer  :  Oleg Grenrus <oleg.grenrus@iki.fi>+--+---------------------------------------------------------------------------- module Algebra.Lattice.Lifted (     Lifted(..)   ) where +#ifndef MIN_VERSION_base+#define MIN_VERSION_base(x,y,z) 1+#endif+ import Algebra.Lattice +#if MIN_VERSION_base(4,8,0)+#else+import Data.Monoid (Monoid(..))+import Data.Foldable+import Data.Traversable+#endif++import Control.Applicative+import Control.DeepSeq+import Data.Data+import Data.Hashable+import GHC.Generics+ -- -- Lifted --@@ -12,6 +44,29 @@ -- As a bonus, the bottom will be an absorbing element for the meet. data Lifted a = Lift a               | Bottom+  deriving ( Eq, Ord, Show, Read, Data, Typeable, Generic+#if __GLASGOW_HASKELL__ >= 706+           , Generic1+#endif+           )++instance Functor Lifted where+  fmap _ Bottom   = Bottom+  fmap f (Lift a) = Lift (f a)++instance Foldable Lifted where+  foldMap _ Bottom   = mempty+  foldMap f (Lift a) = f a++instance Traversable Lifted where+  traverse _ Bottom   = pure Bottom+  traverse f (Lift a) = Lift <$> f a++instance NFData a => NFData (Lifted a) where+  rnf Bottom   = ()+  rnf (Lift a) = rnf a++instance Hashable a => Hashable (Lifted a)  instance JoinSemiLattice a => JoinSemiLattice (Lifted a) where     Lift x `join` Lift y = Lift (x `join` y)

@@ -1,8 +1,18 @@+{-# LANGUAGE Safe #-}+----------------------------------------------------------------------------+-- |+-- Module      :  Algebra.PartialOrd+-- Copyright   :  (C) 2010-2015 Maximilian Bolingbroke+-- License     :  BSD-3-Clause (see the file LICENSE)+--+-- Maintainer  :  Oleg Grenrus <oleg.grenrus@iki.fi>+--+---------------------------------------------------------------------------- module Algebra.PartialOrd (     -- * Partial orderings     PartialOrd(..),     partialOrdEq,-    +     -- * Fixed points of chains in partial orders     lfpFrom, unsafeLfpFrom,     gfpFrom, unsafeGfpFrom@@ -21,14 +31,18 @@ -- This can be defined using either |joinLeq| or |meetLeq|, or a more efficient definition -- can be derived directly. --+-- @ -- Reflexive:     a `leq` a -- Antisymmetric: a `leq` b && b `leq` a ==> a == b -- Transitive:    a `leq` b && b `leq` c ==> a `leq` c+-- @ -- -- The superclass equality (which can be defined using |partialOrdEq|) must obey these laws: --+-- @ -- Reflexive:  a == a -- Transitive: a == b && b == c ==> a == b+-- @ class Eq a => PartialOrd a where     leq :: a -> a -> Bool 

@@ -0,0 +1,8 @@+# 1.3 (2015-05-18)++- relaxed constraint for `BoundedLattice (Levitated a)`+- added instances to `Dropped`, `Levitated` and `Lifted`:+    - from base+    - `NFData`+    - `Hashable`+- added `HashSet` and `HashMap` lattice instances

@@ -1,4 +1,4 @@-Copyright (c) 2010, Maximilian Bolingbroke+Copyright (c) 2010-2015 Maximilian Bolingbroke, 2015 Oleg Grenrus All rights reserved.  Redistribution and use in source and binary forms, with or without modification, are permitted

@@ -0,0 +1,5 @@+# lattices++[![Build Status](https://travis-ci.org/phadej/lattices.svg?branch=master)](https://travis-ci.org/phadej/lattices)++Fine-grained library for constructing and manipulating lattices

@@ -1,21 +1,39 @@-Name:               lattices-Version:            1.2.1.1-Cabal-Version:      >= 1.2-Category:           Math-Synopsis:           Fine-grained library for constructing and manipulating lattices-License:            BSD3-License-File:       LICENSE-Author:             Max Bolingbroke <batterseapower@hotmail.com>-Maintainer:         Max Bolingbroke <batterseapower@hotmail.com>-Build-Type:         Simple+name:               lattices+version:            1.3+cabal-version:      >= 1.10+category:           Math+license:            BSD3+license-File:       LICENSE+author:             Maximilian Bolingbroke <batterseapower@hotmail.com>+maintainer:         Oleg Grenrus <oleg.grenrus@iki.fi>+homepage:           http://github.com/phadej/lattices/+bug-reports:        http://github.com/phadej/lattices.git/issues+copyright:          (C) 2010-2015 Maximilian Bolingbroke+build-type:         Simple+extra-source-files: README.md CHANGELOG.md+synopsis:           Fine-grained library for constructing and manipulating lattices+description:+  In mathematics, a lattice is a partially ordered set in which every two elements have a unique supremum (also called a least upper bound or @join@) and a unique infimum (also called a greatest lower bound or @meet@). -Library-        Exposed-Modules: Algebra.Enumerable,-                         Algebra.Lattice,-                         Algebra.Lattice.Dropped,-                         Algebra.Lattice.Levitated,-                         Algebra.Lattice.Lifted,-                         Algebra.PartialOrd+source-repository head+  type: git+  location: git://github.com/phadej/lattices.git -        Build-Depends:   base >= 3 && < 5,-                         containers >= 0.3 && < 0.6+library+  exposed-modules:  Algebra.Enumerable,+                    Algebra.Lattice,+                    Algebra.Lattice.Dropped,+                    Algebra.Lattice.Levitated,+                    Algebra.Lattice.Lifted,+                    Algebra.PartialOrd++  build-depends:    base >= 3 && < 5,+                    containers >= 0.3 && < 0.6,+                    deepseq >= 1.1 && < 1.5,+                    hashable >= 1.2 && < 1.3,+                    unordered-containers >= 0.2  && < 0.3+  ghc-options:      -Wall+  default-language: Haskell2010++  if impl(ghc >= 7.4 && < 7.5)+    build-depends:  ghc-prim