CODEWITHSUNDEEP
listrecursionocaml
Juan Bernal
Juan Bernal

Reputation: 13

Recursively comparing elements within a list in OCaml

I'm tasked with creating a list of m word portmanteaus with n letter overlap from a given list of words.

For example, a 2 word 2 letter overlap portmanteau would be: "collegenetics" made from "college" and "genetics". A 3 word 2 letter overlap could be "firegaluminum" made of "fire", "regal" and "aluminum".

I have written a function singleport with this syntax:

let singleport word1 word2 n = 
match suffix word1 n = prefix word2 n with
| false -> "No Port" 
| true -> word1 ^ (prefixless word2 n)

which identifies whether or not two words could be portmanteaus. However, I'm struggling to identify a way to run this recursively in order to compare two elements of a list, all while constructing a new list that records all the possible portmantaus.

I figured List.fold_left could be used because of the use of the accumulator, but I don't know how to implement it and I would greatly appreciate any advice. Thank you very much!

Upvotes: 0

Views: 1400

Answers (1)

ivg
ivg

Reputation: 35210

One of the approaches to attack this task is to split it into small understandable subtasks, and then try to merge them. This is the deductive approach.

Deductively

Applying the deductive method to your task, we can split it in the following way:

  1. create a list of consecutive pairs
  2. map the list for portmanteaus
  3. join the result

To create a list of pairs, you need to write the following function:

(** [pair_list xs] given the list [xs], produces a list of consecutive pairs. 
    Fails with an invalid argument, if the list has odd length. *)
val pair_list : 'a list -> ('a * 'a) list

With such a function, you can use map to transform each pair to a list of portmanteau, mapping a pair to an empty list, if it is impossible. E.g., given this function:

val portmanteau : (string * string) -> string list

And now we can join everything with List.concat:

let portmanteau_of_list xs = 
  List.map portmanteau (pair_list xs) |> List.concat

Inductively

Another approach is to move from the opposite direction, i.e., not from top to down, but from the bottom. So inductive reasoning about this task would be the following:

  1. portmanteaus of an empty list is an empty list,
  2. portmanteaus of the list of one element is an error
  3. portmanteaus of a list that is greater than two when the first two elements don't form a portmanteau is the portmanteaus of the rest elements of the list
  4. portmanteaus of a list greater than two when the first two elements form a portmanteau is the portmanteaus of these two elements plus portmanteaus of the rest elements of the list.

The same in OCaml (untested):

 let rec portmanteau_of_list = function
 | [] -> []
 | [_] -> failwith "odd list"
 | x :: y :: xs -> match portmanteau x y with
   | None -> portmanteau_of_list xs
   | Some p -> p :: portmanteau_of_list xs

Upvotes: 2

Related Questions