使用折叠的列表的局部最大值。

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?

是否有办法通过foldr或foldl找到一个列表的局部极大值，或者我必须使用unfoldr，因为列表的第一个和最后一个元素不是本地最大值?

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)

8 个解决方案

#1

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)

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).

它的意思是，您将一个tuple传递给它，而不是一个结果列表。tuple(一个三元组)将包含最后两个元素和结果列表。该函数计算三的第二个元素是否是局部最小的w.r.t.，第一个元素(它的前身)和当前的元素(它的继承者)通过。

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.

无论如何，从这个角度来看，当输入列表太短时，使用您喜欢的任何方法来返回空结果列表是很容易的。

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.

请注意，通过使用foldl，每个新结果都被添加到顶部。正因为如此，结果的列表被颠倒了。如果你想让lmax与原始列表中的顺序相同，那么你可能想要再次反转lmax的结果:lmax' =反向。lmax。

#2

You could, but itd be very ugly. Mostly because to find the local maximum, you'll need to know the previous and next elements.

你可以，但它很丑。主要是因为要找到本地最大值，您需要知道前面和下一个元素。

The previous element is no problem, but a fold isn't supposed to know anything about the elements after it.

前面的元素没有问题，但是折叠不应该知道后面的元素。

As a possible approach

作为一种可能的方法

 import Data.List (zip3)

 localMax xs = map proj2
               . filter isLocalMax
               $ zip3 xs (tail xs) (drop 2 xs)
   where isLocalMax (x, y, z) = x < y && z < y
         proj2 (_,x,_) = x

So we shift the list by one and two and zip it all together so [a, b, c, d, e] becomes [(a, b, c), (b, c, d), (c, d, e)] then we just use map and filter to select the appropriate elements.

因此，我们将列表按1和2进行转换，并将其压缩到一起(a, b, c, d, e)变成[(a, b, c)， (b, c, d)， (c, d, e)]然后我们只使用map和filter来选择合适的元素。

Do note though that map and filter could be smashed into one foldr if you really wanted to.

请注意，如果你真的想要的话，那地图和过滤器可以被粉碎成一个foldr。

#3

localMaxAsUnfold :: [Int] -> [Int]
localMaxAsUnfold = unfoldr work
  where
    work (x:y:z:rest)
      | y > x && y > z = Just (y, y:z:rest)
      | otherwise      = work (y:z:rest) -- cheat and recurse internally
    work _             = Nothing

localMaxAsFold :: [Int] -> [Int]
localMaxAsFold = foldr work [] . makeTriples
  where
    makeTriples :: [Int] -> [(Int, Int, Int)]
    makeTriples vals = zip3 vals (tail vals) (drop 2 vals)

    work (x,y,z) vals
      | y > x && y > z = y : vals
      | otherwise      = vals

#4

we can always call the shortsighted¹foldr over (init . tails) to emulate the insightful paramorphism:

我们总可以把这个短时间的缩略图称为init (init)。模仿富有洞察力的同构:

import Data.List
import Control.Applicative

localMaxima :: Ord a => [a] -> [a]
localMaxima = foldr g [] . init . tails . (zip <*> tail) 
   where
     g ((a,b):(_,c):_) r | a<b && b>c = b:r
     g  _              r              =   r

In this particular case init can be omitted. zip <*> tail (which is just a shorthand for \xs -> zip xs (tail xs)) forms a list of pairs of consecutive elements from the input list.

在这个特殊的例子中，init可以省略。zip <*> tail(它只是\xs -> zip xs (tail xs)的简写)，它从输入列表中形成一系列连续元素的列表。

And no, I don't think it is particularly "ugly".² :)

不，我不认为它特别“丑”。2:)

¹² cf. this answer here
² also another answer here

1 2 cf，这里2也有一个答案。

#5

Idea is very close to what Will Ness suggested, but without applicative zips and a bit shorter:

想法非常接近于所建议的内容，但没有应用的拉链和更短的:

lm a = foldr (\(x:y:z:_) a -> if y > z && y > x then y:a else a) [] 
             $ filter ((2<) . length) (tails a)

Readability still questionable though :)

可读性仍然值得怀疑:

Update As suggested by Will Ness, list comprehension also can be used:

根据Will Ness的建议更新，列表理解也可以使用:

lm a = [y | (x:y:z:_) <- tails a, x < y && y > z]

#6

Here is another one that doesn't pattern match on the list at all and uses only fold:

