haskell - 在 Haskell 中计算 N-Ary(使用不同类型!!)笛卡尔积

Question

我知道函数sequence可以处理[[1, 2], [3, 4]] -> [[1, 3], [1, 4], [2, 3], [2, 4]]问题。

但我认为真正的笛卡尔积应该处理 ([1, 2], ['a', 'b']) -> [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]问题，并且应该关心每个列表的类型是否不同，或者外部元组的类型(&大小)。

所以，cartProd我想要的函数有这样的类型:([a1], [a2], [a3] ...) -> [(a1, a2, a3 ...)]
我知道类型系统存在一些问题。但是有没有办法实现这个cartProd的完美版本？ ?

Answer 1

这里可以使用通常的异构列表:

{-# LANGUAGE
   UndecidableInstances, GADTs,
   TypeFamilies, MultiParamTypeClasses,
   FunctionalDependencies, DataKinds, TypeOperators,
   FlexibleInstances #-}

import Control.Applicative

data HList xs where
  Nil  :: HList '[]
  (:>) :: x -> HList xs -> HList (x ': xs)
infixr 5 :>

-- A Show instance, for illustrative purposes here. 
instance Show (HList '[]) where
  show _ = "Nil"

instance (Show x, Show (HList xs)) => Show (HList (x ': xs)) where
  show (x :> xs) = show x ++ " : " ++ show xs

我们通常在 HLists 上写函数使用类，有一个 Nil 的实例另一个用于 :>案子。但是，仅针对单个用例(即此处的笛卡尔积)创建一个类并不好，因此让我们将问题推广到应用排序:

class Applicative f => HSequence f (xs :: [*]) (ys :: [*]) | xs -> ys, ys f -> xs where
  hsequence :: HList xs -> f (HList ys)

instance Applicative f => HSequence f '[] '[] where
  hsequence = pure

instance (Applicative g, HSequence f xs ys, y ~ x, f ~ g) =>
         HSequence g (f x ': xs) (y ': ys) where
  hsequence (fx :> fxs) = (:>) <$> fx <*> hsequence fxs

注意 ~ 的使用实例定义中的约束。它极大地帮助了类型推断(以及类声明中的功能依赖)；总体思路是将尽可能多的信息从实例头部移动到约束条件，因为这让 GHC 延迟解决它们，直到有足够的上下文信息。

现在笛卡尔积开箱即用:

> hsequence ([1, 2] :> "ab" :> Nil)
[1 : 'a' : Nil,1 : 'b' : Nil,2 : 'a' : Nil,2 : 'b' : Nil]

我们也可以使用 hsequence与任何 Applicative :

> hsequence (Just "foo" :> Just () :> Just 10 :> Nil)
Just "foo" : () : 10 : Nil

编辑:我发现(感谢 dfeuer)现有的 hlist 提供了相同的功能。包裹:

import Data.HList.CommonMain

> hSequence ([3, 4] .*. "abc" .*. HNil)
[H[3, 'a'],H[3, 'b'],H[3, 'c'],H[4, 'a'],H[4, 'b'],H[4, 'c']]