CODEWITHSUNDEEP
haskell
Allemis
Allemis

Reputation: 57

Haskell - MinMax using foldr

I am looking for a Haskell function that takes a list as an argument and returns a tuple (min, max), where min is the minimal value of the list and max is the maximal value.

I already have this: 

maxMinFold :: Ord a => [a] -> (a, a)
maxMinFold list = foldr (\x (tailMin, tailMax) -> (min x tailMin) (max x tailMax)) -- missing part

Could you help me what to add to the missing part? (or tell me what I am doing wrong)

Thanks a lot

Upvotes: 1

Views: 4136

Answers (4)

Simon H
Simon H

Reputation: 21005

You take the head and use that as the fist min and max and then fold over the tail.

maxMinFold :: Ord a => [a] -> (a, a)
maxMinFold (x:xs) = foldr (\x (tailMin, tailMax) -> (min x tailMin, max x tailMax)) (x,x) xs

As regards your answer, your fold function is not returning the right type.

Note that 

foldr :: (a -> b **-> b**) -> b -> [a] -> b

In particular you need to be returning a b, which is a tuple in your case

Upvotes: 5

James Brock
James Brock

Reputation: 3426

It would be nice if the minMax function returned Nothing in the case of an empty list. Here is a version which does that.

import Control.Arrow
import Data.Maybe
import Data.Foldable

minMax :: (Ord a) => [a] -> Maybe (a,a)
minMax = foldl' (flip $ \ x -> Just . maybe (x,x) (min x *** max x)) Nothing

This uses foldl' instead of foldr.

Upvotes: 0

dfeuer
dfeuer

Reputation: 48591

To do this efficiently with foldr,

data NEList a = NEList a [a]
-- deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)

minMax :: Ord a => NEList -> (a, a)
minMax (NEList x0 xs) = foldr go (,) xs x0 x0 where
  go x r mn mx
    | x < mn = r x mx
    | mx < x = r mn x
    | otherwise = r mn mx

Another, similar, approach:

minMaxM :: Ord a => [a] -> Maybe (a, a)
minMaxM xs = foldr go id xs Nothing where
  go x r Nothing = r (Just (x, x))
  go x r mnmx@(Just (mn, mx))
    | x < mn = r (Just (x, mx))
    | mx < x = r (Just (mn, x))
    | otherwise = r mnmx

Upvotes: 1

Christoph W.
Christoph W.

Reputation: 1024

Since you always have to traverse the whole list to find the minimum and the maximum here is the solution with foldl:

maxMinList :: Ord a => [a] -> (a,a)
maxMinList (x:xs) = foldl (\(l,h) y -> (min l y, max h y)) (x,x) xs

Upvotes: 2

Related Questions