CODEWITHSUNDEEP
haskellfunctional-programming
Ahmed Fayed
Ahmed Fayed

Reputation: 141

Define min function using Foldr

I want to define min function to get minimum number on a list using Foldr function

min xs  = foldr (\ x y -> if x<y then x else y) xs

Although I understand the logic of Foldr for simple functions like below

sum     = foldr (+) 0

I get confused how to do it for function like min

Upvotes: 0

Views: 3525

Answers (2)

dfeuer
dfeuer

Reputation: 48591

min is best viewed as a left fold rather than a right fold. The trouble with the right fold approach is that no comparisons happen until the list has already been entirely traversed. If the list is generated lazily, this will lead to a lot of excess memory use. Even if it's not, it will likely lead to poor use of cache and general slowness. The rest of this answer is much less practical.

As http://www.haskell.org/haskellwiki/Foldl_as_foldr shows, it's actually possible to write foldl in terms of foldr:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a bs =
   foldr (\b g x -> g (f x b)) id bs a

This is not going to be such a great implementation in general, but recent developments in program transformation have actually made it work okay, apparently, although maybe not in an actual released compiler!

Then

foldl1 f (a:as) = foldl f a as
                = foldr (\b g x -> g (f x b)) id as a

Now write

min2 x y
  | x <= y = x
  | otherwise = y

Then

min = foldl1 min2

So we can write

min (a:as) = foldr (\b g x -> g (min2 x b)) id as a

and (on a bleeding edge research compiler) this is probably the best way to use foldr to implement min.

Upvotes: 1

ErikR
ErikR

Reputation: 52039

The type signature of foldr is:

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

In particular, foldr takes three arguments, so your definition for min is missing one value:

min xs  = foldr (\ x y -> if x<y then x else y) ??? xs

In the case of sum = foldr (+) 0, the argument 0 is the value of sum on the empty list.

Likewise, the missing argument ??? should be the value for min on the empty list. But does min [] even make any sense?

The way to resolve this is to realize that min should only be called on non-empty lists and write:

min [] = error "min called on an empty list"

min (a:as) = foldr (\x y -> if x < y then x else y) ??? as

To determine what ??? should be, just ask yourself: what should min (a:as) be when as = []?

Upvotes: 4

Related Questions