在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似乎在返回max element的值后挂起.

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..])

编辑:糟糕,我没有看到你是故意从头开始实现它,但我仍然会留在那里.