异构列表的笛卡尔积

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价值观.最终我会将一个函数映射到这些函数上,这些函数将它们全部缩减为相同的类型(a Test)但是到目前为止,n*m我想要执行的测试用例有很多不同的类型(实际上并不是那么简单,因为某些函数只能受限制值的子集).

所以很自然地,将这些异构列表用于其他函数是很好的,例如某些类型map.

我已经看过HList,但它在去年还没有更新过,而且我不确定它是否是最合适的工具.

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不是我的简单测试的想法。但每一个他自己。:)

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))