How to get the last element of a list matching a condition?-CodePudding

So I have a list list of numbers from 3 to 10. I want to get the last number that is bigger than 5 and smaller than 11.

*Main> greatestIndexInRange [3, 6, 7, 2, 5, 1, 0, 10, 2] 5 11

CodePudding user response：

You could reverse the list, filter by your predicate and select the resulting list's head (which would be the last element in the original list) in linear time. Or you could select the last element in the filtered list.

greatestIndexInRange :: Ord a => [a] -> a -> a -> a
greatestIndexInRange xs l h = head . filter (\x -> x > l && x < h) . reverse $ xs

greatestIndexInRange :: Ord a => [a] -> a -> a -> a
greatestIndexInRange xs l h = last $ filter (\x -> x > l && x < h) xs

For example:

greatestIndexInRange [3, 6, 7, 2, 5, 1, 0, 10, 2] 5 11
-- 10

Note that this is a partial function that will fail if no element in the list is in the given range, e.g.:

greatestIndexInRange [1, 2, 3] 5 11
*** Exception: Prelude.head: empty list

As Chris suggested in the comments, you could also use find from Data.List on the reversed list instead of filter head for a slightly more elegant implementation:

import Data.List (find)

greatestIndexInRange :: Ord a => [a] -> a -> a -> Maybe a
greatestIndexInRange xs l h = find (\x -> x > l && x < h) . reverse $ xs

The function now returns a Maybe. This would also resolve the above issue of it being a partial function:

greatestIndexInRange [3, 6, 7, 2, 5, 1, 0, 10, 2] 5 11
-- Just 10
greatestIndexInRange [1, 2, 3] 5 11
-- Nothing

CodePudding user response：

This will let you do what you want on GHC 9.2 or newer:

{-# LANGUAGE ImpredicativeTypes #-}

import Data.Functor.Identity

lastJust :: forall f a b. Foldable f => (a -> Maybe b) -> f a -> Maybe b
lastJust p xs = foldr go id xs Nothing where
  go :: a -> (forall t. Applicative t => t b -> t b) -> forall t. Applicative t => t b -> t b
  go x acc z = case p x of
    Just j -> pure . runIdentity $ acc (Identity j)
    Nothing -> acc z

CodePudding user response：

You don't want to filter all elements and then use last. If the list is huge, it would not be efficient. I prefer getting the result faster using more memory than getting it slower with less memory. Nowadays, memory is cheaper than time.

You only want the last element that satisfies your predicate. So it would be wise to wrap it in a Maybe in case there is none. The idea is that you need to get to the end of the list somehow, for example using reverse. So I can't think of a better solution than linear time.

import Data.List    
greatestIndexInRange :: Ord a => [a] -> a -> a -> Maybe a
greatestIndexInRange xs x y = find (\z -> z > x && z < y) (reverse xs)

Output:

*Main Data.List> greatestIndexInRange [3, 6, 7, 2, 5, 1, 0, 10, 2] 5 11
Just 10
*Main Data.List> greatestIndexInRange [1, 2, 3] 5 11
Nothing