3

我正在开发一个库，我想在其中定义一个递归类，在这里我将其简化为：

{-# LANGUAGE MultiParamTypeClasses 
           , FlexibleInstances #-}

data Snoc st b c = Snoc (st b) (c -> b) 
data Top a = Top

class StackTo a st c  where
     runStack :: st c -> (c -> a)
instance StackTo a Top a where
     runStack _ = id
instance (StackTo a st b) => StackTo a (Snoc st b) c where
     runStack (Snoc st' cb) = runStack st' . cb

这让我做，例如

*Main Data.Label> let f = runStack $ Snoc (Snoc Top fst) head :: [(a,x)] -> a
*Main Data.Label> f [('a',undefined)] 
'a'

但这似乎需要仔细使用类型注释，否则......

*Main Data.Label> let f = runStack $ Snoc (Snoc Top fst) head

<interactive>:1:1:
    No instance for (StackTo a0 Top b0)
      arising from a use of `runStack'
    Possible fix: add an instance declaration for (StackTo a0 Top b0)
    In the expression: runStack
    In the expression: runStack $ Snoc (Snoc Top fst) head
    In an equation for `it': it = runStack $ Snoc (Snoc Top fst) head

我认为这些问题与此问题中解决的问题相同，但我无法在这里调整该解决方案。我可以使用类型族或其他方法来为我的递归延续堆栈提供更用户友好的解决方案吗？

4

2 回答 2

7

链接问题的答案隐藏了以下非常有用的技巧：概括实例头部，并专门研究实例上下文。

instance a ~ b => StackTo a Top b where
    runStack _ = id

在选择要使用的实例时，GHC 只检查可用的实例头——而不是上下文——并选择与当前已知的类型相匹配的一个（如果有的话）。在做出这个选择之前它不会专门化一个类型，即使专门化会允许一个或多个可用的实例头匹配。因此，此处给出的实例与上述问题中的实例之间的区别在于，这个实例更通用：当中间类型为 时，此实例适用Top，而您的实例仅在中间类型为时适用，Top 并且我们对其他两种类型了解足够多类型知道他们是平等的。

您的实例将与更少的其他潜在实例重叠，但这将更强烈地鼓励推理引擎。

于 2012-05-27T21:58:28.813 回答
6

Kleene 明星GADT 不会做这项工作有什么特别的原因吗？

data Star r a b where
  Nil   :: Star r a a
  Cons  :: r a b -> Star r b c -> Star r a c

compose :: Star (->) a b -> a -> b
compose Nil          = id
compose (Cons f fs)  = compose fs . f

但是，如果您需要类型类方法，我不会干涉。

于 2012-05-27T22:05:55.970 回答