Get index of next smallest element in the list in Haskell

Question

I m a newbie to Haskell. I am pretty good with Imperative languages but not with functional. Haskell is my first as a functional language.

I am trying to figure out, how to get the index of the smallest element in the list where the minimum element is defined by me.

Let me explain by examples.

For example :

Function signature minList :: x -> [x]

let x = 2
let list = [2,3,5,4,6,5,2,1,7,9,2] 

minList x list --output 1 <- is index

This should return 1. Because the at list[1] is 3. It returns 1 because 3 is the smallest element after x (=2).

let x = 1
let list = [3,5,4,6,5,2,1,7,9,2] 
minList x list -- output 9 <- is index

It should return 9 because at list[9] is 2 and 2 is the smallest element after 1. x = 1 which is defined by me.

What I have tried so far.

minListIndex :: (Ord a, Num  a) => a -> [a] -> a
minListIndex x [] = 0
minListIndex x (y:ys) 
            | x > y =  length ys
            | otherwise = m
            where m = minListIndex x ys

When I load the file I get this error

• Couldn't match expected type ‘a’ with actual type ‘Int’
      ‘a’ is a rigid type variable bound by
        the type signature for:
          minListIndex :: forall a. (Ord a, Num a) => a -> [a] -> a
        at myFile.hs:36:17
    • In the expression: 1 + length ys
      In an equation for ‘minListIndex’:
          minListIndex x (y : ys)
            | x > y = 1 + length ys
            | otherwise = 1 + m
            where
                m = minListIndex x ys
    • Relevant bindings include
        m :: a (bound at myFile.hs:41:19)
        ys :: [a] (bound at myFile.hs:38:19)
        y :: a (bound at myFile.hs:38:17)
        x :: a (bound at myFile.hs:38:14)
        minListIndex :: a -> [a] -> a (bound at myFile.hs:37:1)

When I modify the function like this

minListIndex :: (Ord a, Num  a) => a -> [a] -> a
minListIndex x [] = 0
minListIndex x (y:ys) 
            | x > y =  2 -- <- modified...
            | otherwise = 3 -- <- modifiedd
            where m = minListIndex x ys

I load the file again then it compiles and runs but ofc the output is not desired.

What is the problem with

| x > y =  length ys
| otherwise = m

?

In short: Basically, I want to find the index of the smallest element but higher than the x which is defined by me in parameter/function signature.

Thanks for the help in advance!

Answer 1

minListIndex :: (Ord a, Num  a) => a -> [a] -> a

The problem is that you are trying to return result of generic type a but it is actually index in a list.

Suppose you are trying to evaluate your function for a list of doubles. In this case compiler should instantiate function's type to Double -> [Double] -> Double which is nonsense.

Actually compiler notices that you are returning something that is derived from list's length and warns you that it is not possible to match generic type a with concrete Int.

length ys returns Int, so you can try this instead:

minListIndex :: Ord a => a -> [a] -> Int

---

Regarding your original problem, seems that you can't solve it with plain recursion. Consider defining helper recursive function with accumulator. In your case it can be a pair (min_value_so_far, its_index).

Answer 2

First off, I'd separate the index type from the list element type altogether. There's no apparent reason for them to be the same. I will use the BangPatterns extension to avoid a space leak without too much notation; enable that by adding {-# language BangPatterns #-} to the very top of the file. I will also import Data.Word to get access to the Word64 type.

There are two stages: first, find the index of the given element (if it's present) and the rest of the list beyond that point. Then, find the index of the minimum of the tail.

-- Find the 0-based index of the first occurrence
-- of the given element in the list, and
-- the rest of the list after that element.
findGiven :: Eq a => a -> [a] -> Maybe (Word64, [a])
findGiven given = go 0 where
  go !_k [] = Nothing --not found
  go !k (x:xs)
    | given == xs = Just (k, xs)
    | otherwise = go (k+1) xs

-- Find the minimum (and its index) of the elements of the
-- list greater than the given one.
findMinWithIndexOver :: Ord a => a -> [a] -> Maybe (Word64, a)
findMinWithIndexOver given = go 0 Nothing where
  go !_k acc [] = acc
  go !k acc (x : xs)
    | x <= given = go (k + 1) acc xs
    | otherwise
    = case acc of
        Nothing -> go (k + 1) (Just (k, x)) xs
        Just (ix_min, curr_min)
          | x < ix_min = go (k + 1) (Just (k, x)) xs
          | otherwise = go (k + 1) acc xs

You can now put these functions together to construct the one you seek. If you want a general Num result rather than a Word64 one, you can use fromIntegral at the very end. Why use Word64? Unlike Int or Word, it's (practically) guaranteed not to overflow in any reasonable amount of time. It's likely substantially faster than using something like Integer or Natural directly.