5

当然，生成异构列表的笛卡尔积可以在 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，但它在去年没有更新，而且我不确定它是否是最合适的工具。

4

2 回答 2

5

看来HList确实有点腐烂了。尽管如此，没有什么能阻止我们自己动手HList！事实上，我们也可以严重依赖于singletons我们的类型级列表操作。首先，一些进口：

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

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

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

于 2017-02-24T16:18:29.317 回答
3

解决此问题的一种方法是为此使用模板 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将有 type 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))
于 2017-02-24T13:03:48.060 回答