packages feed

closure (empty) → 0.1.0.0

raw patch · 5 files changed

+233/−0 lines, 5 filesdep +basedep +hashabledep +unordered-containerssetup-changed

Dependencies added: base, hashable, unordered-containers

Files

+ LICENSE view
@@ -0,0 +1,21 @@+The MIT License (MIT)++Copyright (c) 2013 Joseph Abrahamson++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in+all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+THE SOFTWARE.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ closure.cabal view
@@ -0,0 +1,32 @@+-- Initial closure.cabal generated by cabal init.  For further +-- documentation, see http://haskell.org/cabal/users-guide/++name:                closure+version:             0.1.0.0+synopsis:            Depth- and breadth-first set closures++description:         Fast set closure operators.++homepage:            http://github.com/tel/closure+license:             MIT+license-file:        LICENSE+author:              Joseph Abrahamson+maintainer:          me@jspha.com+copyright:           (c) 2013 Joseph Abrahamson+category:            Math+build-type:          Simple+cabal-version:       >=1.10++library+  exposed-modules:     +    Algebra.Closure.Set.DepthFirst+    Algebra.Closure.Set.BreadthFirst+  build-depends:       base                  >= 4.6   && < 4.7+                     , hashable              >= 1.2.1 && < 1.2.2+                     , unordered-containers  >= 0.2.3 && < 0.2.4+  hs-source-dirs:      src+  default-language:    Haskell2010++source-repository head+  type: git+  location: git://github.com/tel/closure.git
+ src/Algebra/Closure/Set/BreadthFirst.hs view
@@ -0,0 +1,120 @@+-- |+-- Module      : Algebra.Closure.Set.BreadthFirst+-- Copyright   : (c) Joseph Abrahamson 2013+-- License     : MIT+-- +-- Maintainer  : me@jspha.com+-- Stability   : experimental+-- Portability : non-portable+-- +-- Depth-first closed sets. For a particular endomorphism @(p :: a ->+-- a)@ a 'Closed' set is a set where if some element @x@ is in the set+-- then so is @p x@. Unlike "Algebra.Closure.Set.DepthFirst", this+-- algorithm computes the closure in a depth-first manner and thus can+-- be useful for computing infinite closures.+-- +-- It's reasonable to think of a breadth-first 'Closed' set as the+-- process of generating a depth-first+-- 'Algebra.Closure.Set.DepthFirst.Closed' set frozen in time. This+-- retains information about the number of iterations required for+-- stability and allows us to return answers that depend only upon+-- partial information even if the closure itself is unbounded.++module Algebra.Closure.Set.BreadthFirst (++  -- * Closed sets+  Closed, seenBy, seen,++  -- ** Operations+  memberWithin', memberWithin, member', member,++  -- ** Creation+  close,+  +  ) where++import Prelude hiding (foldr)+import Data.HashSet (HashSet)+import Data.Hashable+import Data.Foldable (Foldable, foldr, toList)+import qualified Data.HashSet as Set++-- | A closed set @Closed a@, given an endomorphism @(p :: a -> a)@,+-- is a set where if some element @x@ is in the set then so is @p x@.+data Closed a = Unchanging | Closed Int (a -> a) (HashSet a) (Closed a)++-- | @seenBy n@ converts a 'Closed' set into its underlying set,+-- approximated by @n@ iterations.+seenBy :: Int -> Closed a -> HashSet a+seenBy _ Unchanging = Set.empty+seenBy 0 (Closed _ _ set _)          = set+seenBy n (Closed _ _ set Unchanging) = set+seenBy n (Closed _ _ set next)       = seenBy (pred n) next++-- | Converts a 'Closed' set into its underlying set. If the 'Closed'+-- set is unbounded then this operation is undefined (see+-- 'seenBy'). It's reasonable to think of this operation as+-- +-- @+--   let omega = succ omega in seenBy omega+-- @+seen :: Closed a -> HashSet a+seen Unchanging = Set.empty+seen (Closed _ _ set Unchanging) = set+seen (Closed _ _ set next)       = seen next++-- | @memberWithin' n a@ checks to see whether an element is within a+-- 'Closed' set after @n@ improvements. The 'Closed' set returned is a+-- compressed, memoized 'Closed' set which may be faster to query.+memberWithin' :: (Hashable a, Eq a) => Int -> a -> Closed a -> (Bool, Closed a)+memberWithin' n _ Unchanging = (False, Unchanging)+memberWithin' 0 _ set        = (False, set)+memberWithin' n a c@(Closed _ _ set next)+  | Set.member a set = (True, c)+  | otherwise        = memberWithin' (pred n) a next++-- | @memberWithin' n a@ checks to see whether an element is within a+-- 'Closed' set after @n@ improvements.+memberWithin :: (Hashable a, Eq a) => Int -> a -> Closed a -> Bool+memberWithin n a = fst . memberWithin' n a++-- | Determines whether a particular element is in the 'Closed'+-- set. If the element is in the set, this operation is always+-- defined. If it is not and the set is unbounded, this operation is+-- undefined (see 'memberWithin'). It's reasonable to think of this+-- operation as+-- +-- @+--   let omega = succ omega in memberWithin omega+-- @+-- The 'Closed' set returned is a compressed, memoized 'Closed' set+-- which may be faster to query.+member' :: (Hashable a, Eq a) => a -> Closed a -> (Bool, Closed a)+member' _ Unchanging = (False, Unchanging)+member' a c@(Closed _ _ set next)+  | Set.member a set = (True, c)+  | otherwise        = member' a next++-- | Determines whether a particular element is in the 'Closed'+-- set. If the element is in the set, this operation is always+-- defined. If it is not and the set is unbounded, this operation is+-- undefined (see 'memberWithin'). It's reasonable to think of this+-- operation as+-- +-- @+--   let omega = succ omega in memberWithin omega+-- @+member :: (Hashable a, Eq a) => a -> Closed a -> Bool+member a = fst . member' a++-- | Converts any 'Foldable' container into the 'Closed' set of its+-- contents.+close :: (Hashable a, Eq a, Foldable t) => (a -> a) -> t a -> Closed a+close iter = build 0 Set.empty . toList where+  inserter :: (Hashable a, Eq a) => a -> (HashSet a, [a]) -> (HashSet a, [a])+  inserter a (set, fresh) | Set.member a set = (set, fresh)+                          | otherwise        = (Set.insert a set, a:fresh)+  build n curr [] = Unchanging+  build n curr as =+    Closed n iter curr $ step n (foldr inserter (curr, []) as)+  step n (set, added) = build (succ n) set (map iter added)
+ src/Algebra/Closure/Set/DepthFirst.hs view
@@ -0,0 +1,58 @@+-- |+-- Module      : Algebra.Closure.Set.DepthFirst+-- Copyright   : (c) Joseph Abrahamson 2013+-- License     : MIT+-- +-- Maintainer  : me@jspha.com+-- Stability   : experimental+-- Portability : non-portable+-- +-- Depth-first closed sets. For a particular endomorphism @(p :: a ->+-- a)@ a 'Closed' set is a set where if some element @x@ is in the set+-- then so is @p x@.++module Algebra.Closure.Set.DepthFirst (++  -- * Closed sets+  Closed, seen,++  -- ** Operations+  member,++  -- ** Creation+  empty, insert, close,+  +  ) where++import Prelude hiding (foldr)+import Data.HashSet (HashSet)+import Data.Hashable+import Data.Foldable (Foldable, foldr)+import qualified Data.HashSet as Set++-- | A closed set @Closed a@, given an endomorphism @(p :: a -> a)@,+-- is a set where if some element @x@ is in the set then so is @p x@.+data Closed a = Closed (HashSet a) (a -> a)++-- | Access the underlying set.+seen :: Closed a -> HashSet a+seen (Closed set _) = set++-- | Inserts a new element into a 'Closed' set, maintaining closure.+insert :: (Hashable a, Eq a) => a -> Closed a -> Closed a+insert a c@(Closed set iter)+  | Set.member a set = c+  | otherwise        = insert (iter a) $ Closed (Set.insert a set) iter++-- | An empty closed set under a fixed endomorphism.+empty :: (a -> a) -> Closed a+empty = Closed Set.empty++-- | Is a particular element in the closure of this set?+member :: (Hashable a, Eq a) => a -> Closed a -> Bool+member a = Set.member a . seen++-- | Converts any 'Foldable' container into the 'Closed' set of its+-- contents.+close :: (Hashable a, Eq a, Foldable t) => (a -> a) -> t a -> Closed a+close iter = foldr insert (empty iter)