嵌套列表去重方法及Haskell flatten2set函数实现求助

问题1：移除嵌套列表中的重复元素 #

其实这个需求可以拆成两步走：先把嵌套的列表（也就是[[a]]类型）展平成普通的单列表[a]，再对单列表去重。当然你也可以直接写个函数一步处理，但先展平再去重的逻辑更清晰，也更容易维护——毕竟你已经有flatten函数了，刚好能用上。

问题2：实现flatten2set函数（基于已有flatten，不使用nub） #

首先，先解决你之前自定义nub报错的问题：大概率是类型约束没加或者辅助函数的逻辑有问题。比如Haskell判断元素是否重复需要Eq类型类支持，如果你的自定义去重函数没加Eq a的约束，编译器就会报错。

先给你一个正确的自定义去重函数，我们叫它myNub：

-- 自定义去重函数，完全不依赖标准库的nub
myNub :: Eq a => [a] -> [a]
myNub = go []
  where
    -- 辅助函数go：第一个参数是已经见过的元素列表，第二个是待处理的列表
    go _ [] = []  -- 待处理列表为空，直接返回空
    go seen (x:xs)
      | x `elem` seen = go seen xs  -- 元素已经见过，跳过，继续处理剩下的
      | otherwise     = x : go (x:seen) xs  -- 元素没见过，保留它，把它加入已见过列表再处理剩下的

然后，基于你已有的flatten函数，flatten2set就非常简单了——直接把两个函数组合起来就行：

-- 假设你的flatten函数是类似这样的（如果你的实现不同，不影响，只要类型是[[a]] -> [a]就行）
flatten :: [[a]] -> [a]
flatten [] = []
flatten (x:xs) = x ++ flatten xs

-- 核心的flatten2set：先展平，再用自定义去重
flatten2set :: Eq a => [[a]] -> [a]
flatten2set = myNub . flatten

如果习惯写显式参数的形式，也可以写成：

flatten2set nestedList = myNub (flatten nestedList)

为什么之前的自定义nub会报错？ #

举个反例，如果你的代码没加Eq a约束：

-- 错误示例：缺少Eq约束，编译器不知道怎么判断x是否在seen里
myNubWrong :: [a] -> [a]
myNubWrong = go []
  where
    go _ [] = []
    go seen (x:xs)
      | x `elem` seen = go seen xs
      | otherwise     = x : go (x:seen) xs

编译这个就会报类似你遇到的错误，因为elem函数需要Eq a的约束。只要加上Eq a =>就没问题了。

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