如何仅从列表中获取唯一元素？

Question

我有一个清单，比如说[1,2,3,4,3,2,4]。我想输出每个元素一次，例如[1,2,3,4]。我怎样才能在 Haskell 中做到这一点？

Answer 1

您可以使用nub :: Eq a => [a] -> [a]which 作为uniqness 过滤器。然而，它需要O(n ² )，因为它不使用像哈希集这样的数据结构。

例如：

Prelude Data.List> nub [1,2,3,4,3,2,4]
[1,2,3,4]

如果元件是一种类型，是一个成员Hashable类型类，可以使用例如hashNub :: (Eq a, Hashable a) => [a] -> [a]以执行一个uniqness滤波器为O（n log n）的：

Prelude ClassyPrelude> hashNub [1,2,3,4,3,2,4]
[1,2,3,4]

Answer 2

您可以使用 Data.set 使用集合来做到这一点：

import qualified Data.Set as Set
lst = [1,2,3,4,1,2,3]
y =  Set.fromList lst

输出是：

y
=> fromList [1,2,3,4]

Answer 3

有一个nub功能正是为此。但是，它的复杂度为 O(n^2)，不太好。如果是数字（或任何Ord类型），您可以unique像这样创建自己的函数：

unique :: Ord a => [a] -> [a]
unique = map head . group . sort

您需要导入Data.List. 它的作用是这样的：

sort [1,2,3,1,2] -> [1,1,2,2,3]        -- to order the elements
group [1,1,2,2,3] -> [[1,1],[2,2],[3]] -- to group equal ones
map head [[1,1],[2,2],[3]] -> [1,2,3]  -- to take first of groups

这具有 O(n log n) 的复杂度，这是一种更好的方式。