计算列表中的元素,同时保留顺序

Question

我想知道是否有一种方法可以计算列表中的不同元素,并将计数分组为元组

[4,4,4,2,2,2,2,1,1,3]

要么

[4,2,4,4,2,1,2,2,1,3]

会屈服

[(4,3),(2,4),(1,2),(3,1)]

同时保留原始列表的顺序.

这个问题提到了在评论中保留顺序,但从未解决过这个问题.

这是我到目前为止的尝试:

import Data.List (nub)

countOccurance :: (Eq a) => a -> [a] -> Int
countOccurance x = length . filter (==x)

naiveCounter :: (Eq a) => [a] -> [(a, Int)]
naiveCounter l = map (\x -> (x, countOccurance x l)) $ nub l

但这似乎效率很低.有没有办法更有效地构建它(例如,通过遍历列表只有一次)？

谢谢.

Answer 1

你可以用Data.Map.Ordered.

import Data.Map.Ordered (OMap)
import qualified Data.Map.Ordered as OMap

-- insert L L With
--        ^ ^
--        |  `----- insert combined elements on the left of the sequence
--        `-------- insert new      elements on the left of the sequence
insertLLWith :: Ord k => (v -> v -> v) -> (k, v) -> OMap k v -> OMap k v
insertLLWith f (k, v) m = case OMap.lookup k m of
    Nothing -> (k, v) OMap.|< m
    Just v' -> (k, f v v') OMap.|< m

武装insertLLWith(可能应该进入带有一些变体的库 - 看起来通常很有用!),我们可以编写一个相当简单的折叠:

multisetFromList :: Ord a => [a] -> OMap a Int
multisetFromList = foldr (\x -> insertLLWith (+) (x, 1)) OMap.empty

在ghci:

> multisetFromList [4,4,4,2,2,2,2,1,1,3]
fromList [(4,3),(2,4),(1,2),(3,1)]
> multisetFromList [2,1,2] -- works with ungrouped lists, too
fromList [(2,2),(1,1)]