Haskell类型让一个简单的“平均值”函数感到沮丧

Question

Haskell类型让一个简单的“平均值”函数感到沮丧

haskelltypestypeclass

84

我正在尝试学习Haskell编程语言，并想写一个求平均数的函数。开始看起来这是世界上最简单的事情，对吧？

不对。

似乎Haskell的类型系统禁止平均数函数对于通用的数字类型进行操作 - 我可以让它对整数列表或分数列表进行处理，但不能同时处理两者。

我需要：

average :: (Num a, Fractional b) => [a] -> b
average xs = ...

但我只能得到：

averageInt :: (Integral a, Fractional b) => [a] -> b
averageInt xs = fromIntegral (sum xs) / fromIntegral (length xs)

或者

averageFrac :: (Fractional a) => [a] -> a
averageFrac xs = sum xs / fromIntegral (length xs)

第二个似乎是可行的。直到我尝试传递变量。

*Main> averageFrac [1,2,3]
2.0
*Main> let x = [1,2,3]
*Main> :t x
x :: [Integer]
*Main> averageFrac x

<interactive>:1:0:
    No instance for (Fractional Integer)
      arising from a use of `averageFrac ' at <interactive>:1:0-8
    Possible fix: add an instance declaration for (Fractional Integer)
    In the expression: average x
    In the definition of `it': it = averageFrac x

显然，Haskell对其类型非常挑剔。这很有道理。但是当它们都可以是[Num]时就不是这样了。

我是否错过了RealFrac的明显应用？

是否有一种方法可以将整数强制转换为分数，而不会在输入分数时出现错误？

是否有办法使用Either和either创建某种多态平均函数，以适用于任何类型的数字数组？

Haskell的类型系统是否完全禁止此函数存在？

学习Haskell就像学习微积分一样。它非常复杂，基于大量理论，有时问题非常复杂，以至于我甚至不知道如何正确地表达问题，因此任何见解都将受到热烈欢迎。

（另外，脚注：这是基于一个作业问题。每个人都同意averageFrac可以得到满分，但我有一种隐隐约约的感觉，有一种方法可以使它同时适用于Integral和Fractional数组）

- jakebman

https://dev59.com/k0rSa4cB1Zd3GeqPXZCg - Josh Lee

6个回答

27

问题已经由Dons很好地回答了，我想我可以补充一些内容。

当使用以下方式计算平均值时：

```average xs = realToFrac (sum xs) / genericLength xs```

你的代码将会遍历该列表两次，一次用于计算其元素的总和，另一次用于获取其长度。据我所知，GHC目前还无法优化此操作并在单次遍历中同时计算总和和长度。

即使作为初学者，思考这个问题和可能的解决方案也是有益的，例如可以使用一个fold来计算总和和长度的平均函数。在ghci中：

:set -XBangPatterns

import Data.List

let avg l=let (t,n) = foldl' (\(!b,!c) a -> (a+b,c+1)) (0,0) l in realToFrac(t)/realToFrac(n)

avg ([1,2,3,4]::[Int])
2.5
avg ([1,2,3,4]::[Double])
2.5

虽然这个函数不太优美，但性能更好。

更多信息请参考唐的博客：

http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/

- David V.

4

建议折叠以获得更好的性能提升是个好主意，但我只建议当你完全理解 Haskell 并且整数的多态对你来说非常简单时再尝试性能优化。+1 - Robert Massaioli

12

+1 推荐 Robert Massaioli 的评论，因为这个平均值实际上非常糟糕。在 Haskell 中，foldl' 在累加器上是严格的，这意味着它对于第一个数据构造函数来说是“弱头正常形式”，基本上是严格的。例如，在这里，foldl' 将保证累加器被评估足够以确定它是对（第一个数据构造函数），但其内容不会被评估，因此会积累thunk。在这种情况下，使用 foldl' (\(!b,!c) a -> ... 或者一个严格的对类型 data P a = P !a !a 是关键以获得良好的性能。 - Jedai

+1 给Jedai的评论，我已经相应地编辑了帖子。 - David V.

9

由于dons已经很好地回答了你的问题，所以我将对你的问题提出疑问......

例如，在你的问题中，你首先在给定列表上运行平均值，得到一个很好的答案。然后，你把看起来完全相同的列表赋值给一个变量，然后使用变量的函数......结果就失败了。

你遇到的问题是编译器中的设置，称为DMR：D读入M单态限制。当你直接将列表传递给函数时，编译器不会对数字的类型做出任何假设，它只会根据使用情况推断可能的类型，然后在无法缩小范围时选择一个类型。这有点像鸭子类型的直接反面。

无论如何，当你将列表分配给一个变量时，DMR就开始工作了。由于你将列表放在一个变量中，但没有提供如何使用它的提示，因此DMR选择了一个类型，本例中选择了与形式匹配且似乎合适的一个: 整数。由于你的函数不能在除法操作中使用整数（它需要Fractional类中的一种类型），因此它会产生非常明显的投诉：Fractional类中没有Integer的实例。在GHC中有一些选项可以设置，使其在需要之前不强制将您的值转换为单个形式（“单态”，懂吗？），但这使得任何错误消息都更难弄清楚一些。

现在，另一个注意点是你对dons的回答做出了回复，引起了我的注意:

我被cs.ut.ee/~varmo/MFP2004/PreludeTour.pdf最后一页上的图表误导了，它显示Floating不继承Real的属性，因此我认为它们没有共同的类型。

