recursionpattern-matchingocaml

# How to divide a list of characters (that represents a word) into all possible (prefix, single_letter, suffix) triplets in CAML?

I defined a type "word" as a list of characters. I am trying to write a recursive function "divide_word" that takes one "word" as an argument and returns a list of triplets of all possible (prefix, single_letter, suffix) combinations of the "word".

Example of execution in OCAML:

``````assert( divide_word ['c';'o';'d';'e'] = [  ([],'c',['o';'d';'e']) ; (['c'],'o',['d';'e']) ; (['c','o'],'d',['e']) ; (['c','o','d'],'e',[])  ];;
``````

I've tried writing the function, but it only returns the last possible combination. I know that I have to find a way to return an actual list and not just a single triplet, I tried to concatenate and also to write a separate function.

This is the code that I've written:

``````type word = char list;;

let rec divide_word (w:word) : (word*char*word) list =
match w with
| [] -> []
| h::[] -> [([], h, [])]
| h::t -> List.map (fun (fir, sec, th) -> (h::fir, sec, th)) (divide_word t);;
``````

help! c:

Solution

• You're almost there. In the last case of the pattern matching, you compute correctly all triplets where any character from the second to the last is used as separator, but you also have to add to that list the case where the first character (i.e. `h`) is the separator (hence the prefix empty and the suffix `t`).

Once this is done, you will probably notice that the case `h::[]` is in fact a particular case of `h::t`, thus need not to be treated apart in its own pattern.