Poly/ML编程：实现无重复元素列表的元素计数函数

嘿，我来帮你搞定这个函数式编程练习！要实现类型为''a list -> int的函数，核心就是先过滤掉列表中的重复元素，再统计剩余元素的个数。下面给你两种实用的实现方式，分别适合快速开发和理解递归思路：

方法一：利用Poly/ML内置的Set结构（简洁高效） #

Poly/ML提供了Set模块，它可以自动处理可比较类型（也就是你的''a类型，支持相等比较）的去重操作。这个方法代码简洁，性能也更好：

fun countUnique lst =
    let
        val uniqueElements = Set.fromList lst  (* 将列表转换为集合，自动去重 *)
    in
        Set.size uniqueElements  (* 返回集合的元素数量 *)
    end

说明 #

• Set.fromList会把列表里的重复元素全部剔除，只保留每个元素的唯一实例
• Set.size直接返回集合的元素个数，这就是我们要的不重复元素数量
• 这个方法的时间复杂度是O(n log n)，适合处理较大的列表

方法二：手动递归实现（适合练习函数式编程思路） #

如果是为了练习递归和函数式思维，我们可以手动维护一个“已见过元素”的列表，逐个检查元素是否重复：

fun countUnique lst =
    let
        (* 辅助递归函数：参数1是待处理的剩余列表，参数2是已经收集的不重复元素 *)
        fun helper [] _ = 0
          | helper (current::rest) seen =
            if List.exists (fn elem => elem = current) seen
            then helper rest seen  (* 当前元素已见过，跳过，继续处理剩余列表 *)
            else 1 + helper rest (current::seen)  (* 新元素，计数加1并加入已见列表 *)
    in
        helper lst []  (* 初始调用：待处理列表是原列表，已见列表为空 *)
    end

说明 #

• List.exists用来检查当前元素是否已经在“已见过”的列表里
• 每次遇到新元素时，我们把计数加1，并将该元素加入“已见列表”，避免后续重复计数
• 这个方法的时间复杂度是O(n²)，因为每次检查元素是否存在都要遍历一次“已见列表”，适合小规模列表或者练习使用

你可以根据自己的需求选择其中一种方法，两种都能满足题目要求的类型和功能哦！

内容的提问来源于stack exchange，提问作者johnnyroozak