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

Question

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

1. Cartesian product of 2 lists in Haskell
2. Cartesian product over a list of lists in Haskell
3. How can I compute a Cartesian product iteratively?

但是，我发现的这些都没有完全回答我的问题。

问题

在Haskell中，是否可能以及如何定义一个函数cartesianProduct，该函数采用任意(有限)许多列表不同类型并输出他们的笛卡尔积在 Nose 上？

背景

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

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

对于某个固定整数 n，我们可以轻松地将其推广到 cartesianProd_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 中不可能，请包含一个(指向 a 的指针)证明。

Answer 1

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

这是可以做到的。需要一些类型级别的机制才能让我们起步。理想情况下，我想要以下签名:

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

这里ts是类型级别的类型列表，并且 Map是 map 的类型级版本在列表上。 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 。这里的技术是使用单例，这是一种可以帮助类型检查器摆脱这些情况的类型。

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

请注意，对于给定的类型列表 ts ，只有一种可能 ListS可以居住ListS ts (因此“单例”)。如果我们将此单例作为参数添加到我们的函数中，那么类型检查器就会知道，如果模式是 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 元函数来组合元素(这里元组函数 (,) 和 (,,) 发挥该作用，但它可以是任何函数，例如 (\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

但这没有帮助。看起来应该有效。