使用折叠的列表的局部最大值 [英] Local maxima of list using fold

问题描述

是否可以使用 foldr 或 foldl 找出列表的局部最大值，或者可能因为第一个原因我必须使用 unfoldr list的最后一个元素不是局部最大值吗?

Is there any way to find out local maxima of a list using foldr or foldl or maybe I have to use unfoldr because of first and last elements of list aren't local maximums?

我了解如何使用带有警卫的递归来找到它，例如

I understand how to find it using recursion with guards, e.g.

localMax :: [Int] -> [Int]
localMax []       = []
localMax (x:[])   = []
localMax (x:y:[]) = []
localMax (x:y:z:zs)
    | y > z && y > x = y:localMax (y:z:zs)
    | otherwise = localMax (y:z:zs)

推荐答案

我将按照您的要求仅使用折叠.那这样的事呢?

I'll try to only use the fold, as you asked. What about something like this?

lmax (x:y:xs) = third $ foldl f (x,y,[]) xs
  where
    third (_, _, x) = x
    f (x, y, ls) z = (y, z, if y > x && y > z then y:ls else ls)

这个想法是，您在折叠中传递一个元组，而不是结果列表.元组(三元组)将包含最后两个元素和结果列表.该函数评估三元组的第二个元素是否为局部最小值w.r.t.第一个元素(其前任元素)和折叠传递的当前元素(其后任元素).

The idea is that you pass a tuple in the fold instead of a list of results. The tuple (a triple) will contain the last two elements and the list of results. The function evaluates whether the second element of the triple is a local minimum w.r.t. the first element (its predecessor) and the current element passed by the fold (its successor).

ghci> lmax [1,3,2]
[3]
ghci> lmax [3,4,2,5,1,7,6,1,9]
[7,5,4]
ghci> lmax [1..10]
[]
ghci> lmax []
*** Exception: test.hs:(4,1)-(5,66): Non-exhaustive patterns in function lmax

无论如何，从此开始，只要输入列表太短，就可以轻松使用您喜欢的任何方法来返回空结果列表.

Anyway, from this it should be easy to use whatever method you prefer in order to return an empty result list when the input list is too short.

请注意，通过使用 foldl ，每个新结果都将附加在顶部.因此，结果列表是相反的.如果要按与原始列表相同的顺序使 lmax 的结果再次反转: lmax'= reverse.lmax .

Please note that, by using foldl, every new result is appended at the top. Because of this, the list of results is reversed. You might want to reverse again lmax's results if you want to have them in the same order as in the original list: lmax' = reverse . lmax.

这篇关于使用折叠的列表的局部最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！