异构列表的笛卡尔积

Question

当然，在Haskell中，可以通过多种方式生成异构列表的笛卡尔积，例如：

[(x,y) | x <- [1,2,3], y <- [4,5,6]]

或者

(,) <$> [1,2,3] <*> [4,5,6]

但是我想要的是这样一个函数：

heteroCartesian :: 
  (a1, a2, ... , an) -> 
  (b1, b2, ... , bn) -> 
  ((a1,b1), (a1,b2), ... , (a1,bn), (a2,b1), (a2,b2), ... , (a2,bn), (an,b1), ... ,(an,b2), ... , (an,bn))

这样我可以做到这样：

f (1,'a',True) (2,'b') == 
((1,2),(1,'b'),('a',2),('a','b'),(True,2),(True,'b'))

我不介意使用元组或其他东西，但我需要保留上面所述的类型信息。

我之所以想要这样做是为了创建测试用例。我有一堆函数和值，例如 n 个函数和 m 个值。最终，我将在这些上映射一个函数，将它们全部归约为相同的类型（一个 Test），但在此之前，对于我想执行的 n*m 个测试用例，有许多不同类型的值（实际上并不简单，因为某些函数只能取受限制的子集）。

因此，自然而然地，我希望有其他函数可以处理这些异构列表，例如某种 map。

我已经看过 HList，但它在过去一年多没有更新，而且我也不确定它是否是最合适的工具。

- Clinton

Answer 1

看起来HList确实有点老化了。尽管如此，我们仍然可以自己开发HList！事实上，我们还可以大量依赖singletons进行类型级别的列表操作。首先，导入一些内容：

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

import Data.Singletons
import Data.Promotion.Prelude.List

那么，HList的实际定义（比该名称的软件包使用的定义更简单，原因在这里和这里进行了描述）。

data HList (l :: [*]) where
  HNil :: HList '[]
  HCons :: x -> HList xs -> HList (x ': xs)

-- Notice we are using `:++` from singletons
append :: HList xs -> HList ys -> HList (xs :++ ys)
append HNil xs = xs
append (x `HCons` xs) ys = x `HCons` (xs `append` ys)

-- Notice we are using `Map` and `TyCon1` from singletons. Bow before the magic
-- of type level HOFs. ;)
addTuple :: z -> HList xs -> HList (Map (TyCon1 ((,) z)) xs)
addTuple _ HNil = HNil
addTuple x (y `HCons` ys) = (x,y) `HCons` addTuple x ys

-- These instances aren't needed, but they let us check the output of our code
instance (Show x, Show (HList xs)) => Show (HList (x ': xs)) where
  show (x `HCons` xs) = show x ++ " " ++ show xs
instance Show (HList '[]) where
  show HNil = ""

最后，我们来到了笛卡尔积本身：

type family Cartesian (ys :: [*]) (xs :: [*]) :: [*] where
  Cartesian '[] xs = '[]
  Cartesian (y ': ys) xs = Map (TyCon1 ((,) y)) xs :++ Cartesian ys xs

cartesian :: HList xs -> HList ys -> HList (xs `Cartesian` ys)
cartesian HNil _ = HNil
cartesian (y `HCons` ys) xs = addTuple y xs `append` cartesian ys xs

我们可以测试是否可用：

ghci> h1 = HCons True $ HCons LT $ HCons () $ HCons (1 :: Int) HNil
ghci> h2 = HCons () $ HCons "hello" $ HCons 'a' HNil
ghci> h1 `cartesian` h2
(True,()) (True,"hello") (True,'a') (LT,()) (LT,"hello") (LT,'a') ((),()) ((),"hello") ((),'a') (1,()) (1,"hello") (1,'a')

---

尽管如此，我不确定这对于测试来说真的值得。从根本上讲，我期望测试比我正在测试的代码更简单和更易读。而 HList 不是我所期望的简单测试方式。但是，每个人都有自己的想法。 :)

- Alec

Answer 2

一种解决方法是使用模板Haskell来实现：

import Control.Monad(replicateM)
import Language.Haskell.TH.Syntax(newName,Pat(TupP,VarP),Exp(LamE,TupE,VarE))

heteroCartesian m n = do
    as <- replicateM m $ newName "a"
    bs <- replicateM n $ newName "b"
    return $ LamE [TupP (map VarP as),TupP (map VarP bs)] $ TupE $ [TupE [VarE ai,VarE bi] | ai <- as, bi <- bs]

现在在另一个文件中，你可以使用这个函数：

{-# LANGUAGE TemplateHaskell #-}

heteroCartesian23 = $(heteroCartesian 2 3)

在这种情况下，heteroCartesian23 的类型将为 heteroCartesian23 :: (a1,a2) -> (b1,b2,b3) -> ((a1,b1),(a1,b2),(a1,b3),(a2,b1),(a2,b2),(a2,b3))。

或者你可以在 ghci 中使用它：

$ ghci -XTemplateHaskell library.hs
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( ha.hs, interpreted )
Ok, modules loaded: Main.
*Main> :t $(heteroCartesian 3 4)
$(heteroCartesian 3 4)
  :: (t, t1, t5)
     -> (t2, t3, t4, t6)
     -> ((t, t2),
         (t, t3),
         (t, t4),
         (t, t6),
         (t1, t2),
         (t1, t3),
         (t1, t4),
         (t1, t6),
         (t5, t2),
         (t5, t3),
         (t5, t4),
         (t5, t6))

- Willem Van Onsem

---

请注意，这很快就会到达底部 - GHC的元组仅限于62个元素（如果我数得正确的话）。 - Alec

@Alec：是的，我只想提供一个使用内置的Haskell类型的解决方案。 - Willem Van Onsem