重叠实例以展平元组

Question

我正在尝试编写代码以从元组链中删除空元组.编译器拒绝该程序:

码:

{-# 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:*())

Answer 1

好的,首先:编译器抱怨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怪癖.对于大量荒谬类型的hackery来说,某些版本是必需的,并且原始(不出所料)由Oleg发明,使用稍微误导性的名称TypeCast,并且用于实现TypeEq等级谓词,这是HList之类的东西的基础.