tie-knot (empty) → 0.1
raw patch · 4 files changed
+302/−0 lines, 4 filesdep +basedep +containersdep +fixpointsetup-changed
Dependencies added: base, containers, fixpoint, mtl
Files
- COPYING.LESSER +165/−0
- Setup.hs +2/−0
- src/Data/Knot.hs +104/−0
- tie-knot.cabal +31/−0
+ COPYING.LESSER view
@@ -0,0 +1,165 @@+ GNU LESSER GENERAL PUBLIC LICENSE+ Version 3, 29 June 2007++ Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>+ Everyone is permitted to copy and distribute verbatim copies+ of this license document, but changing it is not allowed.+++ This version of the GNU Lesser General Public License incorporates+the terms and conditions of version 3 of the GNU General Public+License, supplemented by the additional permissions listed below.++ 0. Additional Definitions.++ As used herein, "this License" refers to version 3 of the GNU Lesser+General Public License, and the "GNU GPL" refers to version 3 of the GNU+General Public License.++ "The Library" refers to a covered work governed by this License,+other than an Application or a Combined Work as defined below.++ An "Application" is any work that makes use of an interface provided+by the Library, but which is not otherwise based on the Library.+Defining a subclass of a class defined by the Library is deemed a mode+of using an interface provided by the Library.++ A "Combined Work" is a work produced by combining or linking an+Application with the Library. The particular version of the Library+with which the Combined Work was made is also called the "Linked+Version".++ The "Minimal Corresponding Source" for a Combined Work means the+Corresponding Source for the Combined Work, excluding any source code+for portions of the Combined Work that, considered in isolation, are+based on the Application, and not on the Linked Version.++ The "Corresponding Application Code" for a Combined Work means the+object code and/or source code for the Application, including any data+and utility programs needed for reproducing the Combined Work from the+Application, but excluding the System Libraries of the Combined Work.++ 1. Exception to Section 3 of the GNU GPL.++ You may convey a covered work under sections 3 and 4 of this License+without being bound by section 3 of the GNU GPL.++ 2. Conveying Modified Versions.++ If you modify a copy of the Library, and, in your modifications, a+facility refers to a function or data to be supplied by an Application+that uses the facility (other than as an argument passed when the+facility is invoked), then you may convey a copy of the modified+version:++ a) under this License, provided that you make a good faith effort to+ ensure that, in the event an Application does not supply the+ function or data, the facility still operates, and performs+ whatever part of its purpose remains meaningful, or++ b) under the GNU GPL, with none of the additional permissions of+ this License applicable to that copy.++ 3. Object Code Incorporating Material from Library Header Files.++ The object code form of an Application may incorporate material from+a header file that is part of the Library. You may convey such object+code under terms of your choice, provided that, if the incorporated+material is not limited to numerical parameters, data structure+layouts and accessors, or small macros, inline functions and templates+(ten or fewer lines in length), you do both of the following:++ a) Give prominent notice with each copy of the object code that the+ Library is used in it and that the Library and its use are+ covered by this License.++ b) Accompany the object code with a copy of the GNU GPL and this license+ document.++ 4. Combined Works.++ You may convey a Combined Work under terms of your choice that,+taken together, effectively do not restrict modification of the+portions of the Library contained in the Combined Work and reverse+engineering for debugging such modifications, if you also do each of+the following:++ a) Give prominent notice with each copy of the Combined Work that+ the Library is used in it and that the Library and its use are+ covered by this License.++ b) Accompany the Combined Work with a copy of the GNU GPL and this license+ document.++ c) For a Combined Work that displays copyright notices during+ execution, include the copyright notice for the Library among+ these notices, as well as a reference directing the user to the+ copies of the GNU GPL and this license document.++ d) Do one of the following:++ 0) Convey the Minimal Corresponding Source under the terms of this+ License, and the Corresponding Application Code in a form+ suitable for, and under terms that permit, the user to+ recombine or relink the Application with a modified version of+ the Linked Version to produce a modified Combined Work, in the+ manner specified by section 6 of the GNU GPL for conveying+ Corresponding Source.++ 1) Use a suitable shared library mechanism for linking with the+ Library. A suitable mechanism is one that (a) uses at run time+ a copy of the Library already present on the user's computer+ system, and (b) will operate properly with a modified version+ of the Library that is interface-compatible with the Linked+ Version.++ e) Provide Installation Information, but only if you would otherwise+ be required to provide such information under section 6 of the+ GNU GPL, and only to the extent that such information is+ necessary to install and execute a modified version of the+ Combined Work produced by recombining or relinking the+ Application with a modified version of the Linked Version. (If+ you use option 4d0, the Installation Information must accompany+ the Minimal Corresponding Source and Corresponding Application+ Code. If you use option 4d1, you must provide the Installation+ Information in the manner specified by section 6 of the GNU GPL+ for conveying Corresponding Source.)++ 5. Combined Libraries.++ You may place library facilities that are a work based on the+Library side by side in a single library together with other library+facilities that are not Applications and are not covered by this+License, and convey such a combined library under terms of your+choice, if you do both of the following:++ a) Accompany the combined library with a copy of the same work based+ on the Library, uncombined with any other library facilities,+ conveyed under the terms of this License.++ b) Give prominent notice with the combined library that part of it+ is a work based on the Library, and explaining where to find the+ accompanying uncombined form of the same work.++ 6. Revised Versions of the GNU Lesser General Public License.++ The Free Software Foundation may publish revised and/or new versions+of the GNU Lesser General Public License from time to time. Such new+versions will be similar in spirit to the present version, but may+differ in detail to address new problems or concerns.++ Each version is given a distinguishing version number. If the+Library as you received it specifies that a certain numbered version+of the GNU Lesser General Public License "or any later version"+applies to it, you have the option of following the terms and+conditions either of that published version or of any later version+published by the Free Software Foundation. If the Library as you+received it does not specify a version number of the GNU Lesser+General Public License, you may choose any version of the GNU Lesser+General Public License ever published by the Free Software Foundation.++ If the Library as you received it specifies that a proxy can decide+whether future versions of the GNU Lesser General Public License shall+apply, that proxy's public statement of acceptance of any version is+permanent authorization for you to choose that version for the+Library.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ src/Data/Knot.hs view
@@ -0,0 +1,104 @@+{-+ This file is part of tie-knot.++ tie-knot is free software: you can redistribute it and/or modify it under+ the terms of the GNU Lesser General Public License as published by the Free+ Software Foundation, either version 3 of the License, or (at your option)+ any later version.++ tie-knot is distributed in the hope that it will be useful, but WITHOUT ANY+ WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS+ FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for+ more details.++ You should have received a copy of the GNU Lesser General Public License+ along with tie-knot. If not, see <http://www.gnu.org/licenses/>.+-}++{-# LANGUAGE TypeFamilies, FlexibleContexts, FlexibleInstances #-}++-- | Module for tying the knot on data structures that reference each other by+-- some kind of keys. The 'tie' function replaces all such references with the actual+-- value, creating possibly recursive or cyclic data structures.+--+-- The module re-exports a part of the fixpoint package.+--+-- An example how to construct a structure with circular dependencies:+--+-- > data Person = Person { name :: String, loves :: [Person] }+-- > -- Define a variant of Person where the recursive type+-- > -- is given as a parameter, and injection/projection functions.+-- > instance Fixpoint Person where+-- > data Pre Person t = Loves { _name :: String, _loves :: [t] }+-- > inject ~(Loves n ps) = Person n ps+-- > project ~(Person n ps) = Loves n ps+-- >+-- > -- The easisest way to get 'Foldable' + 'Functor' is to implement+-- > -- 'Traversable' and then just use the default implementations.+-- > instance T.Traversable (Pre Person) where+-- > traverse f (Loves n ns) = Loves n <$> T.traverse f ns+-- >+-- > instance Functor (Pre Person) where+-- > fmap = T.fmapDefault+-- > instance F.Foldable (Pre Person) where+-- > foldMap = T.foldMapDefault+-- >+-- > -- Let's create a person with cicrular dependencies:+-- > alice :: Person+-- > alice = fromJust . Map.lookup "Alice" .+-- > tie' . Map.fromList . map (\l -> (_name l, l)) $ lst+-- > where+-- > lst = [ Loves "Alice" ["Bob", "cat"]+-- > , Loves "Bob" ["Alice"]+-- > -- you may disagree, but the cat thinks of itself as Person+-- > , Loves "cat" ["cat"]+-- > ]+module Data.Knot (tie, tie', isConsistent, RefMap, TieError(..), Fixpoint, Pre, inject, project) where++import Control.Monad+import Control.Monad.Error+import qualified Data.Foldable as F+import Data.Map (Map)+import qualified Data.Map as Map+import Data.Monoid+import Data.Maybe++import Data.Fixpoint++-- | Represents a set of data 'v' that reference each other+-- using keys of type 'k'.+type RefMap k v = Map k (v k)++-- | Possible errors when tying the knot.+data TieError k+ = MissingKey k k -- ^ A value with key k1 referenced non-existent key k2.+ deriving (Show, Eq, Ord)++-- | Check the loader for consistency, i.e. if all referenced keys+-- have a corresponding value. Values need to implement 'Foldable'+-- that traverses over all referenced keys.+isConsistent :: (Ord k, F.Foldable v, Functor v)+ => RefMap k v -- ^ The loader to check.+ -> Either (TieError k) (RefMap k v) -- ^ The loader argument or an error.+isConsistent l = maybe (Right l) Left . getFirst $+ Map.foldrWithKey (\k -> mappend . keysOk k) mempty l+ where+ keysOk k = F.foldMap (\r -> First $ if (Map.member r l)+ then Nothing+ else (Just (MissingKey k r)) )++-- | Helper function for anamorphisms.+ana' :: Fixpoint t => (s -> Pre t s) -> Pre t s -> t+ana' f = inject . fmap (ana f)++-- | Ties the knot without checking consistency.+-- If the references are inconsistent, an exception is raised.+tie' :: (Ord k, Fixpoint v) => RefMap k (Pre v) -> Map k v+tie' m = Map.map f m+ where+ -- (k -> v k) -> v k -> Fix v+ f = ana' $ \k -> fromJust (Map.lookup k m)++-- | Checks consistency by calling 'isConsistent' and then and ties the knot using 'tie''.+tie :: (Ord k, F.Foldable (Pre v), Fixpoint v) => RefMap k (Pre v) -> Either (TieError k) (Map k v)+tie = liftM tie' . isConsistent
+ tie-knot.cabal view
@@ -0,0 +1,31 @@+Name: tie-knot+Version: 0.1+Synopsis:+ "Ties the knot" on a given set of structures that reference each other by+ keys.+Description:+ "Ties the knot" on a given set of structures that reference each other by+ keys - replaces the keys with their respective values. Takes @Map k (v k)@+ and converts into @Map k v'@ where @v'@ is the fixed point of @v@. See the+ homepage for examples.+Category: Data Structures+License: LGPL+License-file: COPYING.LESSER+Author: Petr Pudlák+Copyright: (c) 2012 Petr Pudlák+Maintainer: Petr Pudlák <petr.mvd@gmail.com>+Build-Type: Simple+Cabal-Version: >=1.6+Stability: Experimental+Homepage: https://github.com/ppetr/tie-knot+Bug-reports: https://github.com/ppetr/tie-knot/issues++Source-repository head+ type: git+ location: git://github.com/ppetr/tie-knot.git++Library+ Build-Depends: base == 4.*, fixpoint >= 0.1.1 && < 2, containers >= 0.4, mtl >= 2+ Exposed-Modules: Data.Knot+ hs-source-dirs: src+-- ghc-options: -O2