Understanding Folding in ML

Question

I need to write a function that takes a list of strings and finds the largest string in the list. The trap requires iterating through the list with List.foldl and cannot use recursive calls, except for those that are in the library function 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 was the following:

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

-other for the first xs List.foldl call item

-List.foldl goes into an anonymous function that checks the length s, which should represent the battery against the list header element.

-Set the original battery as an empty string, and the initial comparison value should be the head of the initial list passed by a higher order function

However, it does not enter validation.

I think that my problem is understanding the List.foldl function itself and the accuracy of its reading in its parameters. Can someone please clarify?

Answer 1

So for the code you sent:

• You do not need a case for an empty list. foldl will take care of this for you. Just pass xs to foldl instead of x.
• foldl is curried, so you should not have parentheses around the parameters.

In addition, it looks correct. Anyway, if you are still not sure how the dump works, here is a really long and complete explanation;)

Ok, start with List.foldl.

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

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

So, let's take a simple example - let's 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 (now I will write foldl instead of List.foldl because I'm lazy).

So, we know that the list is the third parameter. The second should be a kind of starting value or battery, which would make sense if the list was empty. For the amount, it will be 0.

The first parameter is a function, and this is the hard part. Type of:

 fn : 'a * 'b -> 'b 

Ok, that's why 'a is also a type of items in a list, so it makes sense if it's an item from a list. 'b is the type of the initial value and the return value.

What actually happens is that foldl calls a function with the first item in the list and the battery. He then calls himself the result as a new drive and the rest of the list. Therefore, if we do this:

 foldl foo 0 [1,2,3] 

It will do

 foo (1,0) 

And then

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

And so on.

So, to summarize the list, we will 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 easier

 val sum = foldl op+ 0 

( op+ does the same thing as the previously anonymous function)

Skip the list through it [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 

Answer 2

The following code is the solution to your problem:

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