不同类型的任意多个列表的笛卡尔积

已经提出并回答了几个类似的问题。可以找到实例，例如：

Haskell中2个列表的笛卡尔积

笛卡尔积在Haskell的列表中

如何迭代计算笛卡尔积？

但是，我所发现的东西都没有完全回答我的问题。

题

在Haskell中，是否可能以及如何定义一个函数cartesianProduct，该函数任意（有限）地获取许多不同类型的列表，并在鼻子上输出其笛卡尔积？

背景

例如，在上面的链接中，可以找到一个cartesianProd_2优雅地吸收两个不同类型列表的列表：

cartesianProd_2 :: [a] -> [b] -> [(a,b)]
cartesianProd_2 list_A list_B = [(x,y) | x<-list_A, y<-list_B]

cartesianProd_n对于某些固定整数n，可以很容易地将其推广为。

但是，我希望我可以定义一个

cartesianProd (list_1,list_2) == (cartesianProd_2 list_1 list_2)
cartesianProd (list_1,list_2,list_3) == (cartesianProd_3 list_1 list_2 list_3)

-- and so on .. notice that list_i is a list of elements of type i.

一个直接的障碍，我遇到的是，我甚至不知道是什么类型的cartesianProd啊！它的域是（不同类型的列表）的元组！那我该怎么办？

编辑

如果在Haskell中无法做到，请提供（指向）指针。

1> luqui..：

---

如果您好奇如何操作类型级数据结构来解决上述问题，请继续阅读。如果您有实际问题要解决，请跳过所有这些废话，然后转到“ 现实中”部分。

可以做到的。要使我们起步，需要一点类型的机器。理想情况下，我想要以下签名：

cartesianProduct :: Tuple (Map [] ts) -> [Tuple ts]

这ts是类型的类型级别列表，并且Map是mapon列表的类型级别版本。 Tuple接受类型列表，并给出与这些类型的元组等效的类型。[Int, Char]例如，假设此签名将减少为：

cartesianProduct :: Tuple [ [Int], [Char] ] -> [Tuple [Int, Char]]
          -- morally, at least, equivalent to
                 :: ([Int], [Char]) -> [(Int, Char)]

希望您能看到符合我们意图的东西。因此，让我们开始吧：

{-# LANGUAGE TypeFamilies, DataKinds, TypeOperators, GADTs #-}

type family Map f xs where
    Map f '[] = '[]
    Map f (x ': xs) = f x ': Map f xs

data Tuple ts where
    Nil :: Tuple '[]
    Cons :: t -> Tuple ts -> Tuple (t ': ts)

这使用了许多高级功能。类型族，数据类型和GADT是关键字。

理想情况下，这应该足够了：

cartesianProduct :: Tuple (Map [] ts) -> [Tuple ts]
cartesianProduct Nil = [Nil]
cartesianProduct (Cons xs xss) = [ Cons x ys | x <- xs, ys <- xss ]

可悲的是，GHC无法弄清楚

• Could not deduce: ts ~ (t0 : ts0)
  from the context: Map [] ts ~ (t : ts1)

它不知道它Map是单射的¹（即使它显然是），因此它无法弄清楚ts当输入类型为Tuple (Map [] ts)且模式为时应该是什么Nil。这里的技术是使用singleton，这种类型可以帮助类型检查器摆脱这些情况。

data ListS ts where
    NilS :: ListS '[]
    ConsS :: ListS (t ': ts)

请注意，对于给定的类型列表，ts只有一种可能ListS存在ListS ts（因此为“单身”）。如果添加此单作为参数传递给我们的函数，那么typechecker知道，如果模式NilS则ts必须是[]（以及类似的缺点）：

cartesianProduct :: ListS ts -> Tuple (Map [] ts) -> [Tuple ts]
cartesianProduct NilS Nil = [Nil]
cartesianProduct (ConsS s) (Cons xs xss) = [ Cons x ys | x <- xs, ys <- xss ]

通过类型检查器。使用它需要一些工作：

example :: [Tuple '[Int, Char]]
example = cartesianProduct (ConsS (ConsS NilS)) (Cons [1,2] (Cons ['a','b'] Nil))

unTuple2 :: Tuple '[a,b] -> (a,b)
unTuple2 (Cons x (Cons y Nil)) = (x,y)

ghci> map unTuple2 example
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

可惜我们必须手动将其转换为真正的元组才能看到它的运行。但是派生一个Show实例Tuple将是另一个大麻烦。

事实上

但是，我们必须unTuple*在这种疯狂的结尾使用精确地知道我们有多少种类型的事实，这暗示着我们应该可以不用做些什么，而可以重新解决我们的问题。确实有这样一种改组，这就是很好的清单。

ghci> (,) <$> [1,2] <*> ['a','b']
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]
ghci> (,,) <$> [1,2] <*> ['a','b'] <*> [True, False]
[(1,'a',True),(1,'a',False),(1,'b',True),(1,'b',False),(2,'a',True) (2,'a',False),(2,'b',True),(2,'b',False)]

只要您可以同时提供一个n元函数来组合元素（在此为tupling函数(,)并(,,)发挥作用，但它可以是任何函数，例如(\x y -> x + 2*y) <$> [1,2] <*> [3,4]），则可在任意多个列表上使用适用的表示法。在实践中，这几乎可以肯定是解决需要n元异构笛卡尔积的问题的方式。这个答案中讨论的类型级别的奇特性是很少需要的，并且通常只会使事情变得不必要地复杂。

---

¹我尝试使用新的内射注解来解决此问题

type family Map f xs = r | r -> xs where
    Map f '[] = '[]
    Map f (x ': xs) = f x ': Map f xs

但这没有帮助。似乎它应该起作用了。

2> amalloy..：

---

不能这样做，正是由于您的最终原因：不同大小的元组是不相关的类型，您不能对其进行概括。出于相同的原因，Haskell没有通用zipWithN的N个不同类型的列表一起压缩。你必须要么接受一个[[a]]输入（要求所有输入是同一类型），或者专攻特定字段大小（cart2，cart3，cart4等）。

我想完整地说一下，原则上我认为您可以按照可行的方式将其重写为可变参数Text.Printf-代替N个元组，接受N个单独的参数。但是即使那样，我仍然不确定如何获得返回类似(x, y, z)而不是的形状的输入(x, (y, z))。

---

@学生，我不同意其他观点；我相信这是可能的，但是要表示此函数的类型，将需要大量的自定义类型级别的机制。我在想类似`cartesianProd :: Tuple（Map [] ts）-> [Tuple ts]`之类的东西。如此可爱，这种事情通常最终会让人感到痛苦。如果我记得的话，稍后我会写出答案（@'inging me随时提醒一下是否有一段时间）