Using fold in SML

Question

I am trying to find out smlnj at the moment and I am having problems with the fold function.

What I'm trying to do is write a function, choose that uses a folding pattern and accepts the function and list. It will take a list of the list in the function to determine if it will add this element to the list. Here is an example of what I mean.

select (fn x => x mod 2 = 0) [1,2,3,4,5,6,7,8,9,10]; val it = [2,4,6,8,10] : int list 

So here is what I still have ...

  fun select fl = foldl (fn (x,y) => if (f(x)) then x else 0) 0 l; 

This is obviously not working properly. It just returns 10. I'm sure I need to use op :: somehow to make this work, but I can't figure it out. I thought it should look something like this ...

  fun select fl = foldl (fn (x,y) => if (f(x)) then op:: else []) [] l; 

But that does not work. Any help would be greatly appreciated. Thanks!

Answer 1

You're close The only problems are if / else cases in the function you pass to fold .

Remember that in your fn (x,y) , x is the list item you are considering, and y is the result of folding the rest of the list. If f(x) fails, you want to exclude x from the result, so you just pass y . If f(x) succeeds, you want to include x in your result so that you return y@ [x] .

Note that it is best to avoid using the append ( y@ [x] ) operator, where you can, since this is a linear time operation, while adding ( x::y ) is constant. Of course, substituting one for the other in this case, you will build your list back. You can get around this by folding back as well, i.e. using foldr instead of foldl .

Answer 2

What you are implementing already exists. It is called filter .

 - List.filter (fn x => x mod 2 = 0) [1,2,3,4,5,6,7,8,9,10]; val it = [2,4,6,8,10] : int list 

Your attempt in the second code example is pretty close. I can point out a few questions:

• op:: is an operator that is a function. You probably don't want to return a function. Instead, you probably want to use the operator to create a list from the head element and the rest of the list, for example: x :: y

• Otherwise, you are currently returning an empty list and throwing away everything that has been accumulated in y . You probably don't want to do this.

• Think about whether the left or right bend will be most suitable for your output.