CODEWITHSUNDEEP
listfunctionloopsfunctional-programmingocaml
Ugabuga
Ugabuga

Reputation: 29

How to apply a function in an iterable list

so I am new to OCaml and im having some trouble with lists. What I have is a List of chars as follows:

let letters = [a;b;c;d]

I would like to know how can I iterate the list and apply a fuction that takes as arguments every possible combination of two chars on the list (do_someting char1 char2), for example: a and b (do_something a b), a and c .... d and b, d and c; never repeating the same element (a and a or c and c should not happen).

Upvotes: 1

Views: 398

Answers (2)

Chris
Chris

Reputation: 36581

As an addendum to Silvio's answer, for large lists, we don't need to actually generate the entire list in memory and then iterate over it. Instead we can create a sequence of ordered pairs.

In order to do this, we need to keep track of three things:

  • The current prefix.
  • The rest of the list after that prefix.
  • The rest of the list after the prefix again so that we can update the first argument and still have it when we iterate to the end of that list.
let rec ordered_pairs_seq lst () =
  let rec aux pre cur_lst lst () =
    match cur_lst with
    | [] -> ordered_pairs_seq lst ()
    | x::xs -> Seq.Cons ((pre, x), aux pre xs lst)
  in
  match lst with
  | [] -> Seq.Nil
  | x::xs -> aux x xs xs ()

Then using this:

# let print_tuple (a, b) =
    Printf.printf "(%d, %d)\n" a b
  in
  pairs_seq [1; 2; 3; 4; 5]
  |> Seq.iter print_tuple;;
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 3)
(2, 4)
(2, 5)
(3, 4)
(3, 5)
(4, 5)
- : unit = ()

Of course, if you need the whole list:

# pairs_seq [1; 2; 3; 4; 5] 
  |> List.of_seq;;
- : (int * int) list =
[(1, 2); (1, 3); (1, 4); (1, 5); (2, 3); (2, 4); (2, 5); 
 (3, 4); (3, 5); (4, 5)]

Upvotes: 0

Silvio Mayolo
Silvio Mayolo

Reputation: 70277

OCaml is a functional language, so we want to try to break down the procedure into as many functional pieces as we can.

Step 1 is "take a list of things and produce all combinations". We don't care what happens afterward; we just want to know all such combinations. If you want each combination to appear only once (i.e. (a, b) will appear but (b, a) will not, in your example), then a simple recursive definition will suffice.

let rec ordered_pairs xs =
  match xs with
  | [] -> []
  | (x :: xs) -> List.append (List.map (fun y -> (x, y)) xs) (ordered_pairs xs)

If you want the reversed duplicates ((a, b) and (b, a)), then we can add them in at the end.

let swap (x, y) = (y, x)

let all_ordered_pairs xs =
  let p = ordered_pairs xs in
  List.append p (List.map swap p)

Now we have a list of all of the tuples. What happens next depends on what kind of result you want. In all likelihood, you're looking at something from the built-in List module. If you want to apply the function to each pair for the side effects, List.iter does the trick. If you want to accumulate the results into a new list, List.map will do it. If you want to apply some operation to combine the results (say, each function returns a number and you want the sum of the numbers), then List.map followed by List.fold_left (or the composite List.fold_left_map) will do.

Of course, if you're just starting out, it can be instructive to write these List functions yourself. Every one of them is a simple one- or two- line recursive definition and is very instructive to write on your own.

Upvotes: 4

Related Questions