CODEWITHSUNDEEP
haskell
aurexav
aurexav

Reputation: 2865

Find min element's index of a large list in Haskell

i know some way to find the min or max element's index, but when i deal with a large list. ghc said:"stack overflow"

So i go to stack overflow.

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

This way is better than using elemIndex but it can't solve 'reverse [1..100000000]'.

subset [] = [[]]
subset (x:xs) = s ++ map ( x : ) s
where s = subset xs

minIndex xs = snd . minimum $ zip xs [0..]

How can i find min element's index of a large list?

You'd better not use other module, just using prelude.

Upvotes: 0

Views: 2166

Answers (1)

shinobi
shinobi

Reputation: 361

elemIndex (foldl1' min a) a

The essential part is using foldl1' min instead of minimum. The evaluation of minimum builds and returns a huge redex, whose evaluation causes stack overflow.

All the gory details: https://wiki.haskell.org/Foldr_Foldl_Foldl%27

A general discussion of strictness in relation to performance in Haskell: https://wiki.haskell.org/Performance/Strictness

Upvotes: 1

Related Questions