How to do an addition on a list with a condition?

Question

I have a university course about functional programming, where I use SML. As a preparation for the exam, I am working on some of the older exam sets without solutions.

One of the only questions I really have problems with is the following question using foldl:

Consider the program skeleton: fun addGt k xs = List.foldl (...) ... xs; Fill in the two missing pieces (represented by the dots ...), so that addGt k xs is the sum of those elements in xs, which are greater than k. For example, addGt 4 [1, 5, 2, 7, 4, 8] = 5 + 7 + 8 = 20

I am sure this is really easy, but I have a very hard time understanding the foldl and foldr functions.

What I have now is the following (which seems to be very wrong if you ask my compiler!):

fun addGt(k,xs) = List.foldl ( fn x => if x > k then op+ else 0) 0 xs;

I would really appreciate some help with this question, and maybe a very short comment which would cast some light on the foldl and foldr functions!

Solution 1

A solution that I just though of is the following:

fun addGt(k, xs) = List.foldl (fn (x, y) => if x >= 5  then x + y else y) 0 xs;

But let me explain. First of all check the type of the List.foldl function, it's:

('a * 'b -> 'b) -> 'b -> 'a list -> 'b

So List.foldl is a curried function that takes as first parameter another function of type ('a * 'b -> 'b). You used (fn x => if x > k then op+ else 0) which has type int -> int. You should instead provide List.foldl with a function that takes a tuple of type int * int and returns an int, so something like this: (fn (x, y) => do stuff). That's why your code didn't compile, you passed a wrong type of function in foldl.

Now you can think of foldl this way:

foldl f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_n, f(x_(n - 1), ..., f(x2, f(x1, b)) ...)) where f is a function of type ('a * 'b -> 'b), b is something of type 'b and the list [x_1, x_2, ..., x_(n - 1), x_n] is of type 'a list.

And similar for foldr you can think it in this way:

foldr f b [x_1, x_2, ..., x_(n - 1), x_n] = f(x_1, f(x_2, ..., f(x_(n - 1), f(x_ n, b))

Solution 2

If you call foldl f s ls on a list, ls = [x1, x2, ..., xn], then you get the result:

f(xn, ... f(x2, f(x1, s)))

That is, it starts by finding

a1 = f(x1, s)

Then

a2 = f(x2, a1)

and so on, until it's through the list.

When it's done, it returns an.

You can think of the a-values as being a sort of accumulator, that is, ai is the result as it would be if the list was only [x1, x2, ..., xi] (or rather, the first i elements of the list).

Your function will usually have the form:

fn (x, a) => ...

What you then need to do is think: Okay, if I have the next element in the list, x(i+1), and the value ai, which is the result for the list [x1, x2, ..., xi], what do I need to do to find the value a(i+1), which is the result for the list [x1, x2, ..., xi, x(i+1)].

s can be thought of as the value given to the empty list.

foldr works the same way, only you start from the back of the list instead of from the front.

Comments

[Lars Holdgaard]

Thanks a lot for the explanation and answer!:-)

[Alex Reinking]

I assume you meant if x >= k?