Вычислить N-арное (с разными типами!!) декартово произведение в Haskell

Здесь можно использовать обычный разнородный список:

{-# 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']]

Этого можно добиться с помощью Template Haskell.

{-# LANGUAGE TemplateHaskell #-}
f :: ExpQ -> ExpQ
f ess = do es <- ess
           case es of
             (TupE e) -> return $ h e
             _ -> fail "f expects tuple of lists"
  where
    h ts = let ns = zipWith (\_ -> mkName . ('x':) . show) ts [0..]
           in CompE $ (zipWith (BindS . VarP) ns ts) ++
                      [NoBindS $ TupE $ map VarE ns]

Тогда, возможно, немного неудобно использовать, но это цена поддержки любых кортежей:

Prelude> take 7 $ $(f [| ([1..], [1..2], "ab") |] )
[(1,1,'a'),(1,1,'b'),(1,2,'a'),(1,2,'b'),(2,1,'a'),(2,1,'b'),(2,2,'a')]

Я сам нашел лучшее решение, это решение идеально подходит для пользователя, но его реализация довольно уродлива (должен создавать экземпляр каждого кортежа, как zip):

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}

class CartProd a b | a -> b where
    cartProd :: a -> b

instance CartProd ([a], [b]) [(a, b)] where
    cartProd (as, bs) = [(a, b) | a <- as, b <- bs]

instance CartProd ([a], [b], [c]) [(a, b, c)] where
    cartProd (as, bs, cs) = [(a, b, c) | a <- as, b <- bs, c <- cs]

c = cartProd (['a'..'c'], [0..2])
d = cartProd (['a'..'c'], [0..2], ['x'..'z'])

Мы также можем предоставить лучшую версию zip таким образом, чтобы мы могли использовать одно имя функции zip' вместо zip, zip3, zip4 ...:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}

class Zip a b | a -> b where
    zip' :: a -> b

instance Zip ([a], [b]) [(a, b)] where
    zip' (as, bs) = zip as bs

instance Zip ([a], [b], [c]) [(a, b, c)] where
    zip' (as, bs, cs) = zip3 as bs cs

a = zip' (['a'..'z'], [0..])
b = zip' (['a'..'z'], [0..], ['x'..'z'])