英文:
Why does the right-hand-side of clause not agree with function result type?
问题
Starting with this data type defined in SML --
在SML中定义了以下数据类型--
datatype exp = Constant of int
| Negate of exp
| Add of exp * exp
| Multiply of exp * exp
I've written this function which is supposed to list all constants in a given exp:
我写了这个函数,它应该列出给定exp中的所有常量:
fun lst_con e =
case e of
Constant i => [i]
| Negate e2 => [~ (lst_con e2)]
| Add(e1, e2) => [(lst_con e1)] @ [(lst_con e2)]
| Multiply(e1, e2) => [(lst_con e1)] @ [(lst_con e2)]
However, it is returning this error:
然而,它返回了以下错误:
Error: right-hand-side of clause does not agree with function result type [tycon mismatch]
expression: int list
result type: int
I don't understand why. Any explanation would be greatly appreciated!
我不明白为什么。非常感谢任何解释!
英文:
Starting with this data type defined in SML --
datatype exp = Constant of int
| Negate of exp
| Add of exp * exp
| Multiply of exp * exp
I've written this function which is supposed to list all constants in a given exp:
fun lst_con e =
case e of
Constant i => [i]
| Negate e2 => [~ (lst_con e2)]
| Add(e1, e2) => [(lst_con e1)] @ [(lst_con e2)]
| Multiply(e1, e2) => [(lst_con e1)] @ [(lst_con e2)]
However, it is returning this error:
Error: right-hand-side of clause does not agree with function result type [tycon mismatch]
expression: int list
result type: int
I don't understand why. Any explanation would be greatly appreciated!
答案1
得分: 3
如molbdnilo在评论中提到的,lst_con
应该返回一个 int
值的列表:一个 int list
。
在你的 Negate e2
情况下,你试图对整个列表进行否定(使用 ~
),但 op~
期望一个 int
,所以类型不匹配。
此外,你的第一个情况返回一个 int list
,但其他情况返回 int list list
。
另外,你可能考虑过多了。如果你有 Negate (Constant 42)
,那么在该表达式中,负数42并不作为常数存在。只有 42
存在。
你可能更想写类似这样的代码:
fun lst_con e =
case e of
Constant i => [i]
| Negate e2 => lst_con e2
| Add(e1, e2) => lst_con e1 @ lst_con e2
| Multiply(e1, e2) => lst_con e1 @ lst_con e2;
我们可以更简洁地写成:
fun lst_con(Constant i) => [i]
| lst_con(Negate e2) => lst_con e2
| lst_con(Add(e1, e2)) => lst_con e1 @ lst_con e2
| lst_con(Multiply(e1, e2)) => lst_con e1 @ lst_con e2;
效率问题
另外需要注意的是,这个函数不是尾递归的,而且以这种方式使用列表附加会导致非常糟糕的性能特征:O(n^2)。
我们可以通过使用一个要处理的值的堆栈和一个累加器来实现O(n)的运行时性能。
fun lst_con'(Constant i, acc, []) = List.rev(i :: acc)
| lst_con'(Constant i, acc, x::xs) = lst_con'(x, i :: acc, xs)
| lst_con'(Negate e2, acc, stack) = lst_con'(e2, acc, stack)
| lst_con'(Add(e1, e2), acc, stack) = lst_con'(e1, acc, e2 :: stack)
| lst_con'(Multiply(e1, e2), acc, stack) = lst_con'(e1, acc, e2 :: stack);
fun lst_con(e) = lst_con'(e, [], []);
如果我们检查一个测试案例的评估:
lst_con(Multiply(Add(Negate(Constant 2), Constant 6), Add(Multiply(Constant 1, Constant 1), Constant 7)))
lst_con'(Multiply(Add(Negate(Constant 2), Constant 6), Add(Multiply(Constant 1, Constant 1), Constant 7)), [], [])
lst_con'(Add(Negate(Constant 2), Constant 6), [], [Add(Multiply(Constant 1, Constant 1), Constant 7)])
lst_con'(Negate(Constant 2), [], [Constant 6, Add(Multiply(Constant 1, Constant 1), Constant 7)]
lst_con'(Constant 2, [], [Constant 6, Add(Multiply(Constant 1, Constant 1), Constant 7)]
lst_con'(Constant 6, [2], [Add(Multiply(Constant 1, Constant 1), Constant 7)]
lst_con'(Add(Multiply(Constant 1, Constant 1), Constant 7), [6, 2], []
lst_con'(Multiply(Constant 1, Constant 1), [6, 2], [Constant 7]
lst_con'(Constant 1, [6, 2], [Constant 1, Constant 7]
lst_con'(Constant 1, [1, 6, 2], [Constant 7]
lst_con'(Constant 7, [1, 1, 6, 2], []
List.rev([7, 1, 1, 6, 2])
[2, 6, 1, 1, 7]
英文:
As molbdnilo has hinted in comments, lst_con
is expected to return a list of int
values: an int list
.
In your Negate e2
case, you're trying to negative (with ~
), a entire list. But op~
expects an int
, so the types don't work.
You also have your first case returning an int list
but then the other cases return int list list
.
Additionally, you may be overthinking this. If you have Negate (Constant 42)
then negative 42 doesn't exist in that expression as a constant. Only 42
does.
You probably meant to write something more like:
fun lst_con e =
case e of
Constant i => [i]
| Negate e2 => lst_con e2
| Add(e1, e2) => lst_con e1 @ lst_con e2
| Multiply(e1, e2) => lst_con e1 @ lst_con e2;
Which we can write more concisely as:
fun lst_con(Constant i) => [i]
| lst_con(Negate e2) => lst_con e2
| lst_con(Add(e1, e2)) => lst_con e1 @ lst_con e2
| lst_con(Multiply(e1, e2)) => lst_con e1 @ lst_con e2;
Efficiency Issues
As an additional note, we can see that this function is not tail-recursive, and the use of list append in this way leads to very poor performance characteristics: O(n^2).
We can achieve this with O(n) runtime performance by using a stack of values left to process and an accumulator.
fun lst_con'(Constant i, acc, []) = List.rev(i :: acc)
| lst_con'(Constant i, acc, x::xs) = lst_con'(x, i :: acc, xs)
| lst_con'(Negate e2, acc, stack) = lst_con'(e2, acc, stack)
| lst_con'(Add(e1, e2), acc, stack) = lst_con'(e1, acc, e2 :: stack)
| lst_con'(Multiply(e1, e2), acc, stack) = lst_con'(e1, acc, e2 :: stack);
fun lst_con(e) = lst_con'(e, [], []);
If we examine how a test case evaluates:
lst_con(Multiply(Add(Negate(Constant 2), Constant 6), Add(Multiply(Constant 1, Constant 1), Constant 7)))
lst_con'(Multiply(Add(Negate(Constant 2), Constant 6), Add(Multiply(Constant 1, Constant 1), Constant 7)), [], [])
lst_con'(Add(Negate(Constant 2), Constant 6), [], [Add(Multiply(Constant 1, Constant 1), Constant 7)])
lst_con'(Negate(Constant 2), [], [Constant 6, Add(Multiply(Constant 1, Constant 1), Constant 7)]
lst_con'(Constant 2, [], [Constant 6, Add(Multiply(Constant 1, Constant 1), Constant 7)]
lst_con'(Constant 6, [2], [Add(Multiply(Constant 1, Constant 1), Constant 7)]
lst_con'(Add(Multiply(Constant 1, Constant 1), Constant 7), [6, 2], []
lst_con'(Multiply(Constant 1, Constant 1), [6, 2], [Constant 7]
lst_con'(Constant 1, [6, 2], [Constant 1, Constant 7]
lst_con'(Constant 1, [1, 6, 2], [Constant 7]
lst_con'(Constant 7, [1, 1, 6, 2], []
List.rev([7, 1, 1, 6, 2])
[2, 6, 1, 1, 7]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论