是否可以重新組織嵌套元組？

Question

我想要做的是這樣的：

拿任意多態元組：

x = (((1, ""), Nothing), ('', 6)) 

並且用類似這種類型的重組（不一定以相同的順序，但相同的結構：

(Int, (Char, (Maybe Int, (String, (Int,())))) 

我真的不爲這種模式，所以我無法使用谷歌盡我最大的能力，知道這個名字。

Answer 1

如果你只需要對付這種特殊情況下，即從

轉換

(((Int, String), Maybe Int), (Char, Int)) 

到

(Int, (Char, (Maybe Int, (String, (Int,())))) 

然後根據您是否希望保留的0階個-components或交換它們，你可以簡單地使用這兩個功能之一：

from1 (((m, s), mb), (c, n)) = (m, (c, mb, (s, (n,())))) 
from2 (((m, s), mb), (c, n)) = (n, (c, mb, (s, (m,())))) 

---

當然，我們還可以稍微多一些雄心勃勃，瞄準一個更通用的解決方案;例如參見Jeuring and Atanassow (MPC 2004)。爲此，讓我們啓用一些語言擴展

{-# LANGUAGE GADTs    #-} 
{-# LANGUAGE TypeFamilies   #-} 
{-# LANGUAGE TypeOperators  #-} 
{-# LANGUAGE UndecidableInstances #-} 

並引入GADT的，我們可以用它來代表元組類型

infixr 5 :*: 

data U a where 
    Unit :: U() 
    Int :: U Int 
    Char :: U Char 
    List :: U a -> U [a] 
    Maybe :: U a -> U (Maybe a) 
    (:*:) :: U a -> U b -> U (a, b) 

例如代碼，請從例如目標類型，現在可以由表達式編碼

Int :*: Char :*: Maybe Int :*: string :*: Int :*: Unit 

類型的

U (Int, (Char, (Maybe Int, (String, (Int,())))) 

爲方便起見，我們引入

string :: U String 
string = List Char 

我們還推出一種顯式類型的元組的值

data Typed where 
    Typed :: U a -> a -> Typed 

和類型層次平等的概念：

infix 4 :==: 

data a :==: b where 
    Refl :: a :==: a 

隨着我們可以定義一個元組類型編碼的異構平等檢查：

eq :: U a -> U b -> Maybe (a :==: b) 
eq Unit Unit     = Just Refl 
eq Int Int      = Just Refl 
eq Char Char     = Just Refl 
eq (List u1) (List u2)   = case eq u1 u2 of 
            Just Refl -> Just Refl 
            _   -> Nothing 
eq (Maybe u1) (Maybe u2)  = case eq u1 u2 of 
            Just Refl -> Just Refl 
            _   -> Nothing 
eq (u11 :*: u12) (u21 :*: u22) = case (eq u11 u21, eq u12 u22) of 
            (Just Refl, Just Refl) -> Just Refl 
            _      -> Nothing 
eq _ _       = Nothing 

即eq u1 u2返回Just Refl如果u1和u2編碼相同元組類型，並Nothing否則。在構造函數Just中，構造函數Refl充當類型檢查器的證據，即元組類型確實是相同的。

現在我們希望能夠將元組類型轉換爲「扁平化」，即右嵌套表示。對於這一點，我們引入一個類型家族Flatten：

type family Flatten a 

type instance Flatten()   =() 
type instance Flatten Int   = Flatten (Int,()) 
type instance Flatten Char   = Flatten (Char,()) 
type instance Flatten [a]   = Flatten ([a],()) 
type instance Flatten (Maybe a) = Flatten (Maybe a,()) 
type instance Flatten ((), a)  = Flatten a 
type instance Flatten (Int, a)  = (Int, Flatten a) 
type instance Flatten (Char, a) = (Char, Flatten a) 
type instance Flatten ([a], b)  = ([a], Flatten b) 
type instance Flatten (Maybe a, b) = (Maybe a, Flatten b) 
type instance Flatten ((a, b), c) = Flatten (a, (b, c)) 

和兩個功能flattenV和flattenU分別用於平坦化元組值和它們的類型的編碼：

flattenV :: U a -> a -> Flatten a 
flattenV Unit _     =() 
flattenV Int n     = flattenV (Int :*: Unit) (n,()) 
flattenV Char c     = flattenV (Char :*: Unit) (c,()) 
flattenV (List u) xs    = flattenV (List u :*: Unit) (xs,()) 
flattenV (Maybe u) mb   = flattenV (Maybe u :*: Unit) (mb,()) 
flattenV (Unit :*: u) (_, x)  = flattenV u x 
flattenV (Int :*: u) (n, x)  = (n, flattenV u x) 
flattenV (Char :*: u) (c, x)  = (c, flattenV u x) 
flattenV (List _ :*: u) (xs, x) = (xs, flattenV u x) 
flattenV (Maybe _ :*: u) (mb, x) = (mb, flattenV u x) 
flattenV ((u1 :*: u2) :*: u3) ((x1, x2), x3) 
           = flattenV (u1 :*: u2 :*: u3) (x1, (x2, x3)) 

flattenU :: U a -> U (Flatten a) 
flattenU Unit     = Unit 
flattenU Int     = Int :*: Unit 
flattenU Char     = Char :*: Unit 
flattenU (List u)    = List u :*: Unit 
flattenU (Maybe u)   = Maybe u :*: Unit 
flattenU (Unit :*: u)   = flattenU u 
flattenU (Int :*: u)   = Int :*: flattenU u 
flattenU (Char :*: u)   = Char :*: flattenU u 
flattenU (List u1 :*: u2)  = List u1 :*: flattenU u2 
flattenU (Maybe u1 :*: u2) = Maybe u1 :*: flattenU u2 
flattenU ((u1 :*: u2) :*: u3) = flattenU (u1 :*: u2 :*: u3) 

兩個，然後組合成單一功能flatten：

flatten :: U a -> a -> Typed 
flatten u x = Typed (flattenU u) (flattenV u x) 

我們還需要一種方法來恢復或從扁平表示元組的組分的iginal嵌套：

reify :: U a -> Flatten a -> a 
reify Unit _     =() 
reify Int (n, _)    = n 
reify Char (c, _)    = c 
reify (List u) (xs, _)  = xs 
reify (Maybe u) (mb, _)  = mb 
reify (Unit :*: u) y   = ((), reify u y) 
reify (Int :*: u) (n, y)  = (n, reify u y) 
reify (Char :*: u) (c, y)  = (c, reify u y) 
reify (List _ :*: u) (xs, y) = (xs, reify u y) 
reify (Maybe _ :*: u) (mb, y) = (mb, reify u y) 
reify ((u1 :*: u2) :*: u3) y = let (x1, (x2, x3)) = reify (u1 :*: u2 :*: u3) y 
           in ((x1, x2), x3) 

現在，給定類型代碼u爲元組分量和與它的類型的編碼的扁平元組一起，我們定義函數select返回所有可能的方式從元組中選擇與類型匹配u和剩餘組分的展平表示的成分：

select :: U b -> Typed -> [(b, Typed)] 
select _ (Typed Unit _)     = [] 
select u2 (Typed (u11 :*: u12) (x1, x2)) = 
    case u11 `eq` u2 of 
    Just Refl -> (x1, Typed u12 x2) : zs 
    _   -> zs 
    where 
    zs = [(y, Typed (u11 :*: u') (x1, x')) | 
      (y, Typed u' x') <- select u2 (Typed u12 x2)] 

最後，我們可以再定義一個函數conv帶有兩個元組類型碼及一個元組與第一個c相匹配的類型賦，並返回所有可能的轉換成類型的元組，所述第二代碼匹配：

conv :: U a -> U b -> a -> [b] 
conv u1 u2 x = [reify u2 y | y <- go (flattenU u2) (flatten u1 x)] 
    where 
    go :: U b -> Typed -> [b] 
    go Unit (Typed Unit _) = [()] 
    go (u1 :*: u2) t  = 
     [(y1, y2) | (y1, t') <- select u1 t, y2 <- go u2 t'] 

作爲一個例子，我們有

conv (Int :*: Char) (Char :*: Int) (2, 'x') 

產量

[('x', 2)] 

返回到您的原始示例，如果我們定義

from = conv u1 u2 
    where 
    u1 = ((Int :*: string) :*: Maybe Int) :*: Char :*: Int 
    u2 = Int :*: Char :*: Maybe Int :*: string :*: Int :*: Unit 

然後

from (((1, ""), Nothing), (' ', 6)) 

產生

[ (1, (' ', (Nothing, ("", (6,()))))) 
, (6, (' ', (Nothing, ("", (1,()))))) 
] 

我們可以讓事情變得更好一點，通過引入表示的元組類型的一個類型類：

class Rep a where 
    rep :: U a 

instance Rep() where rep = Unit 
instance Rep Int where rep = Int 
instance Rep Char where rep = Char 
instance Rep a => Rep [a] where rep = List rep 
instance Rep a => Rep (Maybe a) where rep = Maybe rep 
instance (Rep a, Rep b) => Rep (a, b) where rep = rep :*: rep 

這樣的話，我們可以定義一個不需要元組類型代碼的轉換函數：

conv' :: (Rep a, Rep b) => a -> [b] 
conv' = conv rep rep 

然後，例如

conv' ("foo", 'x') :: [((Char,()), String)] 

產生

[(('x',()), "foo")] 

Answer 2

我仍然是最近Haskell，但我會做這與模式匹配功能。

converter :: (((Int, String), Maybe a), (Char, Int)) -> (Int, (Char, Maybe Int, (String, (Int,())))) 
converter (((i1, s), m), (c, i2)) = (i1, (c, (m, (s, (i2,()))))) 

你當然可以用類型變量替換所有的具體類型，它也可以工作。

converter :: (((a, b), c), (d, e)) -> (a, (d, c, (b, (e,())))) 
converter (((i1, s), m), (c, i2)) = (i1, (c, (m, (s, (i2,()))))) 

（顯然，你會想要得到的類型以正確的順序，並確保這一切編譯）