algorithm - Haskell递归 - 找到列表中数字之间的最大差异

Question

这是手头的问题:我需要使用递归找到列表中相邻数字之间的最大差异。以下面的列表为例:[1,2,5,6,7,9]。两个相邻数字之间的最大差值是 3(介于 2 和 5 之间)。

我知道递归可能不是最好的解决方案，但我正在努力提高我在 Haskell 中使用递归的能力。

这是我目前拥有的当前代码:

largestDiff (x:y:xs) = if (length (y:xs) > 1) then max((x-y), largestDiff (y:xs)) else 0

基本上 - 列表会越来越短，直到达到 1(即无法比较更多数字，然后返回 0)。当 0 向上传递调用堆栈时，max 函数随后用于实现“山丘之王”类型的算法。最后 - 在调用堆栈的末尾，应该返回最大的数字。

问题是，我的代码中出现了一个我无法解决的错误:

Occurs check: cannot construct the infinite type:
  t1 = (t0, t1) -> (t0, t1)
In the return type of a call of `largestDiff'
Probable cause: `largestDiff' is applied to too few arguments
In the expression: largestDiff (y : xs)
In the first argument of `max', namely
  `((x - y), largestDiff (y : xs))'

有没有人可以分享一些智慧的话？

感谢您的宝贵时间!

编辑:感谢大家抽出时间 - 经过多次试验和错误，我最终独立发现了一种更简单的方法。

largestDiff [] = error "List too small"
largestDiff [x] = error "List too small"
largestDiff [x,y] = abs(x-y)
largestDiff (x:y:xs) = max(abs(x-y)) (largestDiff (y:xs))

再次感谢大家!

Answer 1

所以你的代码抛出错误的原因是因为

max((x-y), largestDiff (y:xs))

在Haskell中，你不在参数周围使用括号，而是用逗号分隔它们，正确的语法是

max (x - y) (largestDiff (y:xs))

您使用的语法被解析为

max ((x - y), largestDiff (y:xs))

看起来你正在将一个元组传递给 max!

但是，这并没有解决问题。我总是返回 0。相反，我建议将问题分解为两个函数。您想计算差异的最大值，因此首先编写一个函数来计算差异，然后再编写一个函数来计算这些差异的最大值:

diffs :: Num a => [a] -> [a]
diffs [] = []                            -- No elements case
diffs [x] = []                           -- One element case
diffs (x:y:xs) = y - x : diffs (y:xs)    -- Two or more elements case

largestDiff :: (Ord a, Num a) => [a] -> a
largestDiff xs = maximum $ map abs $ diffs xs

请注意我是如何将递归提取到最简单的可能情况中的。我们不需要在遍历列表时计算最大值；有可能，只是更复杂。由于 Haskell 有一个方便的内置函数来为我们计算列表的最大值，我们也可以利用它。我们的递归函数简洁明了，然后结合 maximum 来实现所需的 largestDiff。仅供引用，diffs 实际上只是一个计算数字列表的导数的函数，它对于数据处理可能是一个非常有用的函数。

编辑:largestDiff 需要Ord 约束，并在计算最大值之前添加到map abs 中。