我想创建一个简单的SML程序，从左到右遍历一个列表。让我说我有一个K个不同类型的N项列表。例如列表1 3 1 3 1 3 3 2 2 1有10个3(1,2,3)类型的数字。
我想要的是从左到右遍历这个列表，当我找到所有K个不同的数字时停止。在这种情况下，我会在绊倒前2后立即停止。
这可以通过在每个步骤中分割头部和尾部的列表并处理头部元素来完成。但是，我怎样才能跟踪我找到的不同数字？
这可以通过简单地保持计数器和具有K个元素的布尔数组在C / C ++中完成。如果我偶然发现了一个与bool[i]=false的元素，我认为它是真的和counter=counter+1。
虽然说明数组不是SML的最佳选择所以我想知道我是否必须使用另一种数据结构，或者我是否必须创建一个新函数来检查每次我是否曾经看过这个元素（这会花费成本）时间复杂度）。
我怎么能跟踪我找到的不同数字？
[...]在C / C ++中由[...]带有K个元素的布尔数组
抽象地，我会调用你想要的数据结构。
我会给你两个答案，一个使用稀疏容器，另一个使用位集。
我会用一个列表来跟踪你已经看过的元素：
fun curry f x y = f (x, y)
val empty = []
fun add x set = curry op:: x set
fun elem x set = List.exists (curry op= x) set
fun seen k xs =
let fun seen_ 0 _ _ = true
| seen_ _ [] _ = false
| seen_ k (x::xs) set =
if elem x set
then seen_ k xs set
else seen_ (k-1) xs (add x set)
in seen_ k xs empty end
您还可以使用平衡二叉树作为集合类型;这会减少查找到O（lg n）。使用实际容器（列表或树）而不是位数组的优点是sparse arrays/matrices。这适用于''a lists。
[...]带有K个元素的布尔数组[...]
如果我偶然发现了一个元素我[...]
在此之前，您还没有说过，元素总是从0到K-1的无符号整数，如果它们应该由长度为K的数组中的唯一索引表示，那么这将是一个要求。
对于无符号整数（单词），SML有一个名为Word / word的模块/类型。添加此约束，输入列表应具有类型word list而不是''a list。
当你在许多命令式编译语言中创建一个基本类型数组时，你会变得可变，unboxed arrays。 SML的Array类型也是可变的，但是这样的数组中的每个bool都会被加框。
获取不可变的，未装箱的位数组的简单方法是在IntInf（SML / NJ; implementations vary）上使用按位运算;它会自动增长，因为有点翻转。这可能看起来像：
fun bit x = IntInf.<< (1, x)
val empty = IntInf.fromInt 0
fun add x set = IntInf.orb (set, bit x)
fun elem x set = IntInf.> (IntInf.andb (set, bit x), 0)
函数seen将是相同的。
事实上k递归递减并且set动态增长意味着你不仅限于[0，K-1]范围内的元素，这就是大小为K的数组的情况。
使用示例：
- seen 5 [0w4, 0w2, 0w1, 0w9];
val it = false : bool
- seen 5 [0w1, 0w2, 0w3, 0w4, 0w8];
val it = true : bool
如果元素很大，此解决方案会占用大量内存：
- seen 1 [0w100000000];
*eats my memory slowly*
val it = true : bool
您可以做的其他事情：
structure BitSet = struct ... end，用操作empty，add和elem封装抽象类型，隐藏特定的实现（无论是IntInf.int，还是bool Array.array或''a list）。fun fold_until f e xs = ...，它提取seen_的递归方案，以避免手动递归;一个常规的foldl是不够的，因为它一直持续到列表为空。您可以使用error-aware return type或使用异常来构建它。