在 Haskell 中查找大型列表的最小元素索引

Question

我知道某种方法可以找到最小元素的索引，但是当我处理大列表时。GHC说："堆叠溢出"

所以我去堆栈溢出。

Prelude> :m Data.List
Prelude Data.List> let a = reverse [1..10000000]
Prelude Data.List> elemIndex  (minimum a) a
*** Exception: stack overflow

这种方式比使用Elemindex更好，但无法解决"反向[1..100000000]'。

subset [] = [[]]
subset (x:xs) = s ++ map ( x : ) s
where s = subset xs
minIndex xs = snd . minimum $ zip xs [0..]

我如何找到大列表的最小元素的索引？

您最好不要使用其他模块，只使用前奏。

Answer 1

elemIndex (foldl1' min a) a

必不可少的部分是使用foldl1' min而不是minimum。minimum的评估构建并返回一个巨大的Redex，其评估导致堆栈溢出。

所有血腥详细信息：https：//wiki.haskell.org/foldr_foldl_foldl'

关于与Haskell中表现有关的严格讨论：https：//wiki.haskell.org/performance/strictness