How to do an addition on a list with a condition?
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!
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))
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.
精彩评论