How do I filter a list without using List.filter in OCaml?-CodePudding

I have to write a function that, given two lists, it returns a list of the elements of the first one whose square is present in the second one (sry for my english). I can't do it recursively and i can't use List.filter. this is what i did:

let lst1= [1;2;3;4;5];;
let lst2= [9;25;10;4];;

let filquadi lst1 lst2 =
  let aux = [] in 
  List.map(fun x -> if List.mem (x*x) lst2 then x::aux else []) lst1;;

It works but it also prints [] when the number doesn't satisfy the if statement:

filquadi lst1 lst2 ;;
- : int list list = [[]; [2]; [3]; []; [5]]

how can I return a list of numbers instead of a list of a list of numbers?

- : int list = [2;3;5]

CodePudding user response：

You can use List.concat to put things together at the end:

List.concat (List.map ...)

As a side comment, aux isn't doing anything useful in your code. It's just a name for the empty list (since OCaml variables are immutable). It would probably be clearer just to use [x] instead of x :: aux.

As another side comment, this is a strange sounding assignment. Normally the reason to forbid use of functions from the List module is to encourage you to write your own recursive solution (which indeed is educational). I can't see offhand a reason to forbid the use of recursion, but it's interesting to combine functions from List in different ways.

CodePudding user response：

Your criteria don't say you can't use List.fold_left or List.rev, so...

let filter lst1 lst2 =
  List.fold_left 
    (fun init x -> 
       if List.mem (x * x) lst2 then x::init 
       else init) 
    [] lst1 
  |> List.rev

We start with an empty list, and as we fold over the first list, add the current element only if that element appears in the second list. Because this results in a list that's reversed from its original order, we then reverse that.

If you're not supposed to use recursion, this is technically cheating, because List.fold_left works recursively, but then so does basically anything working with lists. Reimplementing the List module's functions is going to involve a lot of recursion, as can be seen from reimplementing fold_left and filter.

let rec fold_left f init lst =
  match lst with
  | [] -> init
  | x::xs -> fold_left f (f init x) xs

let rec filter f lst =
  match lst with 
  | [] -> []
  | x::xs when f x -> x :: filter f xs
  | _::xs -> filter f xs