Syntax error in creating a list from a tree in SML

Question

I have the following two datatypes:

datatype leaf = Slist of string list | Real of real | nil;
datatype 'a tree = Empty |  Node of leaf * 'a tree * 'a tree * 'a tree;

The code below goes through all trees of length one/two and forms a list of the values in the leafs.

fun list12(Empty:'a tree) = nil
  | list12(Node(leaf leaf1, 'a tree a1, 'a tree a2, 'a tree a3)) =
    if (not(a1 = Empty) andalso not(a2 = Empty) andalso not(a3 = Empty))
    then list12(a1)::list12(a2)::list12(a3)
    else leaf1::list12(a1)::list12(a2)::list12(a3);

The issue is, I get syntax errors such as

stdIn:94.59-94.66 Error: syntax error: deleting  TYVAR ID
stdIn:94.71-94.78 Error: syntax error: deleting  TYVAR ID
stdIn:94.83-94.93 Error: syntax error: deleting  TYVAR ID ID
stdIn:94.93-94.97 Error: syntax error: deleting  RPAREN RPAREN EQUALOP
stdIn:94.98-94.102 Error: syntax error: deleting  IF LPAREN
stdIn:94.109-94.116 Error: syntax error: deleting  EQUALOP ID

---

The code in itself isn't complicated. Base case is if it's empty, returns null. If it doesn't have three nodes, then I add the value of the leaf and recursively call the function on the nodes. If it does, I just recursively call the function on the nodes without adding the leaf.

It works because it it's empty, it ends that search by adding nil to the list, which does nothing.

I've also tried other cases such as using and instead of andalso, as well as other versions of the code such as

  | list12(Node(leaf1, Empty, Empty, Empty)) = nil
  | list12(Node(leaf2, a1, Empty, Empty)) = leaf2::list12(a1);
  | list12(Node(leaf3, b1, b2, Empty)) = leaf3::list12(b1)::list12(b2);
  | list12(Node(leaf4, c1, c2, c3)) = list12(c1)::list12(c2)::list12(c3);

but I've found that the above doesn't match all cases.

Any idea on why the syntax errors are appearing?

---

Side note, why doesn't 1.0 = 2.0 work, but in the summaries it says it works for reals? It only appears to work for integers, and >, <, and so on don't work either.

Answer 1

Syntax errors:

1. You can't rebind nil. It's a reserved keyword for the built-in list type (i.e. nil = []).
2. You don't prefix types like 'a tree t1. You either infer the type (by not specifying it and letting the type-checker guess it), or you annotate it with the proper syntax (t1 : 'a tree).

Assuming we get the syntax errors out of the way, rely a little more on inference by removing the type annotations, and add a little formatting, this is how your code might look like:

datatype leaf = Slist of string list | Real of real | Nil;
datatype 'a tree = Empty | Node of leaf * 'a tree * 'a tree * 'a tree;

fun list12 Empty = []
  | list12 (Node(leaf1, a1, a2, a3)) =
    if (not(a1 = Empty) andalso not(a2 = Empty) andalso not(a3 = Empty))
    then list12(a1)::list12(a2)::list12(a3)
    else leaf1::list12(a1)::list12(a2)::list12(a3);

Type errors:

!     then list12(a1)::list12(a2)::list12(a3)
!          ^^^^^^^^^^
! Type clash: expression of type
!   'a list
! cannot have type
!   'a
! because of circularity

Looking at the type of op:: : 'a * 'a list -> 'a list, and your use of list12(a1)::list12(a2), the type-checker must find some 'a such that 'a = 'a list. That is like finding an x such that x = x + 1. Clearly, whatever list12 returns, you have something of the same kind on each side.

A dirty and inefficient trick is to use the @ operator (append) instead. A neater way is to fold across the tree in such a way that the function with which you fold has access to the entire node (like in this StackOverflow post from the other day):

fun para f e Empty = e
  | para f e0 (t0 as Node (x, t1, t2, t3)) =
    let val e1 = f (e0, t0)
        val e2 = para f e1 t1
        val e3 = para f e2 t2
        val e4 = para f e3 t3
    in e4 end

fun isNode (Node _) = true
  | isNode Empty = false

fun list12 t =
    let fun extract (xs, Empty) = xs
          | extract (xs, Node (x, t1, t2, t3)) =
            if isNode t1 andalso isNode t2 andalso isNode t3
            then x::xs
            else xs
    in para extract [] t end

You could collapse this into just one function - this way is separating the traversal logic into para and the accumulation logic into list12's helper function.

Comparing reals

Why doesn't 1.0 = 2.0 work, but in the summaries it says it works for reals?

I don't know what summaries you refer to. This question is answered here: Why can't I compare reals in Standard ML? (this answer was originally placed here, but was moved there, since it's a separate question.)