重疊的實例扁平化元組

我試圖編寫代碼從元組鏈中刪除空元組。編譯器拒絕程序：重疊的實例扁平化元組

代碼：

{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE FunctionalDependencies #-} 
{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE OverlappingInstances #-} 
{-# LANGUAGE UndecidableInstances #-} 
{-# LANGUAGE TypeOperators #-} 

infixr 9 :* 
data a :* b = a :* !b 
    deriving (Show, Eq, Ord) 

class Flatten a b | a -> b where 
    flatten :: a -> b 

instance Flatten a a where 
    flatten = id 

instance Flatten a b => Flatten (() :* a) b where 
    flatten (() :* y) = flatten y 

instance Flatten b c => Flatten (a :* b) (a :* c) where 
    flatten (x :* y) = x :* flatten y 


test :: Int :*() 
test = flatten $ 0 :*()

[1 of 1] Compiling Main    (Test\Test.hs, interpreted) 

Test\Test.hs:26:8: 
    Overlapping instances for Flatten (Int :*()) (Int :*()) 
     arising from a use of `flatten' 
    Matching instances: 
     instance [overlap ok] Flatten a a 
     -- Defined at Test\Test.hs:15:10-20 
     instance [overlap ok] Flatten b c => Flatten (a :* b) (a :* c) 
     -- Defined at Test\Test.hs:21:10-49 
    In the expression: flatten 
    In the expression: flatten $ 0 :*() 
    In an equation for `test': test = flatten $ 0 :*() 
Failed, modules loaded: none.

目標：

flatten (0:*():*1:*2:3:*():*():*4:*()) == (0:*1:*2:*3:*4:*())

來源

2012-01-07 Thomas Eding

你爲什麼使用元組而不是列表？這似乎是一個非常困難的方式來做一些非常簡單的事情。 – amccausl 2012-01-07 02:57:43

適用於允許返回混合類型的函數的準標準函數。我想刪除'（）'。 – 2012-01-07 03:04:09

你能否澄清它不工作的方式，以及你期望它做什麼？像這樣重疊在使用多態類型時總會有些脆弱。 – 2012-01-07 03:04:11

好吧，首先：編譯埋怨fundeps衝突的原因是...因爲他們做衝突。實際上沒有辦法解決這個問題，因爲這種衝突是你想要做的。第一個類型參數是「輸入」，對於特定的類型，您基本上是對其進行模式匹配，並重疊給出默認的繼承案例。但第二個「輸出」類型參數需要根據「輸入」的不同而有所不同，具體方式和默認情況之間有所不同，因此存在衝突。

要解決這個問題，你需要使用一點弄虛作假利用選擇的實例時GHC只檢查例如，頭的事實，然後檢查背景後申請額外的約束。技巧的核心是完全不指定「輸出」類型，以便實例選擇僅檢查第一個參數，並認爲第二個參數對於所有實例都是相同的，而將某些東西滑入上下文中，將第二個參數與期望的「輸出「後的事實。

在當前GHC版本中使用此技術的最簡單方法是啓用類型族，以獲得~等式約束功能。這裏有一個例子：

instance (() ~ r) => Flatten (() :*()) r where 
    flatten _ =() 

instance (Flatten a r) => Flatten (() :* a) r where 
    flatten (_ :* rest) = flatten rest 

instance (a ~ r) => Flatten (a :*()) r where 
    flatten (x :* _) = x 

instance ((a :* c) ~ r, Flatten b c) => Flatten (a :* b) r where 
    flatten (x :* rest) = (x :* flatten rest) 

instance (a ~ r) => Flatten a r where 
    flatten x = x

爲了說明模式我已經使每個實例使用這個技巧，即使並非絕對必要。我們可以定義你想要的輸入：

test = (0 :*() :* 1 :* 2 :* 3 :*() :*() :*4 :*())

，然後在GHCI：

∀x. x ⊢ flatten test 
0 :* (1 :* (2 :* (3 :* 4)))

現在，你可能會奇怪，爲什麼我定義test外GHCI的。不幸的是，如果將上述實例應用於多態輸入類型，則仍然會失敗，並且從文件加載導致單態限制並鍵入默認值以將所有數字文字轉換爲Integer。儘管如此，對於這種模糊性實際上並沒有太多可以做的事情，因爲可能匹配多個輸入的類型參數確實是模糊的。

作爲一個歷史說明，你可以做同樣的伎倆沒有~，只用fundeps和GHC的奇怪怪癖。有些版本是大量荒謬類型的駭客所必需的，而原始的（不出所料）是由奧列格發明的，其名稱爲TypeCast，被用來實現等同謂詞TypeEq，它是HList之類的東西的基礎。

來源

2012-01-07 03:30:07

重疊的實例扁平化元組

回答

相關問題