5
\$\begingroup\$

Please see this question for the general description.

Exercise 2: localMaxima :: [Integer] -> [Integer]

A local maximum of a list is an element of the list which is strictly greater than both the elements immediately before and after it

localMaxima :: [Integer] -> [Integer]
localMaxima l =
  let getMaxOf3 x y z | x < y && y > z = Just y
                          | otherwise = Nothing
      accumulate l2 acc = case l2 of
                           u:v:w:xs -> case (getMaxOf3 u v w) of
                                        Just q -> accumulate (v:w:xs) (q:acc)
                                        Nothing -> accumulate (v:w:xs) acc
                           otherwise -> []
  in reverse (accumulate l [])
\$\endgroup\$
3
\$\begingroup\$

The implementation can be much simpler. The main insight I can offer is to use map and filter instead of Maybe and writing your own accumulate. In addition,

  • Instead of writing case l2 of …, use pattern matching.
  • Look for library functions that you can take advantage of. (Here, I've used tails from Data.List.)
  • In keeping with the "wholemeal programming" goal, use higher-order functions instead of recursion.
  • Higher-order functions also let you use point-free style, which lowers your mini-golf score.

I suggest using where instead of let … in … because the former encourages top-down strategic thinking. You want to write a "one-liner", and add supporting details only if necessary.

import Data.List (tails)

localMaxima :: [Integer] -> [Integer]
localMaxima = map (!!1) . filter isLocalMax . tails
  where
    isLocalMax (a:b:c:_) = a < b && b > c
    isLocalMax _         = False

In addition to being shorter, this implementation is more maintainable. You can tell at a glance what map (!!1) . filter isLocalMax . tails does, but reverse (accumulate l []) is mysterious. Furthermore, because isLocalMax is not intertwined with accumulate, you can trace the execution by inspecting tails xs, then (filter isLocalMax . tails) xs, etc.

\$\endgroup\$
2
  • \$\begingroup\$ I couldn't tell at a glance what exactly your snippet computed :). As I commented in my first question: I wanted to avoid other modules than Prelude, so the tails function was not available. Maybe it's not the best way to learn all the low level stuff and then using the high level stuff. \$\endgroup\$
    – hasnoob
    Mar 28 '15 at 18:27
  • \$\begingroup\$ It's not hard to implement tails if needed. When programming, it's smart to think about ways to compose the solution from smaller reusable chunks. If the helper function already exists in a standard library, that's even better. It pays to familiarize yourself with the standard libraries, though, since those are functions that other programmers have deemed useful enough to include. \$\endgroup\$ Mar 28 '15 at 19:27
3
\$\begingroup\$

Traversing a list and accumulating a result naturally suggests an implementation using fold. For any given element, we either want to retain it, if it is greater than its neighbours, or else discard it, so fold should take a step function with a boolean guard. Since the endpoints can't be maxima, we can construct an intermediate list of triples using zip3 (which I'm inlining to save characters, per the problem spec):

localMaxima :: [Integer] -> [Integer]
localMaxima xs = foldr step [] $ zip3 xs (drop 1 xs) (drop 2 xs)
  where step (a,b,c) ys | a < b && b > c = b : ys
                        | otherwise      = ys
\$\endgroup\$
1
\$\begingroup\$

200_success's answer is spot on, but we can more closely cleave to the problem specification by making it explicit that you're determining maxima-ness by inspecting triples.

triples :: [a] -> [(a, a, a)]
triples x@(_:y@(_:z)) = zip3 x y z -- Credit to @Franky for a very slick `triples` implementation
triples _             = []

localMaxima :: (Ord a) => [a] -> [a]
localMaxima []                 = []
localMaxima [x]                = [x]
localMaxima [x, y] | x > y     = [x]
                   | y > x     = [y]
                   | otherwise = []
localMaxima xs                 = map second . filter isLocalMax . triples $ xs
    where
        isLocalMax (a, b, c) = b > a && b > c
        second (_, b, c) = b

The other thing I like about my answer is that you can use it to define a weird sort of version of maximum that ends up obeying the same "strictly greater" property. It's about as useful as a trap door on a lifeboat, but I like the name. :-D

globalLocalMaximum :: (Ord a) => [a] -> Maybe a
globalLocalMaximum = join . fmap listToMaybe . find singleton . iterate localMaxima
    where
        singleton :: [a] -> Bool
        singleton []  = True
        singleton [_] = True
        singleton _   = False

(I would also replace (!!1) in 200_success's answer with headBut = head . tail because that is maybe the greatest programming pun I have ever realized.)

\$\endgroup\$
4
  • \$\begingroup\$ As defined in the problem, an element can only be a local maximum if it has two neighbours. Therefore, your localMaxima [x] and localMaxima [x,y] cases are invalid — they should both evaluate to []. \$\endgroup\$ Mar 27 '15 at 5:49
  • \$\begingroup\$ I consider that a deficiency with the problem statement. ;-) \$\endgroup\$
    – bisserlis
    Mar 27 '15 at 6:08
  • \$\begingroup\$ remove recursion in first line of triples with triples x@(_:y@(_:z)) = zip3 x y z. \$\endgroup\$
    – Franky
    Mar 28 '15 at 7:26
  • \$\begingroup\$ Ooh, good call @Franky. That one slipped right by me! \$\endgroup\$
    – bisserlis
    Mar 28 '15 at 8:17
1
\$\begingroup\$

What about a really simple recursive function ?

localMaxima :: [Integer] -> [Integer]
localMaxima (x:y:z:xs) = if x < y && y > z then y:localMaxima (y:z:xs)
                                           else   localMaxima (y:z:xs)
localMaxima _ = []

It doesn't handle the "edges" though (if you want to consider the 5's in [5,2,5] as localMaxima).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.