CODEWITHSUNDEEP
f#
coder4lyf
coder4lyf

Reputation: 927

writing my own version of List.filter in F#

I'm attempting to rewrite List.filter manually so far I have this:

let rec filter f = function
    |[] -> []
    |x::xs -> if f x = true then x @ filter f xs
              else filter f xs;;

Upvotes: 1

Views: 617

Answers (2)

Gene Belitski
Gene Belitski

Reputation: 10350

I'd add to the accepted answer that recognizing and applying functional patterns may be as important as mastery of recursion and pattern matching. And probably the first of such patterns is folding.

Implementing your task with folding takes a terse:

let filter p ls = List.foldBack (fun l acc -> if p l then l::acc else acc) ls []

Upvotes: 6

Petr
Petr

Reputation: 4280

Operator @ appends 2 lists so x in if ... then ... else expression is supposed to be of type list. You probably meant to use list cons operator ::. Also you don't need to compare the result of function f application to true.

let rec filter f = function
    |[] -> []
    |x::xs -> if f x then x :: filter f xs
              else filter f xs

[1;2;3;4;5;6;7;8;9] |> filter (fun x -> x % 2 = 0)

val it : int list = [2; 4; 6; 8]

Note: this function is not tail recursive so you'll get stack overflow exception with big lists.

Upvotes: 3

Related Questions