基于数据构造器的分区表

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]。

我知道我可以用 foldl 做到这一点：

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

但这需要遍历列表两次来寻找构造函数。我想知道是否有一种使用分区的方法，我可以在其中将列表分成包含数据 A 和不包含数据的列表。

Answer 1

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

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

基于数据构造器的分区表

Partition list based on data constructor

haskell

partition