Standard ML (using MoscowML) Whats wrong with this function? (filter)

Question

This is part of a homework assignment so my goal is to understand why this is wrong. As I mentioned before I'm using Moscow ML.

fun filter pred = let
 fun f ([], a) = []
 | f ([], a) = a
 |   f (e::L, a) = if pred e then (f L (e::a) ) else (f L a)

in
 f
end

The error I get is:

| f (e::L, a) = if pred e then (f L (e::a) ) else (f L a)
                                  ^
Type clash: expression of type 
'a list cannot have type
'a list * 'b list

I have been reading up on documentation, and it really hasn't helped. What I really don't get is where 'b list is coming from. In our assignment we have to use an accumulator with tail recursion. I believe where my error is is how filter calls the function f. Filter takes the predicate as an argument and f should take the list and accumulator which is initially the empty list.

I've tried calling f like: f L [], But in other examples we didn't actually have to call f with its argument and it was somehow passed automatically.

Anyway, any help understanding where my mistake is and guidance on how to fix the problem would be greatly appreciated.

-aitee

(also if anyone could give me any tips on decoding the type expression errors that could also be very beneficial.)

Answer 1

f is a function of type 'a list * 'a list -> 'a list, but you treat it like a function of type 'a list -> 'a list -> 'a list.

I.e. you need to call it as f (foo, bar) (passing it a tuple), instead of f foo bar.

Answer 2

You're confusing tupled versus curried function calls. Your definition of f demands a tuple, (a,b), but you're passing it arguments as f a b. Try replacing your recursive calls to f L ... with f (L,...) instead.

The type error is a little unhelpful, but it's basically saying that you're passing a list when it expects a 2-tuple of lists.

Answer 3

(f L (e::a)) would work only if f were a curried function, of type 'a list -> 'a list -> 'a list. You should be doing:

if pred e then (f (L, (e::a))) else (f (L,a))

Btw., SMLNJ complains of a redundant match (two f ([], a) clauses are given).