如何获取与条件匹配的列表的最后一个元素？

Question

因此，我有一个从3到10的数字列表。我想获得大于5和小于11的最后一个数字。

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

Answer 1

您可以 反向列表， >通过您的谓词，然后选择结果列表的 /code> （这将是原始列表中的最后一个元素），以线性时间为单位。或者，您可以选择 /a>元素中的元素。

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

例如：

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

请注意，这是一个部分函数，​​如果列表中的列表中没有元素在给定范围内，例如：

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

正如克里斯在评论中所建议的那样，您也可以使用过滤+ HEAD ，以稍微优雅的实现：

import Data.List (find)

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

该功能现在返回也许。这也将解决以上问题的部分功能：

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

Answer 2

您可能希望选择过滤使用上次，而不是使用反向与查找。更好的解决方案取决于以下因素，例如：我们想要的元素列表中的位置，与列表中存在的谓词相匹配的元素等等。美好的！

例如，如果我们想要的元素是一个开始时，则一定要逆转并使用查找比使用 filter 与 last 更糟糕。
同样，如果我们有很多元素与过滤器的谓词（均匀分布在列表中分布），那么您将更好地反转列表并使用查找。

如果没有，则将您的结果包裹在中是明智的，以防万一没有。这个想法是您需要以某种方式进入列表的结尾。因此，无论哪种方式，除非订购列表，否则您将获得比线性时间更好的解决方案。

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

输出：

*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

Answer 3

这将使您在GHC 9.2或更新中做您想做的事：

{-# LANGUAGE ImpredicativeTypes #-}

import Control.Monad
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 = maybe (acc z) (pure . runIdentity . acc . Identity) $ p x

greatestIndexInRange :: (Foldable t, Ord a) => t a -> a -> a -> Maybe a
greatestIndexInRange xs lo hi = lastJust (\x -> x <$ guard (x > lo && x < hi)) xs

Answer 4

您可以使用以下简单实现。

import Control.Applicative ((<|>))

greatestIndexInRange :: [Int] -> Int -> Int -> Maybe Int
greatestIndexInRange [] _ _ = Nothing
greatestIndexInRange (x:xs) lo hi = res <|> if inRng x then Just x else Nothing
  where
    inRng x = x > lo && x < hi
    res = greatestIndexInRange xs lo hi

另外，使用 foldr 而不是递归：

import Control.Applicative ((<|>))

greatestIndexInRange :: [Int] -> Int -> Int -> Maybe Int
greatestIndexInRange nums lo hi = foldr f Nothing nums
  where
    inRng x = x > lo && x < hi
    f x res = res <|> if inRng x then Just x else Nothing

我们记住在给定范围内的最后一个值，并将其替换为当前值（如果在给定范围内）。我们还考虑一个事实，即在给定范围内可能没有值。