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

Your function can be constructed out of ready-made parts as

import Data.Maybe (listToMaybe)
import Data.List  (sortBy)
import Data.Ord   (comparing)

foo :: (Ord a, Enum b) => a -> [a] -> Maybe b
foo x = fmap fst . listToMaybe . take 1 
                 . dropWhile ((<= x) . snd) 
                 . sortBy (comparing snd) 
                 . dropWhile ((/= x) . snd)
                 . zip [toEnum 0..] 

This Maybe finds the index of the next smallest element in the list above the given element, situated after the given element, in the input list. As you've requested.

You can use any Enum type of your choosing as the index.

Now you can implement this higher-level executable specs as direct recursion, using an efficient Map data structure to hold your sorted elements above x seen so far to find the next smallest, etc.

Correctness first, efficiency later!

---

Efficiency update: dropping after the sort drops them sorted, so there's a wasted effort there; indeed it should be replaced with the filtering (as seen in the answer by Luis Morillo) before the sort. And if our element type is in Integral (so it is a properly discrete type, unlike just an Enum, thanks to @dfeuer for pointing this out!), there's one more opportunity for an opportunistic optimization: if we hit on a succ minimal element by pure chance, there's no further chance of improvement, and so we should bail out at that point right there:

bar :: (Integral a, Enum b) => a -> [a] -> Maybe b
bar x = fmap fst . either Just (listToMaybe . take 1 
                                . sortBy (comparing snd))
                 . findOrFilter ((== succ x).snd) ((> x).snd)
                 . dropWhile ((/= x) . snd)
                 . zip [toEnum 0..] 

findOrFilter :: (a -> Bool) -> (a -> Bool) -> [a] -> Either a [a]
findOrFilter t p = go 
   where  go []                 = Right []
          go (x:xs) | t x       = Left   x
                    | otherwise = fmap ([x | p x] ++) $ go xs

Testing:

> foo 5 [2,3,5,4,6,5,2,1,7,9,2] :: Maybe Int
Just 4
> foo 2 [2,3,5,4,6,5,2,1,7,9,2] :: Maybe Int
Just 1
> foo 1 [3,5,4,6,5,2,1,7,9,2] :: Maybe Int
Just 9

Answer 3

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.

Answer 4

It is not clear for me what do you want exactly. Based on examples I guess it is: find the index of the smallest element higher than x which appears after x. In that case, This solution is plain Prelude. No imports

minList :: Ord a => a -> [a] -> Int
minList x l = snd . minimum . filter (\a -> x < fst a) . dropWhile (\a -> x /= fst a) $ zip l [0..]

The logic is:

• create the list of pairs, [(elem, index)] using zip l [0..]
• drop elements until you find the input x using dropWhile (\a -> x /= fst a)
• discards elements less than x using filter (\a -> x < fst a)
• find the minimum of the resulting list. Tuples are ordered using lexicographic order so it fits your problem
• take the index using snd