Local maxima of list using fold

Question

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)

Answer 1

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.

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

Answer 2

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

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.

Answer 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

Answer 4

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

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.

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

^{1 2} cf. this answer here
² also another answer here

Answer 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:

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

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

Example

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

Answer 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]

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

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

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 :: (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.

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.

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:

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.