circlarity error in ml

Question

I'm trying to run a function subst(tr, v1, v2) which returns a new ntree where all the values of v1 are replaced by v2 in the output tree.

datatype 'a ntree = leaf of 'a | node of 'a ntree list;

fun map(f, []) = [] | map(f,x::t)=f(x) :: map(f,t);

fun subst(leaf(d), v1, v2) = if d=v1 then v2 else d
  | subst(node(q), v1, v2) = let fun w(k) =
  if k=v1 then subst(v2, v1, v2) else subst(k, v1, v2)
  in map(w, q)
  end;

but i get a circularity error b/c my rhs of clause does not agree w/ the function result type. my expression is ''Z list and my result type is ''Z

Answer 1

You've forgotten to wrap the results of subst with the appropriate ntree constructors again, and consequently, the type system is trying to equate the type of d with a list. Also, your function w does not make a hell lot of sense, given that you map it over a list of ntrees (i.e., k is an ntree, and you cannot compare it to v1).

General hint: if you have strange type errors that you cannot make sense of at first it often helps to narrow them down by adding type annotation, e.g. on function arguments or results.

The following code should work (untested):

fun subst(leaf d, v1, v2) = leaf(if d = v1 then v2 else d)
  | subst(node q, v1, v2) = node(map(fn k => subst(k, v1, v2), q))

With the right amount of currying, and using the standard map function, it can be even simpler:

fun subst v1 v2 (leaf d) = leaf(if d = v1 then v2 else d)
  | subst v1 v2 (node q) = node(map (subst v1 v2) q)

Also, as stylistic nit, it is good practice to capitalise constructors (Leaf and Node), to ease distinguishing them from variables in patterns.