unionfind

Documentation

Overview

Package unionfind is an implementation of Union-Find for use in unification.

Index

• func UnifyTypeExpr(xs []ast.BaseTerm, ys []ast.BaseTerm) (map[ast.Variable]ast.BaseTerm, error)
• type UnionFind
  • func InitVars(vars []ast.Variable, ts []ast.BaseTerm) (UnionFind, error)
  • func New() UnionFind
  • func UnifyTerms(xs []ast.BaseTerm, ys []ast.BaseTerm) (UnionFind, error)
  • func UnifyTermsExtend(xs []ast.BaseTerm, ys []ast.BaseTerm, base UnionFind) (UnionFind, error)
  • func (uf UnionFind) AsConstSubstList() ast.ConstSubstList
  • func (uf UnionFind) Get(v ast.Variable) ast.BaseTerm
  • func (uf UnionFind) String() string

Functions

func UnifyTypeExpr

func UnifyTypeExpr(xs []ast.BaseTerm, ys []ast.BaseTerm) (map[ast.Variable]ast.BaseTerm, error)

UnifyTypeExpr unifies two type expressions. These are terms that contain ApplyFn nodes.

Types

type UnionFind

type UnionFind struct {
	// contains filtered or unexported fields
}

UnionFind holds a data structure that permits fast unification.

func InitVars

func InitVars(vars []ast.Variable, ts []ast.BaseTerm) (UnionFind, error)

InitVars initializes a unionfind with a given substitution. The caller needs to ensure that none of the variables is "_" and none of the variables appears among the terms.

func New

func New() UnionFind

New constructs a new UnionFind instance.

func UnifyTerms

func UnifyTerms(xs []ast.BaseTerm, ys []ast.BaseTerm) (UnionFind, error)

UnifyTerms unifies two same-length lists of relational terms. It does not handle apply-expressions.

func UnifyTermsExtend

func UnifyTermsExtend(xs []ast.BaseTerm, ys []ast.BaseTerm, base UnionFind) (UnionFind, error)

UnifyTermsExtend unifies two same-length lists of relational terms, returning an extended UnionFind. It does not handle apply-expressions.

func (UnionFind) AsConstSubstList

func (uf UnionFind) AsConstSubstList() ast.ConstSubstList

AsConstSubstList turns this UnionFind structure into a linked list representation.

func (UnionFind) Get

func (uf UnionFind) Get(v ast.Variable) ast.BaseTerm

Get implements the Subst interface so UnionFind can be used as substituion.

func (UnionFind) String

func (uf UnionFind) String() string

String returns a readable debug string for this UnionFind object.