intern 0.9.1.4 → 0.9.2
raw patch · 6 files changed
+85/−48 lines, 6 filesdep ~basedep ~hashablenew-uploader
Dependency ranges changed: base, hashable
Files
- .travis.yml +0/−1
- CHANGELOG.markdown +24/−0
- Data/Interned/IntSet.hs +13/−3
- README.markdown +15/−0
- examples/Term.hs +21/−19
- intern.cabal +12/−25
− .travis.yml
@@ -1,1 +0,0 @@-language: haskell
+ CHANGELOG.markdown view
@@ -0,0 +1,24 @@+0.9.2+-----+* Add a `Semigroup IntSet` instance.++0.9+---+* Removed `identity` from the Interned class, to support applications where the identity is obtained by other means (e.g. a unique Ptr value)++0.8+---+* Disabled cache removal as it was causing problems on large data sets. There is no good way to ensure that both references remain alive long enough to finish comparisons.+* Switched to IORef from MVar++0.7+---+* Fixed problem where comparisons could happen between data structures while one was still a thunk, leading to equal structures comparing as inequal in limited circumstances, by appropriately using strictness annotations.++0.6+---+* Widened the caches so they don't go through a single MVar per type. This has made a dramatic impact on performance. However, this broke the previous invariant that newer entries always had higher Ids than older entries.++0.5.2+-----+* Added Data.Interned.IntSet
Data/Interned/IntSet.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE MagicHash, TypeFamilies, FlexibleInstances, BangPatterns #-}+{-# LANGUAGE MagicHash, TypeFamilies, FlexibleInstances, BangPatterns, CPP #-} ----------------------------------------------------------------------------- -- | -- Module : Data.Interned.IntSet@@ -88,7 +88,7 @@ , minView -- * Map- , map+ , map -- * Fold , fold@@ -113,6 +113,9 @@ import qualified Data.List as List import Data.Monoid (Monoid(..)) import Data.Maybe (fromMaybe)+#if MIN_VERSION_base(4,9,0) && !(MIN_VERSION_base(4,11,0))+import Data.Semigroup (Semigroup(..))+#endif import Data.Interned.Internal import Data.Bits import Data.Hashable@@ -218,9 +221,16 @@ type Prefix = Int type Mask = Int +#if MIN_VERSION_base(4,9,0)+instance Semigroup IntSet where+ (<>) = union+#endif+ instance Monoid IntSet where mempty = empty+#if !(MIN_VERSION_base(4,11,0)) mappend = union+#endif mconcat = unions @@ -950,7 +960,7 @@ [highestBitMask] returns a word where only the highest bit is set. It is found by first setting all bits in lower positions than the highest bit and than taking an exclusive or with the original value.- Allthough the function may look expensive, GHC compiles this into+ Although the function may look expensive, GHC compiles this into excellent C code that subsequently compiled into highly efficient machine code. The algorithm is derived from Jorg Arndt's FXT library. ----------------------------------------------------------------------}
+ README.markdown view
@@ -0,0 +1,15 @@+intern+======++[](https://hackage.haskell.org/package/intern) [](http://travis-ci.org/ekmett/intern)++Efficient hash-consing for arbitrary data types.++Contact Information+-------------------++Contributions and bug reports are welcome!++Please feel free to contact me through github or on the #haskell IRC channel on irc.freenode.net.++-Edward Kmett
examples/Term.hs view
@@ -12,37 +12,39 @@ type Var = Int data Term- = App {-# UNPACK #-} !(Id Term) !Term !Term- | Lam {-# UNPACK #-} !(Id Term) {-# UNPACK #-} !Var !Term !Term- | Pi {-# UNPACK #-} !(Id Term) {-# UNPACK #-} !Var !Term !Term- | Set {-# UNPACK #-} !(Id Term) {-# UNPACK #-} !Int+ = App {-# UNPACK #-} !Id !Term !Term+ | Lam {-# UNPACK #-} !Id {-# UNPACK #-} !Var !Term !Term+ | Pi {-# UNPACK #-} !Id {-# UNPACK #-} !Var !Term !Term+ | Set {-# UNPACK #-} !Id {-# UNPACK #-} !Int deriving Show-data UninternedTerm +data UninternedTerm = BApp Term Term- | BLam Var Term Term + | BLam Var Term Term | BPi Var Term Term | BSet Int deriving Show instance Interned Term where type Uninterned Term = UninternedTerm- data Description Term = DApp (Id Term) (Id Term)- | DLam Var (Id Term) (Id Term)- | DPi Var (Id Term) (Id Term)+ data Description Term = DApp Id Id+ | DLam Var Id Id+ | DPi Var Id Id | DSet Int deriving Show- describe (BApp f a) = DApp (identity f) (identity a) + describe (BApp f a) = DApp (identity f) (identity a) describe (BLam v t e) = DLam v (identity t) (identity e) describe (BPi v t e) = DPi v (identity t) (identity e) describe (BSet n) = DSet n identify i = go where- go (BApp f a) = App i f a + go (BApp f a) = App i f a go (BLam v t e) = Lam i v t e go (BPi v t e) = Pi i v t e go (BSet n) = Set i n- identity (App i _ _) = i- identity (Lam i _ _ _) = i- identity (Pi i _ _ _) = i- identity (Set i _) = i cache = termCache +identity :: Term -> Id+identity (App i _ _) = i+identity (Lam i _ _ _) = i+identity (Pi i _ _ _) = i+identity (Set i _) = i+ instance Uninternable Term where unintern (App _ f a) = BApp f a unintern (Lam _ v t e) = BLam v t e@@ -61,10 +63,10 @@ _ == _ = False instance Hashable (Description Term) where- hash (DApp f a) = 0 `hashWithSalt` f `hashWithSalt` a- hash (DLam v t e) = 1 `hashWithSalt` v `hashWithSalt` t `hashWithSalt` e- hash (DPi v t e) = 2 `hashWithSalt` v `hashWithSalt` t `hashWithSalt` e- hash (DSet n) = 3 `hashWithSalt` n+ hashWithSalt s (DApp f a) = s `hashWithSalt` (0 :: Int) `hashWithSalt` f `hashWithSalt` a+ hashWithSalt s (DLam v t e) = s `hashWithSalt` (1 :: Int) `hashWithSalt` v `hashWithSalt` t `hashWithSalt` e+ hashWithSalt s (DPi v t e) = s `hashWithSalt` (2 :: Int) `hashWithSalt` v `hashWithSalt` t `hashWithSalt` e+ hashWithSalt s (DSet n) = s `hashWithSalt` (3 :: Int) `hashWithSalt` n instance Eq Term where (==) = (==) `on` identity
intern.cabal view
@@ -1,6 +1,6 @@ name: intern category: Data, Data Structures-version: 0.9.1.4+version: 0.9.2 license: BSD3 cabal-version: >= 1.6 license-file: LICENSE@@ -11,32 +11,19 @@ bug-reports: http://github.com/ekmett/intern/issues copyright: Copyright (C) 2011-2014 Edward A. Kmett build-type: Simple+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.2+ , GHC == 8.2.2+ , GHC == 8.4.1 synopsis: Efficient hash-consing for arbitrary data types-description:- Changes from 0.8 to 0.9- .- * Removed 'identity' from the Interned class, to support applications where the identity is obtained by other means (e.g. a unique Ptr value)- .- Changes from 0.7 to 0.8- .- * Disabled cache removal as it was causing problems on large data sets. There is no good way to ensure that both references remain alive long enough to finish comparisons.- * Switched to IORef from MVar- .- Changes from 0.6 to 0.7- .- * Fixed problem where comparisons could happen between data structures while one was still a thunk, leading to equal structures comparing as inequal in limited circumstances, by appropriately using strictness annotations.- .- Efficient hash-consing for arbitrary data types- .- Changes from 0.5.2 to 0.6- .- * Widened the caches so they don't go through a single MVar per type. This has made a dramatic impact on performance. However, this broke the previous invariant that newer entries always had higher Ids than older entries.- .- Changes from 0.5.1 to 0.5.2- .- * Added Data.Interned.IntSet+description: Efficient hash-consing for arbitrary data types. -extra-source-files: examples/Term.hs .travis.yml+extra-source-files: examples/Term.hs, CHANGELOG.markdown, README.markdown source-repository head type: git