这是另一个在列表上没有模式匹配的，只使用折叠:

g :: a -> (a -> Bool) -> (a -> Bool) -> [a]
g x p n | p x && n x = [x]
        | otherwise  = []

localMax :: Ord a => [a] -> [a]
localMax l = fr $ const False
  where (_, fr) = foldr worker (const False, \_ -> []) l
        worker x (p,f) = ((> x), \n -> g x p n ++ f (> x))

How does this work?

The basic idea is to use a function in the accumulator, so that we can "pass back" a later element to a previous stage. So we pass back a function of type a -> Bool, that returns True only if the next element is greater than the argument. (this function is called n for nextin the code above). We also have another function of type a -> Bool in the accumulator which returns True if the previous element is less than the passed value (called p for previous). We have a maximum exactly when both of the functions return True. This is what g checks.

基本思想是在累加器中使用一个函数，这样我们就可以将后面的元素“传回”到先前的阶段。所以我们返回a类型的函数-> Bool，只有当下一个元素大于参数时才返回True。(此函数称为n，用于nextin上面的代码)。在累加器中，我们还有另一个类型为a -> Bool的函数，如果前面的元素小于传递值(之前称为p)，则返回True。当两个函数返回True时，我们有一个最大值。这是g检查。

Example

*Main> localMax [3,4,2,5,1,7,6,1,9]
[4,5,7]
*Main> localMax [1..10]
[]
*Main> localMax []
[]

#7

Here is another one with zipWith

这是另一个带拉链的。

localMax a = [ x | (x,v) <- zip a localMaxInd, v]
where  
   localMaxInd = zipWith (&&) u v
         where 
              u = False : zipWith (>) (tail a) a
              v = zipWith (>) a (tail a) 

test case

测试用例

> localMax [3,4,2,5,1,7,6,1,9]
[4,5,7]

#8

I'd like to @jozefg's answer, that it is possible to express the whole thing using folds. Any recursive operation on lists can be eventually expressed using foldr, but often it's quite ugly.

我想要@jozefg的答案，可以用折叠来表达整个事情。在列表上的任何递归操作最终都可以使用foldr来表示，但通常情况下是相当丑陋的。

First let's implement locMax using mapMaybe and zip, very similarly to what @jozefg did::

首先让我们使用mapMaybe和zip来实现locMax，非常类似于@jozefg所做的::

import Prelude hiding (zip)

isMax :: (Ord a) => ((a, a), a) -> Maybe a
isMax ((x, y), z) | y > z && y > x   = Just y
                  | otherwise        = Nothing

locMax :: (Ord a) => [a] -> [a]
locMax xs@(_:xs'@(_:xs'')) = mapMaybe isMax $ zip (zip xs xs') xs''

Implementing mapMaybe using foldr isn't so difficult:

实现mapMaybe使用foldr并不是那么困难:

mapMaybe :: (a -> Maybe b) -> [a] -> [b]
mapMaybe f = foldr (\x xs -> maybe xs (: xs) (f x)) []

Implementing zip is a bit more tricky, since we need to consume two lists at once. What we'll do is that we'll accumulate inside foldr a function of type [b] -> [(a,b)] that'll consume the second list.

实现zip比较麻烦，因为我们需要同时使用两个列表。我们要做的是，我们将在foldr中积累a类型的函数[b] -> [(a,b)]，这将消耗第二个列表。

The base case is simple. If the first list is empty, the constructed function is const [], so whatever is the second list, the result is also empty.

基本情况很简单。如果第一个列表为空，则构造函数为const[]，因此无论第二个列表是什么，结果也是空的。

The folding step takes a value x : a, an accumulated function that converts a sub-list of [b]. And since we're producing a function again, we just take a third argument of type [b]. If there are no bs, the result is an empty list. If there is at least one, we construct a pair and call f on the rest of bs:

折叠步骤使用一个值x: a，它是一个累积的函数，它可以转换[b]的子列表。因为我们又在生成一个函数，我们只需要第三个类型的参数[b]。如果没有b，结果就是一个空列表。如果至少有一个，我们构造一对，并把f称为b的其余部分:

zip :: [a] -> [b] -> [(a,b)]
zip = foldr step (const [])
  where
    step _ _ []       = []
    step x f (y : ys) = (x, y) : f ys

You can verify that this implementation has the required properties and works properly also if one or both lists are infinite.

您可以验证这个实现是否具有所需的属性，并且如果一个或两个列表是无限的，也可以正常工作。