Haskell 中的多变量函数

Question

阅读这篇关于在 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 (+)

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

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

Michał Marczyk 关于fundeps 和实例匹配问题的说法绝对正确，并且包装器类型似乎是一个简单的解决方案。另一方面，如果您已经在阅读 Oleg 的网站，您可能更愿意访问 深入研究兔子洞并尝试为“任何不是函数的类型”编写一个实例。

就 UndecidableInstances 而言，描述了覆盖条件 此处；您的实例失败的原因应该很明显。请注意，这里的“不可判定”一词与“停止问题是不可判定的”含义大致相同，也就是说，您告诉 GHC 不计后果地尝试解析可能会使其进入无限循环的代码仅基于您的断言“没问题”。破解巧妙的想法很有趣，但同意成为 GHC 的人类首次类型检查员是我个人认为令人厌倦的负担。

Answer 2

函数依赖背后的想法是，在像

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

r -> 这样的声明中a 位表示 a 由 r 唯一确定。因此，您不能拥有instance Collapse (a -> r) (a -> r) 和instance Collapse a (a -> r)。请注意，instance Collapse (a -> r) (a -> r) 源自完整图片的 instance 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) ; r）。因此，GHC 抱怨道。

Answer 3

如果您仍在尝试这一点，这里有一个从采用列表的函数构造多变量函数的示例，而不需要包装器类型或不可判定的实例：

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}

class Variadic a b r | r -> a where
    variadic :: ([a] -> b) -> r

instance Variadic a b (a -> b) where
    variadic f x = f [x]

instance (Variadic a b (a -> r)) => Variadic a b (a -> a -> r) where
    variadic f x y = variadic (f . (x:)) y

vList :: (Variadic a [a] r) => r
vList = variadic id

vFoldl :: (Variadic b a r) => (a -> b -> a) -> a -> r
vFoldl f z = variadic (foldl f z)

vConcat :: (Variadic [a] [a] r) => r
vConcat = vFoldl (++) []

main = do
    putStrLn $ vConcat "abc" "def" "ghi" "jkl"
    putStrLn $ vList 'x' 'y' 'z'
    if vFoldl (&&) True True True True then putStrLn "Yes" else putStrLn "No"
    if vFoldl (&&) True True False True then putStrLn "Yes" else putStrLn "No"

这种方法的缺点是类型检查器必须能够推断出结果的类型（或者你必须对其进行注释），并且它在多态数字常量上严重失败；您提到的文章中讨论了这两个问题的原因。不知道您是否会发现这有帮助，但我之前正在修改多变量函数并记住了这个问题。