       addToMap concated, k, v
   concated
 
+subtractSets =
+subtractMaps = (from, what) ->
+  subtracted = newMap()
+  for k, v of from.values when k not of what.values
+    addToMap subtracted, k, v
+  subtracted
+
+values = (map) ->
+  map.values
+
 # end of Set
 
-# Type inference and checker
+# Type inference and checker ala Mark Jones
+
+unify = (ctx, t1, t2) ->
+  sub = ctx.substitution
+  ctx.extendSubstitution findSubToMatch (substitute sub, t1), (substitute sub, t2)
+
+findSubToMatch = (t1, t2) ->
+  if t1 instanceof TypeVariable
+    bindVariable t1, t2
+  else if t2 instanceof TypeVariable
+    bindVariable t2, t1
+  else if t1 instanceof TypeConstr and t2 instanceof TypeConstr and
+    t1.name is t2.name
+      emptySubstitution()
+  else if t1 instanceof TypeApp and t2 instanceof TypeApp
+    s1 = findSubToMatch t1.op, t2.op
+    s2 = findSubToMatch (substitute s1, t1.arg), (substitute s1, t2.arg)
+    joinSubs s1, s2
+  else
+    newMapWith "could not unify", [(printType t1), (printType t2)]
+
+bindVariable = (variable, type) ->
+  if type instanceof TypeVariable and variable.name is type.name
+    emptySubstitution()
+  else if inSet (findFree type), variable.name
+    newSetWith variable.name, "occurs check failed"
+  else if not kindsEq (kind variable), (kind type)
+    newSetWith variable.name, "kinds don't match for #{variable.name}"
+  else
+    newMapWith variable.name, type
+
+joinSubs = (s1,s2) ->
+  concatSets s1, mapMap ((type) -> substitute s1, type), s2
+
+emptySubstitution = ->
+  newMap()
+
+substitute = (substitution, type) ->
+  if type instanceof TypeVariable
+    if sub = lookupInMap substitution, type.name
+      sub
+    else
+      type
+  else if type instanceof TypeApp
+    new TypeApp (substitute substitution, type.op),
+      (substitute substitution, type.arg)
+  else if isBinding type
+    newBinding mapMap ((t) -> substitute substitution t) type
+  else
+    type
+
+findFree = (type) ->
+  if type instanceof TypeVariable
+    newMapWith type.name, type.kind
+  else if type instanceof TypeApp
+    concatMaps (findFree type.op), (findFree type.arg)
+  else
+    newMap()
+
+findBound = (name, binding) ->
+  (lookupInMap binding, name) or 'unbound name #{name}'
+
+# TODO: when using qualified types, replace with
+# freshInst over type schemes
+freshInstance = (ctx, type) ->
+  freshes = mapMap ((kind) -> ctx.freshTypeVariable kind), findFree type
+  substitute freshes, type
+
+# Old type inference
 
 assignTypes = (context, expression) ->
   [s, _, expression] = infer context, expression, 0

  suffix = if nameIndex > 25 then Math.floor nameIndex / 25 else ''
  String.fromCharCode 97 + nameIndex % 25

typeVariable = (name) ->
  new TypeVariable name

nullaryType = (name) ->
  new NullaryType name

naryType = (name, params) ->
  new PolyType name, params

class MonoType
  constructor: (@name) ->

class TypeVariable extends MonoType
class NullaryType extends MonoType

class PolyType
  constructor: (@name, @params) ->

class NaryType extends PolyType

ignoreTypeErrors = (fn) ->
  try
    ret = fn()
  catch e
    unless e instanceof TypeError
      throw e

class TypeError extends Error
  # required for instanceof to work
  constructor: (@message, @data) -> super @message

# mycroft = (context, node, environment) ->
#   if node.label is 'numerical'

    cb ast
  ast

visitExpressions = (expression, cb) ->
  cb expression
  if isForm expression
    for term in _terms expression
      visitExpressions term, cb

inside = (node) -> node[1...-1]

matchNode = (to, node) ->
