I am trying to write a Standard ML function called 'select' that receives a list of integers and a function. The passed function receives an integer and returns a boolean (ex, fun isOdd 3 -> true). The function is to go through each integer in the list and append them to a new list if the given function returns true for that integer. So select [1,2,3,4,5] isOdd will return [1,3,5].
This is the code I've got:
fun select (l : int list, f:int -> bool) =
let val newlist : int list = []
fun recurse (x::xs) =
if f(x)
then newlist :: [x] :: recurse(xs)
else
newlist :: recurse(xs)
in
recurse(l : int list)
end
recurse doesn't have a case for the empty list, so it will fail when you reach the empty list.
Let's fix that:
fun select (l : int list, f:int -> bool) =
let val newlist : int list = []
fun recurse [] = []
| recurse (x::xs) =
if f(x)
then newlist :: [x] :: recurse(xs)
else
newlist :: recurse(xs)
in
recurse l
end
and test:
- select ([1,2,3,4], fn x => x mod 2 <> 0);
val it = [[],[1],[],[],[3],[]] : int list list
- select ([1], fn x => true);
val it = [[],[1]] : int list list
- select ([1], fn x => false);
val it = [[]] : int list list
That's no good – we want [1,3], [1], and [].
The type of your function is
val select = fn : int list * (int -> bool) -> int list list
The int list list result is wrong; it should be int list.
This happens because the first element of the result from recurse is an int list – the empty newlist – so the result must be an int list list.
Fixing the problem gives
fun select (l : int list, f:int -> bool) =
let fun recurse [] = []
| recurse (x::xs) =
if f x
then x :: recurse xs
else recurse xs
in
recurse l
end
Note that the type constraints are fairly pointless; if you remove them you will get a much more useful polymorphic function.