Haskell与您所习惯的方式不同。Real和Floating是类型类，它们更像是接口而不是对象类。它们告诉你可以对在该类中的类型做什么，但这并不意味着某些类型不能做其他事情，就像拥有一个接口并不意味着（面向对象式）类不能拥有其他接口一样。

学习Haskell就像学习微积分一样。

我认为学习Haskell就像学习瑞典语一样 - 有很多小的、简单的东西（字母、数字）看起来并且工作方式相同，但也有一些单词看起来应该意味着某个东西，实际上却意味着另一个东西。但是一旦你精通它，你的普通朋友会惊叹于你能够说出这些奇怪的东西，并让美丽的人做出惊人的技巧。有趣的是，从一开始就参与Haskell的许多人也懂得瑞典语。也许这个比喻不仅仅是比喻...

- BMeph

2

:m Data.List
let list = [1..10]
let average = div (sum list) (genericLength list)
average

- had same problem

1

经过这么多年，令人惊讶的是，没有人指出Don Stewart的average函数不能处理复数，而OP的averageFrac函数可以处理复数。两者并非绝对优劣。

无法编写的根本原因在于：

average :: (Num a, Fractional b) => [a] -> b

它可以像类型一样实例化

average :: [Complex Double] -> Double

Haskell的数值类支持一些略带损失的转换，例如从Rational到Double、从Double到Float和从Integer到Int，但不支持极度有损失的转换，例如复数到实数或分数到整数。你不能将Complex Double转换为Double而不显式地取其实部分，这不是average应该做的事情。因此，你不能编写average :: [Complex Double] -> Double。因此，你不能使用任何可以专门化为[Complex Double] -> Double的类型来编写average。

对于average来说，最Haskellish的类型可能是OP的averageFrac。一般来说，不专门用于类型转换的函数应该尽可能地将类型转换留给调用者。averageFrac将直接或在输入列表的强制转换后与几乎任何数字类型配合使用。由于调用者更接近数据源，因此更有可能知道是否需要强制转换（如果它不知道，则可以将决策留给其调用者）。相比之下，Don Stewart的average甚至不支持复数，即使进行强制转换也不行。你要么必须从头开始重写它，要么就要对列表的实部和虚部投影分别调用它两次（然后再编写另一个包装器，对四元数调用它四次等等）。

- benrg

-5

是的，Haskell 的类型系统非常挑剔。问题在于 fromIntegral 的类型：

Prelude> :t fromIntegral
fromIntegral :: (Integral a, Num b) => a -> b

fromIntegral 只接受整数类型作为参数a，而不是其他Num类型。而(/)则只接受分数类型。那么如何让这两个函数协同工作呢？

嗯，sum函数是个不错的起点：

Prelude> :t sum
sum :: (Num a) => [a] -> a

Sum接受任何Num列表并返回Num。

你接下来要解决的问题是列表的长度。长度是一个Int：

Prelude> :t length
length :: [a] -> Int

你需要将那个 Int 转换成 Num。这就是 fromIntegral 的作用。

现在你有一个返回 Num 的函数和另一个返回 Num 的函数。有一些关于数字类型提升的规则可以查阅，但基本上在这一点上你已经准备好了：

Prelude> let average xs = (sum xs) / (fromIntegral (length xs))
Prelude> :t average
average :: (Fractional a) => [a] -> a

让我们试一下：

Prelude> average [1,2,3,4,5]
3.0
Prelude> average [1.2,3.4,5.6,7.8,9.0]
5.4
Prelude> average [1.2,3,4.5,6,7.8,9]
5.25

- JUST MY correct OPINION

11

你也掉入了迈克尔同样的陷阱——数字重载！5不是一个整数值。它是任何数字类型。在这里，它默认为分数值——你无法传递Int或Integer——因为你会得到"No instance for (Fractional Int)"的错误提示。 - Don Stewart

是的，那是我的错。我没有足够仔细地注意到。我想这正是为什么我从未在Haskell中进行过更多的编程工作的原因。即使作为一个受虐待语言的粉丝，我也觉得Haskell有点残酷。 - JUST MY correct OPINION

2

Haskell 不是 B&D。以 B&D 的方式接近它会很痛苦。如果你想学习 Haskell，你需要掌握类型系统。就是这样。当你学会如何为自己使用类型时，你的困惑将会消失。 - nomen

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Don Stewart · Accepted Answer

基本上，你的限制取决于 / 的类型：

(/) :: (Fractional a) => a -> a -> a

顺便提一下，您也需要使用Data.List.genericLength

genericLength :: (Num i) => [b] -> i

那么，如果想要使用更加通用的方法来替代fromIntegral，该怎么做呢：

import Data.List

average xs = realToFrac (sum xs) / genericLength xs

这个只有一个实数约束（Int、Integer、Float、Double）的...

average :: (Real a, Fractional b) => [a] -> b

这将使任何实数变成分数。

注意到所有的帖子提到了Haskell中的多态数值字面量。1不是整数，它可以是任何数字。

Real类只提供了一种方法：将类Num中的值转换为有理数。这正是我们在这里所需要的。

因此，

Prelude> average ([1 .. 10] :: [Double])
5.5
Prelude> average ([1 .. 10] :: [Int])
5.5
Prelude> average ([1 .. 10] :: [Float])
5.5
Prelude> average ([1 .. 10] :: [Data.Word.Word8])
5.5