Understanding foldl in ML

Question

I need to write a function that takes a list of strings and finds the largest string in the list. The catch is it needs to iterate through the list using List.foldl and cannot use recursive calls except for those in the library function of List,foldl.

I wrote

fun longest_string1(xs)= 
case xs of 
[] => ""  
| x::xs' => List.foldl((fn (s,x) => if String.size s > String.size x then s else x) "" x,)

with my interpretation being as follows:

-take in xs, if xs is empty return an empty string

-otherwise for the first item of xs call List.foldl

-List.foldl passes in an anonymous function that checks the length of s, which should represent the accumulator against the head item of the list.

-Set the initial accumulator to be the empty string and the initial compare value to be the head of the initial list passed in by the higher order function

However, it does not type check.

I think my issue is in the understanding of the List.foldl function itself and how exactly it reads in its parameters. Can someone please provide some clarification?

Sabella

Answer 1

So, for the code you posted:

1. You don't need the case for the empty list. foldl will take care of that for you. Just pass xs to foldl instead of x.
2. foldl is curried, so you shouldn't have parentheses around the parameters.

Other than that, it actually looks correct. Anyway, if you're still not sure how foldl works, here's a really long and thorough explanation ;)

Okay, let's start with List.foldl.

val foldl : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

So, there are three parameters. One is a function which we'll worry about later, the second is a value of the same type as the return type, and the last is the list.

So, let's take a simple example - say we have a list of ints, and we want to sum all the numbers. We could do this:

fun sum [] = 0
  | sum (x::xs) = x + sum xs

Or, we can use foldl (I'll write foldl instead of List.foldl from now, because I'm lazy).

So, we know that the list is the third parameter. The second should be some sort of starting value, or accumulator, something that would make sense if the list was empty. For a sum, that would be 0.

The first parameter is a function, and this is the tricky part. The type is:

fn : 'a * 'b -> 'b

Okay, so 'a is also the type of the elements in the list, so it makes sense if this is an item from the list. 'b is the type of the starting value and the return value.

What actually happens is that foldl calls the function with the first element in the list, and the accumulator. It then calls itself with the result as the new accumulator, and the rest of the list. So if we do this:

foldl foo 0 [1,2,3]

It'll do

foo (1,0)

And then

foldl foo (foo (1,0)) [2,3]

And so on.

So for summing a list, we'll make the following function:

fn (x,acc) => x + acc

So we can do this:

fun sum xs = foldl (fn (x,acc) => x + acc) 0 xs

Or, even simpler

val sum = foldl op+ 0

(op+ does the same as the anonymous function I used earlier)

Let's walk through it with the list [1,2,3]

foldl op+ 0 [1,2,3]
foldl op+ (op+ (1,0)) [2,3] -> foldl op+ 1 [2,3]
foldl op+ (op+ (2,1)) [3]   -> foldl op+ 3 [3]
foldl op+ (op+ (3,3)) []    -> foldl op+ 6 []
6

Heterosporous