Using fold in SML

4
votes

I'm trying to learn smlnj at the moment and am having trouble with a fold function.

What I'm trying to do is write a function, select, that uses the folding pattern and takes in a function and a list. It will take the head of the list into the function to determine whether it will add that 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 have so far...

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

This obviously doesn't work correctly. It simply returns 10. I'm sure I need to use op:: somehow to get this to work, but I can't figure it out. My thought is that it should look something like this...

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

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

2
functional-programmingsmlsmlnj

2 Answers

4
votes

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

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

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

2
votes

What you're implementing already exists. It's 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 your second code sample is pretty close. There are several issues I might point out:

  • op:: is an operator, which 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 a head element and the rest of the list, like this: x :: y

  • In the else case, you are currently returning an empty list, and throwing away whatever was accumulated in y. You probably don't want to do that.

  • Think about whether left-fold or right-fold would be most suitable for your output