ML High-order function

Question

Write an ML High-order function philter(f,x,L) that takes a function f and an element x and returns the list of all those elements y on list L such that f(x,y) = true.

Philter:((a’ * a’)→bool * a’ * a’list)→a’list

My code

fun filter p [] = [] | filter p (x::xs) =
if p x
then
    x :: filter p xs
else
    filter p xs;

    filter (fn(x) => x<6) [6,3,0,1,8,5,9,3]; filter (fn(x) => x<6)

and i have diffrent val filter = fn : ('a -> bool) -> 'a list -> 'a list

any one can help me ?

Answer 1

Your function only takes a list and a function as argument where is the third argument e.g element x ?? As a consequence you check the condition p x and not p(x,y), from your description p should have type:

(a'* a') -> bool 

Here is my implementation:

fun filter (p :('a * 'a -> bool) , _ ,[]) = [] 
  | filter (p, x ,(y::ys))= if p (x,y) then y :: filter (p, x, ys)
                                   else filter (p, x, ys);

and here is a tail-recursive implementation:

fun filter2 (p : ('a * 'a -> bool), x, L)=
    let
        fun filter3 (p, _, [], L) = rev L 
          | filter3 (p, x, (y::ys), L) = if p (x,y) then filter3 (p, x, ys, (y::L))
                                                    else filter3 (p, x, ys, L);
     in
        filter3 (p, x, L, [])
      end 

Example (see types and results):

val filter = fn : ('a * 'a -> bool) * 'a * 'a list -> 'a list

val filter2 = fn : ('a * 'a -> bool) * 'a * 'a list -> 'a list

val it = () : unit
- filter ((fn(x,y) => x<y), 4,[6,3,0,1,8,5,9,3]);
val it = [6,8,5,9] : int list

- filter2 ((fn(x,y) => x<y), 4,[6,3,0,1,8,5,9,3]);
val it = [6,8,5,9] : int list