从 SML 中的树创建列表时出现语法错误

问题描述

我有以下两种数据类型:

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

代码本身并不复杂.基本情况是如果它为空，则返回 null.如果它没有三个节点，那么我添加叶子的值并递归调用节点上的函数.如果是这样，我只是在节点上递归调用该函数而不添加叶子.

---

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.

它有效，因为它是空的，它通过向列表添加 nil 来结束搜索，这什么都不做.

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

我也尝试过其他情况，例如使用 and 而不是 andalso，以及其他版本的代码，例如

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?

旁注，为什么 1.0 = 2.0 不起作用，但在摘要中它说它适用于实数?它似乎只适用于整数，>、< 等也不起作用.

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.

推荐答案

语法错误:

1. 您不能重新绑定 nil.它是内置列表类型的保留关键字(即 nil = []).
2. 你不要像'a tree t1这样的类型前缀.您可以推断类型(通过不指定它并让类型检查器猜测它)，或者使用正确的语法对其进行注释(t1 : 'a tree).

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);

输入错误:

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

查看op::的类型:'a * 'a list ->'a list，以及你对 list12(a1)::list12(a2) 的使用，类型检查器必须找到一些 'a 使得 'a = '一个列表.这就像找到一个 x 使得 x = x + 1.很明显，无论 list12 返回什么，每一侧都有相同类型的东西.

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.

一个肮脏且低效的技巧是使用 @ 运算符(追加)代替.一种更简洁的方法是以这样一种方式折叠树，即折叠的函数可以访问整个节点(例如 在前几天的这篇 StackOverflow 帖子中):

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

您可以将其合并为一个函数 - 这种方式将遍历逻辑分离为 para，并将累积逻辑分离为 list12 的辅助函数.

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.

为什么 1.0 = 2.0 不起作用，但在摘要中它说它适用于实数?

我不知道你指的是什么摘要.这个问题在这里回答:为什么我不能在标准 ML 中比较实数?(这个答案最初放在这里，但移到那里，因为它是一个单独的问题.)

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.)

这篇关于从 SML 中的树创建列表时出现语法错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！