[MLton] fold on lists that need to be non-empty

Matthew Fluet fluet@cs.cornell.edu
Tue, 6 Jun 2006 10:04:46 -0400 (EDT)


> Have  you  ever  thought  about  the need for a function like fold, but which
> fails on empty lists?  The canonical example is something like max or min.

I'm pretty sure that I've run into such situations; certainly, I've needed 
max or min over a list of integers.

> The simpler case would be
>
>    fun ('e)
>       reduce ((h::t): 'e list, f: 'e * 'e -> 'e): 'e =
>          fold (t, h, f)

Haskell's standard library provides such functions, under the names:
   foldl1 :: (a -> a -> a) -> [a] -> a
   foldr1 :: (a -> a -> a) -> [a] -> a

> The more general version would need a separate function  to  take  the  first
> element of the list and convert it to the result type:
>
>    fun ('e, 's)
>       reduce ((h::t): 'e list, f: 'e -> 's, g: 'e * 's -> s'): 's =
>          fold (t, f h, g)

I don't see that Haskell has anything corresponding to this more general 
form.