基于数据构造函数的分区列表

Question

假设我有以下内容：

data D = A Int | B Int deriving Show

我有一个功能

simplify :: [D] -> [D]

我的目标是简化创建一个新列表，它将包含数据A的所有值相加(成数据A的单个值(，并保持B数据不变。

例如，[A 1, A 2, A 3, B 1, A 4, B 2]会变得[A 10, B 1, B 2]。

我知道我可以用折叠来做到这一点：

A (foldl (+) 0 [x | A x <- ll]) : [B x | B x <- ll]

但这涉及两次浏览列表以寻找构造函数。 我想知道是否有一种方法可以使用分区，我可以将列表分为具有数据A的列表和没有数据的列表。

Answer 1

如果您愿意始终将A值放在Bs之前，这似乎是可行的。

simplify :: [D] -> [D]
simplify = uncurry (:) . foldr f (A 0, [])
where
f (A x) ((A n), acc) = (A (n+x),   acc)
f b     (a    , acc) = (a      , b:acc)

虽然老实说我认为uncurry (:)在这里是一个错误，你的最终类型应该是：

simplify :: [D] -> (D, [D])

Answer 2

你不需要分区，只需要左折：

import Data.List (mapAccumL)
simplify :: [D] -> [D]
simplify = f . mapAccumL g 0 
where
g acc (A i) = acc `seq` (acc+i, [])
g acc b     = (acc,  [b])
f (acc, ys) = A acc : concat ys