Haskell-将并集列表转换为列表元组

Question

我正在寻找一种将列表转换为n元组的方法，在不相交的并集中，n个构造函数中的每一个都有一个列表。标准库专门为Either定义了一个类似的函数：

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 ([], [], [], [])后，我想到了一件事，那就是定义一个monoid，其中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)

Generically将来将从GHC.Generics导出。通过广义逐点提升将Classify定义为半群和半群。

有了这个，你只需要一个分类器函数，它将MySum分类为Classify，你可以根据foldMap定义partition

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

Answer 2

由于函数是从和到乘积的转换，因此使用generics-sop有一个相当简单的实现。这是一个库，它用更专业的类型来增强GHCs泛型，使代数三元类型(即乘积和)的归纳更简单。

首先，一个前奏：

{-# LANGUAGE DeriveGeneric, StandaloneDeriving #-}
import Generics.SOP hiding ((:.:))
import qualified GHC.Generics as GHC
import GHC.Generics ((:.:)(..))

partitionSum :: (Generic t) => [t] -> NP ([] :.: NP I) (Code t)

这是您要编写的方法。让我们检查一下它的类型。

• 单个参数是某个泛型类型的列表。相当简单。请注意，Generic是来自generics-sop的，而不是来自GHC
• 返回的值是一个n元乘积(n元组)，其中每个元素都是一个由NP I组成的列表(它本身就是n元乘积，因为通常代数数据类型构造函数可能有多个字段)
• CCD_ 16是CCD_ 17的乘积类型表示的和。这是一个类型列表。例如CCD_ 18。CCD_ 19的一般值表示是CCD_；代码">

要实现这一点，我们可以将每个t转换为其通用表示，然后折叠得到的列表：

partitionSum = partitionSumGeneric . map from
partitionSumGeneric :: SListI xss => [SOP I xss] -> NP ([] :.: NP I) xss
partitionSumGeneric = foldr ((SOP x) -> classifyGeneric x) emptyClassifier

partitionSumGeneric与partitionSum基本相同，但对值的通用表示进行操作。

现在来看有趣的部分。让我们从我们阵营的基本情况开始。每个位置都应包含空列表。generics-sop提供了一种方便的机制，用于在每个位置生成具有统一值的产品类型：

emptyClassifier :: SListI xs => NP ([] :.: NP I) xs
emptyClassifier = hpure (Comp1 [])

递归情况如下：如果该值在索引k处具有标记，则将该值添加到累加器中索引k处的列表中。我们可以在sum类型(现在是通用的，所以NS (NP I) xs类型的值是乘积的和)和累加器上同时递归。

classifyGeneric :: NS (NP I) xss -> NP ([] :.: NP I) xss -> NP ([] :.: NP I) xss
classifyGeneric (Z x)  (Comp1 l :* ls) = (Comp1 $ x : l) :* ls
classifyGeneric (S xs) (      l :* ls) =              l  :* classifyGeneric xs ls

您的示例添加了一些数据，使其更有趣：

data MySum
= CaseA A
| CaseB B
| CaseC C
| CaseD D
-- All that's needed for `partitionSum' to work with your type
deriving instance GHC.Generic MySum
instance Generic MySum
data A = A Int deriving Show
data B = B String Int deriving Show
data C = C deriving Show
data D = D Integer deriving Show
test = partitionSum $
[CaseD $ D 0, CaseB $ B "x" 1, CaseA $ A 2, CaseA $ A 3, CaseB $ B "y" 4, CaseB $ B "z" 5]

结果是：

Comp1 {unComp1 = [I (A 2) :* Nil,I (A 3) :* Nil]} :* Comp1 {unComp1 = [I (B "x" 1) :* Nil,I (B "y" 4) :* Nil,I (B "z" 5) :* Nil]} :* Comp1 {unComp1 = []} :* Comp1 {unComp1 = [I (D 0) :* Nil]} :*Nil