haskell - 如何有效地过滤 Haskell 中的一对列表？

Question

我正在研究关于 Programming Praxis 的一个简单问题:从列表中删除所有重复项而不更改顺序。假设元素在类 Ord 中，我想出了以下内容:

import Data.Set (Set)  
import qualified Data.Set as Set

buildsets::Ord a => [a] -> [Set a]
buildsets = scanl (flip Set.insert) Set.empty

nub2::Ord a => [a] -> [a]
nub2 thelist = map fst $ filter (not . uncurry Set.member) (zip thelist (buildsets thelist))

如您所见，buildsets 函数让我完成了大部分工作，但将所有内容放在一起的最后一步 (nub2) 看起来绝对糟糕。有没有更简洁的方法来完成此操作？

Answer 1

由于我们必须过滤列表并且我们可能应该使用一些集合来保存记录，我们不妨使用带有状态 monad 的 filterM:

import qualified Data.Set as S
import Control.Monad.State.Strict

nub2 :: Ord a => [a] -> [a]
nub2 = (`evalState` S.empty) . filterM go where
    go x = state $ \s -> if S.member x s
        then (False, s)
        else (True, S.insert x s) 

如果我想稍微玩一下这个函数，我会执行以下操作:

import Control.Arrow (&&&)

nub2 = (`evalState` S.empty) . filterM (\x -> state (S.notMember x &&& S.insert x))