unification-fd-0.9.0: Simple generic unification algorithms.

CopyrightCopyright (c) 2007--2014 wren gayle romano
LicenseBSD
Maintainerwren@community.haskell.org
Stabilityexperimental
Portabilitysemi-portable (MPTCs,...)
Safe HaskellNone
LanguageHaskell98

Control.Unification.IntVar

Description

This module defines a state monad for functional pointers represented by integers as keys into an IntMap. This technique was independently discovered by Dijkstra et al. This module extends the approach by using a state monad transformer, which can be made into a backtracking state monad by setting the underlying monad to some MonadLogic (part of the logict library, described by Kiselyov et al.).

  • Atze Dijkstra, Arie Middelkoop, S. Doaitse Swierstra (2008) Efficient Functional Unification and Substitution, Technical Report UU-CS-2008-027, Utrecht University.
    • Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry (2005) Backtracking, Interleaving, and Terminating Monad Transformers, ICFP.

Synopsis

Documentation

newtype IntVar Source

A "mutable" unification variable implemented by an integer. This provides an entirely pure alternative to truly mutable alternatives (like STVar), which can make backtracking easier.

N.B., because this implementation is pure, we can use it for both ranked and unranked monads.

Constructors

IntVar Int 

data IntBindingState t Source

Binding state for IntVar.

Instances

data IntBindingT t m a Source

A monad for storing IntVar bindings, implemented as a StateT. For a plain state monad, set m = Identity; for a backtracking state monad, set m = Logic.

evalIntBindingT :: Monad m => IntBindingT t m a -> m a Source

N.B., you should explicitly apply bindings before calling this function, or else the bindings will be lost