Haskell数组最大元素索引计算：现有实现错误排查

需求 #

给定一个数组，找出其中唯一最大元素对应的索引。

错误实现代码 #

maxIndex' :: (Ix i, Ord a) => Array i a -> [i] -> i -> a -> i -> a -> i
maxIndex' arr ids index element maxIndex maxElement
  | length ids == 1 && element > maxElement = index
  | length ids == 1 && element <= maxElement = maxIndex
  | element > maxElement = maxIndex' arr (tail ids) (head ids) (arr ! head ids) index element
  | otherwise = maxIndex' arr (tail ids) (head ids) (arr ! head ids) maxIndex maxElement

maxIndex :: (Ix i, Ord a) => Array i a -> i
maxIndex arr = maxIndex' arr (tail (indices arr)) firstIndex firstMaximum firstIndex firstMaximum
  where
    firstIndex = head (indices arr)
    firstMaximum = arr ! firstIndex

测试结果 #

print (maxIndex (array (False,True) [(False,54),(True,104)])) -- 输出False（预期应为True）
print (maxIndex (array (False,True) [(True,104),(False,54)])) -- 输出False（预期应为True）

问题分析 #

这段代码的核心错误是递归终止逻辑完全错误：

• 错误地将length ids == 1作为终止条件，此时待处理的索引列表ids中还有一个元素未参与对比，直接拿初始第一个元素的值和当前最大值比较，完全跳过了ids头部元素的处理
• 初始调用时element参数固定为第一个元素的值，递归过程中没有更新为当前待处理索引的元素值，导致后续元素根本没参与最大值对比

修正方案 #

调整递归逻辑，让函数遍历所有索引，每次对比当前索引的元素值和记录的最大值，更新最大索引：

修正后的递归实现 #

maxIndex' :: (Ix i, Ord a) => Array i a -> [i] -> i -> a -> i
-- 所有索引处理完毕，返回记录的最大索引
maxIndex' _ [] currentMaxIndex _ = currentMaxIndex
maxIndex' arr (currentId:remainingIds) currentMaxIndex currentMaxVal
  | currentVal > currentMaxVal = 
      -- 当前元素更大，更新最大索引和值，继续处理剩余索引
      maxIndex' arr remainingIds currentId currentVal
  | otherwise = 
      -- 当前元素不更大，保留原最大索引，继续处理剩余索引
      maxIndex' arr remainingIds currentMaxIndex currentMaxVal
  where currentVal = arr ! currentId

maxIndex :: (Ix i, Ord a) => Array i a -> i
maxIndex arr = maxIndex' arr (tail indicesList) firstIndex firstMaxVal
  where
    indicesList = indices arr
    firstIndex = head indicesList
    firstMaxVal = arr ! firstIndex

更简洁的fold实现 #

如果不想手动写递归，也可以用foldl'遍历索引，代码更简洁易读：

import Data.List (foldl')

maxIndex :: (Ix i, Ord a) => Array i a -> i
maxIndex arr = fst $ foldl' updateMax initialMaxPair (tail indicesList)
  where
    indicesList = indices arr
    firstIndex = head indicesList
    initialMaxPair = (firstIndex, arr ! firstIndex)
    -- 对比当前索引元素和已记录的最大值，更新最大索引和值
    updateMax (currMaxIdx, currMaxVal) idx =
      let val = arr ! idx
      in if val > currMaxVal then (idx, val) else (currMaxIdx, currMaxVal)

修正后测试结果 #

两个测试用例都会返回True，符合预期。

内容的提问来源于stack exchange，提问作者coderodde