15

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

进行此更改后，它编译得很好，我可以collapse在ghci.

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

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

4

3 回答 3

8

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

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

该r -> a位表示a由 唯一确定r。所以，你不能拥有instance Collapse (a -> r) (a -> r)and 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)得到. 现在这是唯一一个第二个类型参数等于你可以拥有的实例，因为类声明说第一个类型参数可以从第二个类型参数推导出来。然而接下来你尝试建立，这将添加另一个实例，第二个类型参数是。因此，GHC 抱怨。tinstance Collapse (a -> r) (a -> r)Collapse(a -> r)instance a (a -> r)Collapse(a -> r)

于 2010-01-28T17:49:48.053 回答
5

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

{-# 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"

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

于 2010-01-31T07:32:37.233 回答
4

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

就 UndecidableInstances 而言，这里描述了覆盖条件；您的实例失败的原因应该很明显。请注意，这里的“undecidable”一词的含义与“Halting Problem is undecidable”的含义大致相同——也就是说，您告诉 GHC 鲁莽地尝试解决可能将其发送到无限循环的代码仅基于您认为没关系的断言。破解巧妙的想法很有趣，但同意成为 GHC 的人类首过类型检查员是我个人觉得厌倦的负担。

于 2010-01-28T18:23:42.903 回答