ContextAlgebra 0.2.0.1 → 1.0.0.0
raw patch · 6 files changed
+133/−332 lines, 6 filesdep +QuickCheckdep +criteriondep +statisticsdep −latticesdep ~basenew-component:exe:ContextAlgebra
Dependencies added: QuickCheck, criterion, statistics, vector
Dependencies removed: lattices
Dependency ranges changed: base
Files
- ContextAlgebra.cabal +10/−52
- LICENSE +30/−1
- README.md +51/−0
- src/ConceptModel.hs +0/−144
- src/ContextLattice.hs +0/−135
- src/Main.hs +42/−0
ContextAlgebra.cabal view
@@ -1,67 +1,25 @@ -- Initial ContextAlgebra.cabal generated by cabal init. For further -- documentation, see http://haskell.org/cabal/users-guide/ --- The name of the package. name: ContextAlgebra---- The package version. See the Haskell package versioning policy (PVP) --- for standards guiding when and how versions should be incremented.--- http://www.haskell.org/haskellwiki/Package_versioning_policy--- PVP summary: +-+------- breaking API changes--- | | +----- non-breaking API additions--- | | | +--- code changes with no API change-version: 0.2.0.1---- A short (one-line) description of the package.-synopsis: Context Algebra---- A longer description of the package.-description: Context Algebra to identify typical exemplars of a concept influenced by a context. A executable model is included in the package NearContextAlgebra also available here---- The license under which the package is released.-license: BSD3---- The file containing the license text.+version: 1.0.0.0+synopsis: Implementation of the context algebra.+description: Implementation of the context algebra published in dissertation: Context Algebra applied to Spatial Concepts+homepage: https://github.com/juergenhah/ContextAlgebra+license: BSD3 license-file: LICENSE---- The package author(s). author: Jürgen Hahn---- An email address to which users can send suggestions, bug reports, and --- patches. maintainer: hahn@geoinfo.tuwien.ac.at---- A copyright notice. -- copyright: - category: Math- build-type: Simple---- Extra files to be distributed with the package, such as examples or a --- README.--- extra-source-files: ---- Constraint on the version of Cabal needed to build this package.+extra-source-files: README.md cabal-version: >=1.10 --library- -- Modules exported by the library.- exposed-modules: ConceptModel, ContextLattice- - -- Modules included in this library but not exported.+executable ContextAlgebra+ main-is: Main.hs -- other-modules: - - -- LANGUAGE extensions used by modules in this package.- other-extensions: FlexibleContexts, FlexibleInstances, MultiParamTypeClasses, TypeSynonymInstances, DeriveGeneric, InstanceSigs, UndecidableInstances- - -- Other library packages from which modules are imported.- build-depends: base >=4.7 && <5, containers >=0.5 && <0.6,lattices ==1.3.*, multiset ==0.3.*- - -- Directories containing source files.+ other-extensions: ScopedTypeVariables, TypeSynonymInstances, FlexibleInstances, MultiParamTypeClasses, FlexibleContexts+ build-depends: base >=4.8 && <4.9, multiset >=0.3 && <0.4, criterion >=1.1 && <1.2, QuickCheck >=2.8 && <2.9, containers >=0.5 && <0.6, vector >=0.11 && <0.12, statistics >=0.13 && <0.14 hs-source-dirs: src- - -- Base language which the package is written in. default-language: Haskell2010-
LICENSE view
@@ -1,1 +1,30 @@-I declare this package as public domain+Copyright (c) 2016, Jürgen Hahn++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++ * Redistributions of source code must retain the above copyright+ notice, this list of conditions and the following disclaimer.++ * Redistributions in binary form must reproduce the above+ copyright notice, this list of conditions and the following+ disclaimer in the documentation and/or other materials provided+ with the distribution.++ * Neither the name of Jürgen Hahn nor the names of other+ contributors may be used to endorse or promote products derived+ from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,51 @@+# ContextAlgebra+Implementation of the ContextAlgebra published in dissertation: *Context Algebra applied to Spatial Concepts*++This library is available on hackage [ContextAlgebra](https://hackage.haskell.org/package/ContextAlgebra)++# Abstract+Words are used to refer to objects in reality. One word can imply many references to different objects that are categorized as similar. For example, the word “city” can refer to Vienna, Alexandria, or Las Vegas; the word “near” can refer to a range of distances, e. g. “moon is near the earth” or “near St. Stephens cathedral”. If a Geographic Information System (GIS) is queried with a sentence including “city” or “near”, the challenge for an algorithm executed by the GIS is to decide which exemplar of the word “city” or which distance “near” refers to.++To overcome this challenge, the hypothesis is that context selects references to objects in reality. A context algebra is presented, implemented, and used to represent the word “near” (in the thesis), in order to evaluate the hypothesis. Context algebra makes use of the theory established by a context-enriched semiotic triangle. The semiotic triangle connects objects in reality to words via concepts in an agent. With context enrichment, the concept is separated into contextualized concepts that include objects in reality valid for a specific context. If words are used in this specific context, then they correspond to a specific contextualized concept, which then selects specific references to objects from reality.++Context algebra proposes a formalization for context. In this algebra, contexts are ordered with a partial order relation and can be combined with a disjunction or conjunction function to create other contexts. This relation and these functions satisfy algebraic properties that result in a lattice structure for context. Each context included in the lattice is mapped to a contextualized concept. A contextualized concept is modeled with sets of objects observed from reality, where a typical object is determined. This typical object (prototype) is assumed to be the translation from a word to an object in reality. For example, the influencing context “capital of Austria” for the word “city” selects the prototypical instance Vienna. ++Context algebra is implemented using Haskell, it is then proven, and the complexity class is determined. + - The implementation shows that the context algebra is realizable with reasonable performance. + - To prove that the implementation satisfies the proposed algebraic properties, tests are successfully executed. + - The benchmarks determine the complexity class exponential for the implementation.+++# Implementation+The implementation is structured into several modules according to the mathematical structure of the theory.++ - **ContextAlgebra** is built upon several abstract classes, each representing a mathematical structure.+ - **Concept** invents two containers, one to connect a concept to context (*Observation* data type) and one to build the concept (*MultiSet* of *Observations*).+ - **Mapping** establishes a *ContextualizedConcept* via the mapping function *m*+ - **ContextualizedConcept** calculates prototypes for a *ContextualizedConcept*.++## SetImplementation+ - **ContextAlgebraSetInstance** instances all abstract classes given in module **ContextAlgebra** using sets.++## ExemplarScales+ - **NominalExemplars** calculates a prototype from exemplars on a nominal exemplar scales.+ - **RatioExamplars** calculates a prototype from exemplars on a rational measurement scale.++# Evaluation + - **ContextAlgebraEvaluation** execution of all property tests for the **ContextAlgebra**.+ - **QuickCheckHelper** wrapper functions for [QuickCheck](https://hackage.haskell.org/package/QuickCheck) execution.++# Benchmarks - Complexity+ - **ConceptGenerator** establishes concepts, with a freely selected number of exemplars and contexts.+ - **ProtoCalculator** calculates prototypes for each level of a *ContextLattice*.++# Example for a General Context Operation++Module **GeneralContextOperation** shows an example of the context algebra refining concepts and calculating prototypes for contextualized concepts. For an extended explanation look on page 58 in the dissertation.+++# Further Reading+If you are interested, there are two publications online to read and do not hesitate to contact me.+ - Context Algebra applied to Spatial Concepts (soon available)+ - [A Computational Model for Context and Spatial Concepts](https://link.springer.com/chapter/10.1007/978-3-319-33783-8_1)+
− src/ConceptModel.hs
@@ -1,144 +0,0 @@-{-# LANGUAGE DefaultSignatures #-}-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE MultiParamTypeClasses #-}-{-|-Module : ConceptModel-Description : connects the context Lattice with observation frequencies of exemplars using a multiset-Maintainer : hahn@geoinfo.tuwien.ac.at-Stability : beta--This module implements the necessary functions to model a concept influenced by several contexts. The concept is represented by several exemplars. For each influencing context the exemplars have different observation frequency. The connection from exemplars and context is modeled by the data type Experience. Each Experience can be made several times where the amount is hold by a Multiset.--}-module ConceptModel (Experience(..)- , Concept(..)- , Probability- ,ConceptContextModel- ,createConceptForContext- ,typicalityForExemplarsInContext- ,typicalExemplarInContext- ,printConcept- ,unionsConceptsForDiffContexts- ,filterConceptWithContext- ,amountExperiences) where--import ContextLattice--import Algebra.Enumerable-import qualified Data.Function as F-import qualified Data.List as L-import qualified Data.MultiSet as Mset---- | Each experience is formed by a exemplar of type e and a context c this exemplar was observed at.-data Experience c e =- -- | constructor; establishes an experience from a context and an exemplar- Exp c e deriving (Ord, Show, Eq)---- | All experiences are hold in a multiset-type Concept c e = Mset.MultiSet (Experience c e)---- | type synonym for better readability-type Probability = Float---- | the class defines the necessary functions needed for the context algebra-class (Ord c, Ord e, Show c, Show e)=> ConceptContextModel c e where-- -- | combines the observation amount of exemplars for one context- createConceptForContext :: (Show c,Ord c, Show e,Ord e) =>- (Context c) -- ^ context in which the experiences were made- -> [e] -- ^ exemplars which are observed- -> [Int] -- ^ amount of observations for one exemplar in this context- -> Concept (Context c) e -- ^ resulting concept with the given experiences- createConceptForContext context exemplars amounts = Mset.unions $zipWith manyfoldExperiences experiencesOnce amounts- where experiencesOnce = map (Exp context) exemplars-- -- | If an experience is made several times the amount can be specified by the @amount@- manyfoldExperiences :: (Ord c, Show c, Ord e, Show e) =>- Experience (Context c) e -- ^ experience that is observed several times- -> Int -- ^ amount of observations of the experience- -> Concept (Context c) e -- ^ concept represented by an amount of experiences- manyfoldExperiences exp amount= Mset.insertMany exp amount Mset.empty-- -- | calculates the amount of experiences that are present for the concept- amountExperiences ::- Concept (Context c) e -- ^ concept including experinces- -> Int -- ^ amount of experiences- amountExperiences = Mset.size-- -- | unions the experiences stored for one concept for different contexts- unionsConceptsForDiffContexts :: (Ord e, Ord c) =>- [Concept (Context c) e] -- ^ list of conceptualizations holding experiences for different contexts- -> Concept (Context c) e -- ^ union of the experiences holding now all experiences for all contexts- unionsConceptsForDiffContexts = Mset.unions-- -- | filters a concept for a context, gets a concept for a finer context,- -- the context c has to be more finer than the context that are included in the concept- filterConceptWithContext :: ((Enumerable c), Enumerable (Context c),Ord e, Eq c,Ord c) =>- Context c -- ^ context used to filter the experiences- -> Concept (Context c) e -- ^ experiences to filter- -> Concept (Context c) e -- ^ filtered experiences, more finer experiences are returned- filterConceptWithContext context concept = Mset.unions . L.map (\fctx -> (Mset.filter (\(Exp c1 _)-> c1 == fctx ) concept ) ) $ allfinerContexts- where allfinerContexts = getFinerContexts context--- -- | returns a probability of an exemplar observed in a context for the given experiences- typicalityofExemplarInContext ::((Enumerable c), Enumerable (Context c),Ord e,Ord c)=>- Experience (Context c) e -- ^ exemplar and context to look for- -> Concept (Context c) e -- ^ concept hoding experiences that are considered- -> Probability -- ^ probability of the exemplar in this context for the given concept- typicalityofExemplarInContext (Exp context exemplar) concept = if amountContext==0 then 0- else amountExemplar /amountContext- where observationAmounttForContext = amountExperiences experiencesForContext;- exemplarOservationAmountForContext = amountExperiences $ filterExemplars exemplar experiencesForContext;- experiencesForContext = filterConceptWithContext context concept- amountExemplar= fromIntegral exemplarOservationAmountForContext- amountContext = fromIntegral observationAmounttForContext-- -- * functions to print and export- -- | returns the typicality distribution for each exemplar in the context c, the type e is only used as type parameter- typicalityForExemplarsInContext :: (Ord c, Ord e,Enum e,Bounded e,(Enumerable c), Enumerable (Context c))=>- Context c -- ^ context the distribution is made for- -> e -- ^ exemplar type, used as type parameter- -> Concept (Context c) e -- ^ concept with the experiences- -> [(e,Probability)] -- ^ returned distribution- typicalityForExemplarsInContext context exemplar concept= map (\e ->(e, typicalityofExemplarInContext (Exp context e) concept) ) exemplars- where exemplars= enumFromTo minBound $ maxBound `asTypeOf` exemplar-- -- | returns the typical exemplar of a concept for the context- typicalExemplarInContext :: (Ord c, Ord e,Enum e,Bounded e,(Enumerable c), Enumerable (Context c))=>- Context c -- ^ context the distribution is made for- -> e -- ^ exemplar type, used as type parameter- -> Concept (Context c) e -- ^ concept with the experiences- -> (e, Probability) -- ^ tupel with the highest probability value- typicalExemplarInContext context exemplar concept = L.maximumBy (compare `F.on` snd) $ typicalityForExemplarsInContext context exemplar concept--- -- | returns experiences for the exemplar given in the first argument @e@- -- in quantum mechanics called projector- filterExemplars:: (Ord c, Ord e) =>- e -- ^ exemplar used to filter the experiences- -> Concept (Context c) e -- ^ concept that are filtered- -> Concept (Context c) e -- ^ concept including experiences for the exemplar e- filterExemplars exemplar = Mset.filter (\(Exp _ actualExemplar)-> exemplar ==actualExemplar)--- -- | converts the experiences of the concept to a IO()- printConcept :: (Show e, Show c) =>- Concept c e -- ^ experiences of the concept to print- -> IO() -- ^ returned IO()- printConcept concept = putStrLn $ Mset.showTreeWith True True concept--- -- * functions for further development of the model- -- | adds the @new@ experience to the given experiences- addExperience :: (Ord c,Ord e) =>- Experience c e -- ^ new experience to add- -> Concept c e -- ^ given concept where to add the new experience- -> Concept c e -- ^ resulting concept including the new and the given experiences- addExperience = Mset.insert--- forgetExperience:: (Ord c,Ord e) =>- Experience c e -- ^ new experience to add- -> Concept c e -- ^ given concept where to add the new experience- -> Concept c e -- ^ resulting concept including the new and the given experiences- forgetExperience = Mset.delete
− src/ContextLattice.hs
@@ -1,135 +0,0 @@-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE InstanceSigs #-}-{-# LANGUAGE MultiParamTypeClasses #-}-{-# LANGUAGE TypeSynonymInstances #-}-{-# LANGUAGE UndecidableInstances #-}-{-|-Module : ContextLattice-Description : models a Lattice for a context type, the top of the lattice is represented by One and inherits a list of all subcontexts, the bottom of the lattice is represented by Zero.-Maintainer : hahn@geoinfo.tuwien.ac.at-Stability : beta--models a Lattice for a context type, the top of the lattice is represented by One and inherits a list of all subcontexts, the bottom of the lattice is represented by Zero. To inherit the contextlattice to a new data type the data type has to instanciate: Enumerable c, Eq c, Ord c, Show c--}-module ContextLattice (Context (One,Ctx,Zero), getFinerContexts- ,extractContext, propCommutative,propIdempotent,propAssociative) where--import Algebra.Enumerable-import Algebra.Lattice-import qualified Data.List as L-import qualified Debug.Trace as T---- | data type to represent a lattice structure, the actual context is the type variable @c@-data Context c=- -- | constructor represents the One element of the lattice, all contexts are included in this constructor,- -- for this constructor the model includes all contexts- One [Context c]- -- | constructor for one context- | Ctx [c]- -- | constructor represents the bottom element of the lattice, without any context- | Zero deriving (Show,Eq,Ord)---- | makes the Context c type to a MeetSemiLattice by implementing the meet function-instance (Enumerable c,Eq c,(Enumerable (Context c)))=>- MeetSemiLattice (Context c) where-- -- | the meet funtion implements the algebraic properties of context- meet:: Context c-> Context c-> Context c- meet (One _) c = c -- cummutative with One element- meet c (One _) = c -- cummutative with One element- meet firstContext secondContext- | null firstIntersectWithSecondContext = Zero- | otherwise = Ctx (L.head firstIntersectWithSecondContext)- where firstContextList = L.concatMap extractContext $ getFinerContexts firstContext- secondContextList = L.concatMap extractContext $ getFinerContexts secondContext- firstIntersectWithSecondContext = firstContextList `isPartOf` secondContextList -- commutativity property---- | extracts a context list of contexts from the element,--- needed for the One wrapper constructor-extractContext ::- Context c -- ^ Context where elements are extracted from,- -> [[c]] -- ^ extracted context list-extractContext (One c) = extractOneContext c-extractContext (Ctx c) = [c]-extractContext Zero = []---- | makes a list of contexts for the One constructor-extractOneContext ::- [Context c] -- ^ list of context c occured by constructor c- -> [[c]] -- ^ extracted list-extractOneContext [] = []-extractOneContext (Ctx c:cs)= c : extractOneContext cs---- | takes a context and returns all finer-getFinerContexts :: (Eq c, (Enumerable c),(Enumerable (Context c))) =>- Context c -- ^ context that is used as start- -> [Context c] -- ^ all finer contexts of the start context included in the lattice-getFinerContexts c = L.map Ctx $ contextListWholeLattice `isPartOf` contextListfromStart- where contextListfromStart = extractContext c- contextListWholeLattice = extractContext (One universe)---- | Checks if the first context list is included in the second, if so the context is returned,--- so far the function is does not have any order restrictions (is commutative)--- checks also sublists, if an element of a sublist is in both lists, the whole list is included-isPartOf ::(Eq c) =>- [[c]] -- ^ first list that is used to check against second one- -> [[c]] -- ^ second list is like a reference- -> [[c]] -- ^ elements that are included in both lists-isPartOf = L.intersectBy (\lista listb -> all (`elem` lista) listb)----- * algebraic property test methods--- | test for commutativity------ >>> (Ctx [Walking]) `propCommutative` One [Ctx [Walking],Ctx [Driving],Ctx [Walking,Driving],Ctx [Uphill],Ctx [Walking,Uphill],Ctx [Driving,Uphill],Ctx [Walking,Driving,Uphill]] = (Ctx [Walking]) `meet` One [Ctx [Walking],Ctx [Driving],Ctx [Walking,Driving],Ctx [Uphill],Ctx [Walking,Uphill],Ctx [Driving,Uphill],Ctx [Walking,Driving,Uphill]] == One [Ctx [Walking],Ctx [Driving],Ctx [Walking,Driving],Ctx [Uphill],Ctx [Walking,Uphill],Ctx [Driving,Uphill],Ctx [Walking,Driving,Uphill]] `meet` (Ctx [Walking])--- true-propCommutative ::(Eq c,Enumerable c, Enumerable (Context c)) =>- Context c -- ^ context one- -> Context c -- ^ context two- -> Bool -- ^ true if the property is full-filled-propCommutative c1 c2 = c1 `meet` c2 == c2 `meet` c1---- | test for idempotency------ >>> propIdempotent (Ctx [Walking]) = (Ctx [Walking]) `meet` (Ctx [Walking]) == (Ctx [Walking])--- true-propIdempotent ::(Eq c,Enumerable c, Enumerable (Context c)) =>- Context c-- ^ context to test- -> Bool -- ^ true if the property is full-filled-propIdempotent c = c `meet` c == c---- | test for associativity------ >>> propAssociative (Ctx [Walking]) (Ctx [Driving]) (Ctx [Uphill]) = (Ctx [Walking]) `meet` ((Ctx [Driving]) `meet` (Ctx [Uphill])) == ((Ctx [Walking]) `meet` (Ctx [Driving])) `meet` (Ctx [Uphill])--- true-propAssociative :: (Eq c, Enumerable c, Enumerable (Context c)) =>- Context c -- ^ context one- -> Context c -- ^ context two- -> Context c -- ^ context three- -> Bool -- ^ true if the property is full-filled-propAssociative x y z = x `meet` (y `meet` z) == (x `meet` y) `meet` z----- |Absorption laws------ @--- a `join` (a `meet` b) = a,---a `meet` (a `join` b) = a.--- @---- | Identity laws------ @--- a `join` 0 = a,--- a `meet` 1 = a.--- @---- * not needed--- | checks in which level of the lattice the actual @Context c@ is--- One gets level 1, Zero gets level 0, and all others are 1+-level ::- Context c -- ^ context to check level in the lattice- -> Int -- ^ level in the lattice-level (One _)= 1-level (Zero)=0-level (Ctx a)= L.length a
+ src/Main.hs view
@@ -0,0 +1,42 @@+module Main where++import Criterion.Main+import System.IO++import Complexity.ProtoCalculator+import Complexity.ConceptGenerator++main :: IO()+main = do+ mapM_ makeSafe [stdout, stdin, stderr]+-- creation+ generationBench+ prototypeBench++-- ^ needed because on Manjaro Linux unicode characters abort the execution, the workaround removes the unicode characters+makeSafe h = do+ ce' <- hGetEncoding h+ case ce' of+ Nothing -> return ()+ Just ce -> mkTextEncoding ((takeWhile (/= '/') $ show ce) ++ "//TRANSLIT") >>=+ hSetEncoding h++-- be aware to change numbers in CalcPrototype+prototypeBench = defaultMain+ [bgroup "prototypeCalculation"$ + map (\c ->bench (label c) $! nfIO (calcProto c)) [1..ctx]+ ]+ where ctx = fromInteger testAmountContexts+ exe = testAmountExemplars+ label c = "meets-"++(show c)++"-contexts-"++(show testAmountContexts)++"-exemplars-"++(show exe)+++generationBench = defaultMain+ [bgroup "Concept generation"$+ map (\c -> bench (label c) $ nfIO (createAndStoreConcept c exe)) [12..ctx]+ ]+ where ctx = 12+ exe = 1+ label c = ("contexts-"++(show c)++"-exemplars-"++(show exe))++