haskell - 如何为 OVERLAPPABLE 实例、单态容器和 newtype 包装器实现默认关联类型族？

Question

我有以下 Haskell 代码:

type family Element t

class ToList t where
    toList :: t -> [Element t]

之前有人建议我将 Element 设为关联的类型系列:Foldable IntSet

我尝试实现这种方法。但它不适用于我的情况。完整代码如下:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies #-}

import Prelude hiding (toList)
import qualified Data.Foldable as Foldable (toList)
import Data.Text (Text, unpack)

class ToList t where
    type Element t :: *
    toList :: t -> [Element t]

-- | This instance makes 'ToList' compatible and overlappable by 'Foldable'.
instance {-# OVERLAPPABLE #-} Foldable f => ToList (f a) where
    type Element (f a) = a
    toList = Foldable.toList

instance ToList Text where
    type Element Text = Char
    toList = unpack

newtype WrappedList l = WrappedList l

instance ToList l => ToList (WrappedList l) where
    type Element (WrappedList l) = Element l
    toList (WrappedList l) = toList l

当我使用 GHC-8.2.2 编译此代码时，我看到以下错误:

Element.hs:14:10: error:
    Conflicting family instance declarations:
      Element (f a) = a -- Defined at Element.hs:14:10
      Element (WrappedList l) = Element l -- Defined at Element.hs:24:10
   |
14 |     type Element (f a) = a
   |          ^^^^^^^^^^^^^^^^^

如何修复此错误？我不知道如何使其与相关类型系列兼容......

Answer 1

本质的问题是你不能使用类型类重叠来使类型族重叠。它根本没有意义 - 类型族从输入类型计算类型，并且结果类型可能不依赖于编译器如何选择类型类实例(否则它不会是一个函数 - 因为输出函数可能仅取决于输入)。这个问题很常见，但如何解决它完全取决于您的具体用例。

最简单的解决方案是使用 DefaultSignatures 提供默认实现。请注意，关联的类型系列也可以有默认值:

type family ElementDefault (t :: *) :: * where
  ElementDefault (f a) = a

class ToList t where
    type Element t :: *
    type Element t = ElementDefault t

    toList :: t -> [Element t]
    default toList :: (Foldable f, t ~ f a, Element t ~ a) => t -> [Element t]
    toList = Foldable.toList

这允许您为所有 Foldable 类型编写实例，而无需给出实现:

instance ToList [a]
instance ToList (Maybe a)
-- etc...

<小时/>

如果你想避免编写这样的实例(甚至是实例头)，你需要将关联的类型移到类实例头中。由于只有类可能重叠，而不是开放类型族，因此这样做允许“元素”类型也重叠。

class ToList t e | t -> e where
  toList :: t -> [e]

instance {-# OVERLAPPABLE #-} (a ~ a', Foldable f) => ToList (f a) a' where
  toList = Foldable.toList

instance ToList Text Char where
  toList = unpack

instance ToList l a => ToList (WrappedList l) a where
  toList (WrappedList l) = toList l

<小时/>

提供多个默认定义的最简单方法是在类外部提供它们。如果您有 15 个类函数，这确实会很乏味。在这种情况下，我会用记录来实现该类:

data ToList' t e = ToList'
  { toList' :: t -> [e] {- 14 more fields... -} }

class ToList t where
  type Element t 
  toList_impl :: ToList' t (Element t)

-- For consumers of ToList
toList :: ToList t => t -> [Element t]
toList = toList' toList_impl

instance ToList Text where
  type Element Text = Char
  toList_impl = ToList' unpack

toList_Foldable_default :: Foldable f => ToList' (f a) a
toList_Foldable_default = ToList' Foldable.toList

toList_Wrapped_list :: ToList l => ToList' l (Element l)
toList_Wrapped_list = ToList' toList

通过这种方法，您可以完全省去类型类；它唯一剩下的用途是获得实例的唯一性。