4

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

代码：

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

1 回答 1

10

好的，首先：编译器抱怨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会失败，并且从文件加载它会导致单态限制和类型默认将所有数字文字转换为. 但是，对于这种歧义，实际上没有什么可以做的，因为可以匹配多个输入的类型参数确实是模棱两可的。

作为历史记录，您可以在没有 的情况下执行相同的技巧~，仅使用 GHC 的fundeps 和奇怪的怪癖。大量可笑类型的黑客需要其中的某个版本，而原始版本（不出所料）是由 Oleg 发明的，名称稍有误导性TypeCast，用于实现作为TypeEqHList 之类的基础的相等谓词。

于 2012-01-07T03:30:07.527 回答