haskell - 在 Haskell 中查找列表的最大元素和索引

Question

我正在迈出进入 Haskell 美妙世界的第一步。作为练习，我想实现一个方法来查找列表的最大元素及其索引。我们称这个函数为“maxi”。在列表上调用 maxi 应返回以下结果:

ghci> maxi [1, 3, 4, 1, 2, 3]
(4, 2)

4 是这个列表中最大的 int，它位于索引 2 处。

我试图按如下方式实现此功能:

maxim :: (Ord a) => [a] -> (a, Int)
maxim l = 
  let pmaxim :: (Ord a) => [a] -> Int -> (a, Int) -- Internal function to do the work
      pmaxim [] _  = error "Empty list"           -- List is empty, error
      pmaxim [x] xi = (x, xi)                     -- List has one item, return it and the index
      pmaxim (x:xs) xi                            -- More than one item, break list apart
        | x > t     = (x, xi)                     -- If current item is bigger, return it and its index
        | otherwise = (t, ti)                     -- If list tail has a bigger item, return that
        where (t, ti) = pmaxim xs (ti + 1)        -- Get max of tail of the list
  in pmaxim l 0                                   -- Call internal function with start index

当我调用它时，我得到了一些非常奇怪的东西:ghci 在返回最大元素的值后似乎挂起。

ghci> maxi [1, 3, 4, 1, 2, 3]
(4,

我冒昧地猜测这与 Haskell 的懒惰评估性质有关，但我发现很难弄清楚这里到底发生了什么，以及如何解决它。我也非常感谢任何人关于如何在 Haskell 中调试的任何提示。有没有一种简单的方法可以在执行期间打印出值而不影响行为？

我只是想指出，我知道有几种更好的方法可以使用内置的 Haskell 函数来获得这种行为。我正在从头开始实现它以尝试学习 Haskell。

谢谢

Answer 1

这是因为您的代码中有一个小错误。你有:

where (t, ti) = pmaxim xs (ti + 1)

...但实际上应该是:

where (t, ti) = pmaxim xs (xi + 1)

这修复了您的代码，现在产生了正确的解决方案:

>>> maxim [1, 2, 3, 2, 1]
(3, 2)

您的代码挂起，因为您对 ti 的计算导致无限循环，因为您不小心根据自身定义了它。请注意 ghc是一个足够聪明的编译器，并计算出 t不依赖于 ti 的值，这就是为什么您的版本即使无法计算索引也可以成功计算最大值的原因。

调试纯计算的标准方法是 Debug.Trace模块。

作为旁注，有一个更简单的解决方案:

import Data.List
import Data.Ord

maxi xs = maximumBy (comparing fst) (zip xs [0..])

编辑:哎呀，我没有看到你是故意从头开始实现它，但我还是把它留在那里。