## Description

In this assignment, you will construct a constraint solver and a few unification algorithms.

You will implement four modules: Unify, Equation, Tree, and Natural. You should submit

each in its own *.hs or *.lhs file. File names are case sensitive.

Note: All function definitions at top level must have explicit type annotations. Unless

otherwise specified, your solutions may utilize functions from the standard prelude as well as

material from the lecture notes and textbook. You may not use any other materials without

explicit citation.

Problem 1. (5 pts)

A substitution is any mapping (in a mathematical sense) of variables to values. Substitutions

can be represented in various ways. We will represent a substitution by a list of pairs.

In each pair in the list, the first component specifies a variable name as a string and the

second component specifies the value to which that variable is mapped. For example, the

substitution

[(“x”, 1), (“y”, 2)]

indicates that all instances of “x” map to 1 and all instances of “y” map to 2. To apply

a substitution is to replace all variables in a data type instance (i.e. a value) with their

corresponding value in the substitution. You should introduce into your Unify module the

following type synonym declaration:

type Subst a = [(String, a)]

Unification is defined in terms of substitutions. We say a substitution s unifies two values

v1 and v2 if

subst s v1 == subst s v2,

where (==) is derived equality on the type of those values and subst s v is the application

of a substitution s on a value v. You will define a representation for substitutions in the

Unify module.

1

(a) Define a value emp::Subst a that represents the empty substitution, and a function

sub::String -> a -> Subst a for constructing a substitution for only a single variable.

(b) Define a function get::String -> Subst a -> Maybe a that takes a variable name

and a substitution, and returns the value for which that variable must be substituted.

If the substitution is not defined on the variable, the function should return Nothing.

Problem 2. (15 pts)

Because every data type has different constructors, each data type requires its own specific

definition of a substitution function. However, we may want to write polymorphic code that

uses substitutions and performs unification without explicitly referencing a particular data

type. In order to accomplish this, we define some new type classes.

(a) Define a type class Substitutable that specifies that two functions, subst::Subst

a -> a -> a and vars::a -> [String], must be defined for any type a inside this

class. The vars function is meant to return a list of all the variables in a value of type

a.

(b) Within the Substitutable class declaration, define a function solved::Subst a ->

Bool. This function should return True only if the second component of every pair

in its input list has no variables (as determined by the vars function). Otherwise, it

should return False. To avoid generating an Eq a constraint, you may want to use the

null::[a] -> Bool function from the Haskell libraries.

(c) Within the Substitutable class declaration, define a function reduce::Subst a ->

Subst a. This function should take as input a substitution 푠 and collect all the pairs

in 푠 whose second component contains no variables. Call this new list of pairs 푠

′

. It

should then apply 푠

′

to all the second components in 푠, returning the result.

Problem 3. (10 pts)

(a) Define a type class Unifiable that specifies that a function unify::a -> a -> Maybe

(Subst a) must be defined for any type a inside this class. A type a can only be in the

Unifiable class if it is already in the Eq and Substitutable classes, and this should

be represented in your definition.

(b) Within the Unifiable class declaration, define a function combine::Maybe (Subst a)

-> Maybe (Subst a) -> Maybe (Subst a) that takes two substitutions (one or both

of which might be Nothing) as arguments. If neither one is Nothing, it should combine

them into a single substitution using concatenation. If even one of the arguments is

Nothing, combine should return Nothing.

(c) Modify your definition of the Unify module so that only the values emp, sub, get,

the type constructor Subst, the type classes Substitutable and Unifiable, and the

functions subst, vars, unify, and combine are exported from the module.

2

Problem 4. (20 pts)

In the module Natural, you will be working with the following data type:

data Natural = Zero | Succ Natural | Var String

(a) Add an instance declaration so that Natural is in the Substitutable class.

(b) Add an instance declaration so that Natural is in the Unifiable class. The unify

function must return a substitution under which the two arguments to unify are equivalent. If the two arguments are syntactically equivalent, unify should return the empty

substitution.

In the module Tree, you will be working with the following data type:

data Tree = Leaf | Node Tree Tree | Var String

(c) Add an instance declaration so that Tree is in the Substitutable class.

(d) Add an instance declaration so that Tree is in the Unifiable class.

Problem 5. (30 pts)

Within the Unifiable class declaration, define a function resolve::Maybe (Subst a) ->

Maybe (Subst a) that takes a substitution or Nothing as an argument. If its input is

Nothing, it can also return Nothing. If its input is a substitution, however, resolve should

do the following.

(1) Repeatedly apply reduce to the input substitution until no more changes occur when

reduce is applied. You may want to write a helper function to accomplish this. You

may also want to use the nub::Eq a => [a] -> [a] function from the Haskell libraries

to make sure your substitutions do not contain duplicated entries after each reduction.

(2) Once the substitution is stable with respect to reduce, check if it has any conflicts. A

conflict occurs if the substitution contains two pairs (x,u) and (y,v) such that x = y

but u ∕= v. If a conflict exists, resolve should return Nothing.

(3) Check if the substitution is solved by using the solved function. If it is solved, it

should be returned; otherwise, resolve should return Nothing.

You will need to add resolve to the list of functions that you export from the Unify module.

3

Problem 6. (20 pts)

In the module Equation, equations on a type a are represented in the following way:

data Equation a = a ‘Equals‘ a

(a) Define a function solveEqn::(Unifiable a) => Equation a -> Maybe (Subst a)

that returns the substitution that solves an equation, if possible.

(b) Define a function solveSystem::(Unifiable a) => [Equation a] -> Maybe (Subst

a) that takes a list of equations as an argument, and returns the substitution that solves

the system of equations represented by it, if possible. Be careful: you cannot implement

this correctly if you use your solution from part (a) directly, but the two functions in

parts (a) and (b) may share a helper function.

It is also now possible to define unify on values of type Tree.

(c) Solve the following equations or systems of equations. You are allowed to share your

solutions to these equations, but you may not share any of your Haskell code. For each

equation, define a value in the Tree module that holds its solution (for example, s0

can be the solution for e0, and so on).

e0 = Node (Node (Node (Var “x”) (Var “y”)) (Node (Var “y”) (Var “x”))) (Var “z”)

‘Equals‘

Node (Node (Node Leaf (Var “z”)) (Node Leaf (Var “y”))) (Var “x”)

e1 = let f b 0 = b

f b n = Node (f b (n-1)) (f b (n-1))

in f (Var “x”) 10 ‘Equals‘ f Leaf 13

e2 = [ (Var “z”) ‘Equals‘ Leaf

, Node (Var “y”) Leaf ‘Equals‘ Node Leaf (Var “x”)

, (Var “x”) ‘Equals‘ Node (Var “z”) (Var “z”)

]

4