haskell - 重叠实例以展平元组

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)))

现在，您可能想知道为什么我在 GHCi 之外定义 test。不幸的是，如果应用于多态输入类型，上述实例仍然会失败，并且从文件加载它会导致单态限制和类型默认将所有数字文字转换为整数>。不过，对于这种歧义，我们确实无能为力，因为可以匹配多个输入的类型参数确实是不明确的。

<小时/>

作为历史记录，您可以在没有 ~ 的情况下完成相同的技巧，仅使用fundeps和GHC的奇怪怪癖。大量 absurd 的类型黑客技术需要某些版本，而原始版本是由 Oleg 发明的(不出所料)，其名称有点误导性 TypeCast，并用于实现相等谓词 TypeEq 是 HList 之类的基础。