haskell - Haskell 中的多变量函数

Question

阅读后this article on writing polyvariadic functions in Haskell ，我尝试写一些自己的。

起初我以为我应该尝试概括它 - 这样我就可以拥有一个通过折叠给定参数来返回可变参数函数的函数。

{-# OPTIONS -fglasgow-exts #-}
module Collapse where
class Collapse a r | r -> a where
  collapse :: (a -> a -> a) -> a -> r
instance Collapse a a where
  collapse _ = id
instance (Collapse a r) => Collapse a (a -> r) where
  collapse f a a' = collapse f (f a a')

但是，编译器不喜欢这样:

Collapse.hs:5:9:
    Functional dependencies conflict between instance declarations:
      instance Collapse a a -- Defined at Collapse.hs:5:9-20
      instance (Collapse a r) => Collapse a (a -> r)
        -- Defined at Collapse.hs:7:9-43

但是，如果我返回并为最终结果添加包装类型，它就会起作用:

module Collapse where
class Collapse a r | r -> a where
  collapse :: (a -> a -> a) -> a -> r
data C a = C a
instance Collapse a (C a) where
  collapse _ = C . id
instance (Collapse a r) => Collapse a (a -> r) where
  collapse f a a' = collapse f (f a a')
sum :: (Num a, Collapse a r) => a -> r
sum = collapse (+)

一旦我进行了此更改，它就可以正常编译，并且我可以使用 ghci 中的 collapse 函数。

ghci> let C s = Collapse.sum 1 2 3 in s
6

我不确定为什么最终结果需要包装类型。如果有人能解释这一点，我将非常感激。我可以看到编译器告诉我这是函数依赖性的一些问题，但我还没有真正理解fundeps的正确使用。

后来，我尝试采取不同的策略，并尝试为采用列表并返回值的函数定义一个可变参数函数生成器。我必须执行相同的容器技巧，并且还允许 UndecidableInstances。

{-# OPTIONS -fglasgow-exts #-}
{-# LANGUAGE UndecidableInstances #-}
module Variadic where
class Variadic a b r | r -> a, r -> b where
  variadic :: ([a] -> b) -> r
data V a = V a
instance Variadic a b (V b) where
  variadic f = V $ f []
instance (Variadic a b r) => Variadic a b (a -> r) where
  variadic f a = variadic (f . (a:))
list :: Variadic a [a] r => r
list = variadic . id
foldl :: (Variadic b a r) => (a -> b -> a) -> a -> r
foldl f a = variadic (Prelude.foldl f a)

如果不允许UndecidableInstances，编译器会提示我的实例声明非法:

Variadic.hs:7:0:
    Illegal instance declaration for `Variadic a b (V b)'
        (the Coverage Condition fails for one of the functional dependencies;
         Use -XUndecidableInstances to permit this)
    In the instance declaration for `Variadic a b (V b)'

Variadic.hs:9:0:
    Illegal instance declaration for `Variadic a b (a -> r)'
        (the Coverage Condition fails for one of the functional dependencies;
         Use -XUndecidableInstances to permit this)
    In the instance declaration for `Variadic a b (a -> r)'

但是，一旦编译完成，我就可以在 ghci 中成功使用它:

ghci> let V l = Variadic.list 1 2 3 in l
[1,2,3]
ghci> let vall p = Variadic.foldl (\b a -> b && (p a)) True
ghci> :t vall
vall :: (Variadic b Bool r) => (b -> Bool) -> r
ghci> let V b = vall (>0) 1 2 3 in b
True

我想我正在寻找的是解释为什么最终值的容器类型是必要的，以及为什么所有各种功能依赖项都是必要的。

另外，这看起来很奇怪:

ghci> let vsum = Variadic.foldl (+) 0

<interactive>:1:10:
    Ambiguous type variables `a', `r' in the constraint:
      `Variadic a a r'
        arising from a use of `Variadic.foldl' at <interactive>:1:10-29
    Probable fix: add a type signature that fixes these type variable(s)

<interactive>:1:10:
    Ambiguous type variable `a'in the constraint:
      `Num a' arising from the literal `0' at <interactive>:1:29
    Probable fix: add a type signature that fixes these type variable(s)
ghci> let vsum' = Variadic.foldl (+) 
ghci> :t vsum'
(Num a, Variadic a a r) => t -> a -> r
ghci> :t vsum' 0
(Num a, Variadic a a r) => a -> r
ghci> let V s = vsum' 0 1 2 3 in s
6

我猜这是允许 UndecidableInstances 的后果，但我不知道，我想更好地了解发生了什么。

Answer 1

函数依赖背后的想法是在像这样的声明中

class Collapse a r | r -> a where
  ...

r -> a 位表示 a 由 r 唯一确定。因此，您不能拥有 instance Collapse (a -> r) (a -> r) 和 instance Collapse a (a -> r)。请注意，实例 Collapse (a -> r) (a -> r) 源自完整图片的 实例 Collapse a a。

换句话说，您的代码正在尝试建立instance Collapse t t(类型变量的名称当然不重要)和instance Collapse a (a -> r) 。如果在第一个实例声明中将 (a -> r) 替换为 t，则会得到 instance Collapse (a -> r) (a -> r) 。现在这是您可以拥有的第二个类型参数等于(a -> r) 的唯一Collapse 实例，因为该类声明表示第一个类型参数可以从第二个类型参数推导。接下来，您尝试建立实例 a (a -> r)，这将添加另一个 Collapse 实例，第二个类型参数为 (a -> r )。因此，GHC 提示道。