Haskell - 将联合列表转换为列表元组

Question

我正在寻找一种将列表转换为 n 元组的方法，其中一个列表用于不相交联合中的 n 个构造函数中的每一个。标准库专门为Eithers定义了一个类似的函数：

partitionEithers :: [Either a b] -> ([a], [b])

我正在寻找解决具有以下要求的广义问题的技术：

• 写起来方便
• 尽可能少的样板文件
• 一次性处理列表
• 数据类型泛型、元编程、现有库等都是允许的

例子

这是一个示例规范，其中包含两个建议的解决方案：

partitionSum :: [MySum] -> ([A], [B], [C], [D])

data MySum
  = CaseA A
  | CaseB B
  | CaseC C
  | CaseD D

data A = A deriving Show
data B = B deriving Show
data C = C deriving Show
data D = D deriving Show

-- expect "([A,A],[B,B,B],[],[D])"
test :: IO ()
test = print . partitionSum $
  [CaseD D, CaseB B, CaseA A, CaseA A, CaseB B, CaseB B]

第一次尝试：n 个遍历列表n次的列表推导式。

partitionSum1 :: [MySum] -> ([A], [B], [C], [D])
partitionSum1 xs =
  ( [a | CaseA a <- xs]
  , [b | CaseB b <- xs]
  , [c | CaseC c <- xs]
  , [d | CaseD d <- xs]
  )

第二次尝试：单次遍历输入列表。我必须手动将状态穿过折叠，这使得解决方案有点重复并且写起来很烦人。

partitionSum2 :: [MySum] -> ([A], [B], [C], [D])
partitionSum2 = foldr f ([], [], [], [])
  where
    f x (as, bs, cs, ds) =
      case x of
        CaseA a -> (a : as, bs, cs, ds)
        CaseB b -> (as, b : bs, cs, ds)
        CaseC c -> (as, bs, c : cs, ds)
        CaseD d -> (as, bs, cs, d : ds)

Answer 1

除了Representable答案之外：

我看到的一件事foldr f ([], [], [], [])是定义一个幺半群，其中 nil 情况是mempty

{-# DerivingVia #-}
..
import GHC.Generics (Generically(..), ..)

type Classify :: Type
type Classify = C [A] [B] [C] [D]
  deriving
  stock Generic

  deriving (Semigroup, Monoid)
  via Generically Classify

-- mempty = C [] [] [] []
-- C as bs cs ds <> C as1 bs1 cd1 ds1 = C (as ++ as1) (bs ++ bs1) (cs ++ cs1) (ds ++ ds1)

GenericallyGHC.Generics未来将被出口。它Classify通过通用的逐点提升定义为半群和幺半群。

有了这个，您所需要的只是一个分类器函数，它将 a 分类MySum为Classify，您可以partition根据foldMap

classify :: MySum -> Classify
classify = \case
  SumA a -> C [a] [] [] []
  SumB b -> C [] [b] [] []
  SumC c -> C [] [] [c] []
  SumD d -> C [] [] [] [d]

partition :: Foldable f => f MySum -> Classify
partition = foldMap classify