More/better two lists scanning?

Community
1

When scanning two lists i use :

val exists2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> bool

However if i want to exhibit one adequate pair what i need is :

val exists2_opt : ('a -> 'b -> bool) -> 'a list -> 'b list -> ('a,'b) option

Moreover what i want is actually to catch all adequate pairs so what i need is :

val filter2 : ('a -> 'b -> bool) -> 'a list -> 'b list -> ('a,'b) list

let rev_append_map_filter p f la lb =
   let rec loop l acc =
      match l with
      | [] -> acc
      | h::t ->
         if p h then loop t (f h::acc)
         else loop t acc
   in loop la lb

let rec filter2 p la lb =
   match la with
   | [] -> []
   | a::l -> rev_append_map_filter (p a) (fun b -> a,b) lb (filter2 p l lb)

:camel:

2

You can use List.fold_left2:

let filter2 p la lb =
  List.fold_left2 (fun acc a b -> if p a b then (a, b) :: acc else acc) [] la lb

(This will reverse the order of elements, you can List.rev or use List.fold_right2 instead as needed.)

Cheers,
Nicolas

3 Likes
3

Only my twisted mind could have use another way than List.fold_...2 :grinning_face_with_smiling_eyes:
edit: it isn’t the task at hand, i don’t want it to be positionnal.

4

Edit: I realize this wasn’t the task at hand.

An easy way to do this [something else] is to zip the lists first:

> let find_map2 f xs ys = List.find_map f (List.combine xs ys);;
val find_map2 : ('a * 'b -> 'c option) -> 'a list -> 'b list -> 'c option
> let filter2 f xs ys = List.filter_map f (List.combine xs ys);;
val filter2 : ('a * 'b -> 'c option) -> 'a list -> 'b list -> 'c list

The temporary list can be avoided with Seq:

> let find_map2 f xs ys = Seq.find_map f (Seq.zip (List.to_seq xs) (List.to_seq ys));;
val find_map2 : ('a * 'b -> 'c option) -> 'a list -> 'b list -> 'c option
> let filter2 f xs ys = List.of_seq (Seq.filter_map f (Seq.zip (List.to_seq xs) (List.to_seq ys)));;
val filter2 : ('a * 'b -> 'c option) -> 'a list -> 'b list -> 'c list
1 Like
5

It looks like you’re trying to find all the pairs (x,y) that satisfy p x y where x and y can occur anywhere in the lists, not just in corresponding positions. In other words, you want

filter2 (fun x y -> x < 2 && y > 20) [0; 1; 2; 3] [10; 20; 30; 40]

to return

[(0, 30); (0, 40); (1, 30); (1, 40)]

If so, then you could write your filter2 like this:

open ListLabels

let when_list c v = if c then [v] else []

let filter2 p l r =
  concat_map l ~f:(fun x ->
  concat_map r ~f:(fun y ->
  when_list (p x y) (x, y)))

and you could write exists2_opt similarly, like this:

let when_opt c v = if c then Some v else None

let exists2_opt p l r =
  find_map l ~f:(fun x ->
  find_map r ~f:(fun y ->
  when_opt (p x y) (x, y)))

or, if you prefer, you might use binding operators:

let ( let++ ) o f = List.find_map f o

let exists2_opt p l r =
  let++ x = l in
  let++ y = r in
  when_opt (p x y) (x, y)

let ( let** ) o f = List.concat_map f o

let filter2 p l r =
  let** x = l in
  let** y = r in
  when_list (p x y) (x, y)
2 Likes
6

It looks like you’re trying to find all the pairs (x,y) that satisfy p x y where x and y can occur anywhere in the lists, not just in corresponding positions.

You are right, i fooled myself, exists2_opt & filter2 are ill-named, it’s nothing positionnal like List.exists2. Same type but not same meanning ! exists_two & filter_two could be better names.