1

Is there a concept of range in Haskell or other functional programming languages? Suppose I want to compute I_AMAX from BLAS (to find the smallest index of the largest element in vector x). A naive method would be something like

idamax x idx = foldr(imax) 0 (zip x idx)

where idx is the index vector and imax returns the tuple with the smallest index and largest value.

For example, some vector (say, [1, 7, 3, 5]), zipped with its index vector ([0, 1, 2, 3], which makes [(1, 0), (7, 1), (3, 2), (5, 2)]), then reduced with the maximum function (so (7, 1), or 7).

But the index knowledge should be implicit, since in a loop the index is self-evident. Is there a way to write this in Haskell?

tl;dr, what's the best way to write I_AMAX in Haskell?

xiii1408
  • 361
  • 2
  • 11

1 Answers1

0

Here's a version:

idamax :: Ord a => [a] -> Int
idamax = negate . snd . maximum . flip zip [0, -1..]

Explanation

First note that zipping to lists yields a list with length of the shortest input list. So we can use [0..] to attach natural indices to list elements:

zip [0..] [1, 7, 3, 5] = [(0, 1), (1, 7), (2, 3), (3, 5)]

So what we do is:

  1. attach an (negated) index to each element in a list
  2. find a pair with max value and least index (which is max here because of previous negation)
  3. extract index from resulting pair
  4. negate it back

For example, starting with [1, 4, 2, 4]:

  1. attach index: [(1, 0), (4, -1), (2, -2), (4, -3)]
  2. find maximum: (4, -1) (note that (4, -1) > (4, -3))
  3. extract index: -1
  4. negate: 1

Examples

>>> idamax [1..10]
9
>>> idamax [1, 3, 4, 2, 4]
2
>>> idamax "oh hello"
0
fizruk
  • 1,855
  • 14
  • 24
  • Thanks for your response--but is there a way to compute it without having to generate the array? [0, -1..] – xiii1408 May 19 '14 at 14:23
  • 1
    @xiii1408 this is list (not array) and it will be fused by compiler in this case (i.e. it won't exist as a whole at runtime), because `maximum` needs only one pass and `zip` can yield resulting list incrementally (one element per time). This is a basic optimisation called "list fusion" (or "stream fusion"). Check this another SO question for more: http://stackoverflow.com/questions/578063/what-is-haskells-stream-fusion – fizruk May 19 '14 at 14:29
  • 2
    An infinite index list is *the* idiomatic Haskell way to deal with things like loop counters. – n. m. could be an AI May 19 '14 at 15:01