sml - 如何在没有 cons 运算符的情况下检查“集合”中的项目

Question

这是一个代码示例，我认为它可以在作为列表实现的集合数据类型中正常工作：

fun newSet() = nilset;

fun isMember (k, x::xs) = if k = x then true else isMember (k, xs)
  | isMember (k, nilset) = false;

问题是我不能将它作为一个列表来实现。下面是我的集合的实现代码。

abstype ''a set = nilset | st of ''a * ''a set

::如果是针对列表，我如何递归地执行此操作和其他设置操作？如果不是，为什么会抛出异常？我在使用时得到这个::：

! Type clash: pattern of type
!   ''a set
! cannot have type
!   ''b list

谢谢你的帮助。

score 2 · Accepted Answer

这也不例外。这是一个类型错误，表示您不能使用::属于'a listwith 的cons 构造函数'a set。

假设您有两个构造函数Nilset和Set递归数据类型：

datatype 'a set = Nilset | Set of 'a * 'a set

您应该按照数据类型的递归结构来定义isMember：

fun isMember (k, Set(x, xs)) = k = x orelse isMember (k, xs)
  | isMember (k, Nilset) = false

当然，要认真使用Set，您应该查看Set 结构。

1 回答 1