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

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

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))