Beginner filter use

Learn
#1

Hi everyone, very noob question here:

– From the input list create an output list which contains local maxima - only the elements bigger than both predecessor and successor

localMaxima :: [Int] → [Int]
localMaxima [] = []
localMaxima [a] = []
localMaxima [a, b] = []
localMaxima (x:y:z:zs) = filter cond (x:y:z:zs)
where
cond y = (y > x) && (y > z)

GHCi returns:
*Main> localMaxima [1,2,85,3]
[]

I don’t understand how pattern matching is working inside filter.

#2

Here is some (slightly informal) equational reasoning:

   localMaxima [1,2,85,3]
= { desugar }
   localMaxima (1 : 2 : 85 : 3 : [])
= { pattern match where: x = 1, y = 2, z = 85, zs = 3 : [] }
   filter cond (x : y : z : zs) where cond y = (y > x) && (y > z)
= { substitute }
  filter cond (1 : 2 : 85 : 3 : []) where cond y = (y > 1) && (y > 85)

Can you see at this point why your function won’t do what you expected?

The filter will only keep elements that are both greater than 1 and greater than 85, which no elements of your list are.

Your localMaxima function is not recursive, so the x and z variables used in cond will always have the same value, in this case 1 and 85. The actual traversal of the list happens inside the filter function, but that function doesn’t know anything about x and z, it just uses cond on each element to see which elements it should keep.

1 Like
#3

Thank you very much for the explanation, it’s clear now. It seems to me that filter function is not the best way to proceed here, I made this:

localMaxima :: [Int] -> [Int]
localMaxima [] = []
localMaxima [a] = []
localMaxima [a, b] = []
localMaxima (x:y:z:xs)
    | (y > x) && (y > z) = y : localMaxima (y:z:xs)
    | otherwise = localMaxima (y:z:xs)

which works, I just wanted to play around with filter

#4

You can write an implementation with filter, but you first have to combine each element with the elements to the left and to the right of it. You can do that like this:

localMaxima xs = map getMiddle (filter isLocalMaximum (triples xs))
  where
    triples xs = zip3 xs (tail xs) (tail (tail xs))
    isLocalMaximum (x, y, z) = y > x && y > z
    getMiddle (_, y, _) = y

That zip3 xs (tail xs) (tail (tail xs)) is a really common trick for cases like this, although usually you just need two adjacent elements in which case you would write zip xs (tail xs). There is an explanation how that works on stackoverflow.

2 Likes