类型级递归和 PolyKinds

Question

我正在尝试实现一个多态函数，它基本上遍历一个类型，累积一个 Tag 值。我希望用户能够做，例如rec ((1,2), ('a', 3)).

{-# LANGUAGE KindSignatures, PolyKinds, FlexibleInstances #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}
import Data.Proxy

newtype Tag (a :: k) = Tag Int
    deriving (Eq, Read, Show)

-- My users only have to define their own instances of this class...
class Tagged (a :: k) where
  tag :: Tag a

-- ...like these:
instance Tagged Int where
  tag = Tag 1

instance Tagged Char where
  tag = Tag 2

instance Tagged (,) where
  tag = Tag 3


-- While this is a morally "closed" class; implementing recursion over
-- components of types. This is what I'm struggling with:
class Rec (a :: k) where
  rec :: proxy a -> Tag a

instance (Rec ab, Rec c)=> Rec (ab c) where
  rec _ = let Tag ab = rec Proxy :: Tag ab
              Tag c = rec Proxy :: Tag c
           in Tag (ab * c)

instance {-# OVERLAPPABLE #-} Tagged a=> Rec a where
  rec _ = tag :: Tag a

我以各种方式解决了这个问题，在当前版本中得到了错误（对于 ab 和 c，在第一个实例中）：

    • Could not deduce (Tagged ab) arising from a use of ‘rec’
      from the context: (Rec ab, Rec c)
        bound by the instance declaration at flook.hs:26:10-37
    • In the expression: rec Proxy :: Tag ab
      In a pattern binding: Tag ab = rec Proxy :: Tag ab
      In the expression:
        let
          Tag ab = rec Proxy :: Tag ab
          Tag c = rec Proxy :: Tag c
        in Tag (ab * c)
   |
27 |   rec _ = let Tag ab = rec Proxy :: Tag ab
   |                        ^^^^^^^^^

我对这个错误感到有点惊讶，因为它似乎表明第二个基本案例实例是在第一个实例的主体中先验选择的。

有没有办法让这个工作，或者更好的方法？

Answer 1

我认为你应该跳过两个类。一个就够了。

缺点是您的用户将无法在您的设计中编写对应于 instance Tagged (Maybe Int) 的实例，这些实例为复合类型做一些特殊的事情......但他们已经无法真正使用这些，因为Rec 的应用程序实例无论如何都会与它重叠。

所以，事不宜迟：

{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE UndecidableInstances #-}

import Data.Tagged

class Rec a where rec :: Tagged a Int

-- it is still possible for users to define their own instances for base types
instance Rec Int  where rec = 1
instance Rec Char where rec = 2
instance Rec (,)  where rec = 3

instance (Rec ab, Rec c) => Rec (ab c) where
  rec = retag (rec :: Tagged ab Int) * retag (rec :: Tagged c Int)

在 ghci 中：

> rec :: Tagged ((Int, Int), Char) Int
Tagged 18

类型级递归和 PolyKinds

Type-level recursion and PolyKinds

haskell

type-level-computation

polykinds