Define min function using Foldr

0
votes

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

2
haskellfunctional-programming
min is already defined in Data.Ord. Although it looks like you may want minimum from Data.List. Latices are semigroups and Maybe lifts semigroups to monoids, so you could also define a Min Monoid nad use Data.Foldable.foldMap. - Boyd Stephen Smith Jr.

2 Answers

3
votes

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 = []?

1
votes

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.