(Invalid_argument "index out of bounds") while encoding a word to a Morse code

Question

Bonjour.I am struggling with the function code_word. The purpose of this function is to take a message of type string and the Morse alphabet itself on the input, and it should return an encoded word of the same type on the output. For instance:

code_mot: string->(char * string)list -> string 
code_word "SOS" alphabet;;
-: string list = ["... --- ..."]

PS: Each encoded letter of the word have to be separated by the space.

I created a function (as demonstrated below), however each time I pass it an argument, I always get an error:

Exception: (Invalid_argument "index out of bounds")

To be honest I have tried all possible combinations to solve this problem. Nonetheless, I didn't find a suitable solution.Due to this I would like to ask for help: What is the source of an error and how can I fix it ?

let alphabet =
  [ ('A', "._" ); ('B', "_..." ); ('C', "_._.") ;
    ('D', "_.." ); ('E', "." ); ('F', ".._." );
    ('G', "__." ); ('H', "...." );( 'I', ".." );
    ('J', ".___" ); ('K', "_._" ); ('L', "._.." );
    ('M', "__" );  ('N', "_." ); ('O', "___" );
    ('P', ".__."); ( 'Q', "__._" );( 'R', "._.") ;
    ('S', "..." ); ('T', "_" ); ('U', ".._" );
    ('V', "..._" ); ('W', ".__" ); ('X', "_.._") ;
    ('Y', "_.__" ); ('Z', "__.." )
   ];;

let code_word s alpha = 
  let rec cw_aux s i alpha word = 
    match alpha with 
    | [] -> word
    | (cha, l)::r -> 
      if s.[i] = cha then 
        cw_aux s (i+1) alpha (l^" "^word)
      else
        cw_aux s (i+1) r word
  in
  cw_aux s 0 alpha " " ;

Answer 1

Your code needs to iterate over two things: the incoming string, and the list of morse codes. But you have only one termination condition, the end of the morse code list. In other words, you're not checking anywhere for when you reach the end of the string. Thus your recursive calls with (i + 1) will eventually reach past the end of the string and cause your error.

It seems to me that you also have the problem that you have merged your two searches. It's not true that you want to move along to the next character in the string when you don't find a code for the current char of the string.

In other words, this call looks wrong to me:

cw_aux s (i+1) r word

It's not the case that you want to move along to the next character of the incoming string here. You want to find the correct code for the current character first.

Answer 2

This is a great place to use a Map to map characters to Morse codes. Then it's just a matter of mapping each character in your string to that character's binding in the map. By letting library functions handle looping over the string, the index error cannot happen.

You could just use List.assoc with your list, but that's O(n) while lookups in a map are O(log n). For simple purposes, there's likely little practical difference, but for larger strings, it will matter.

module CMap = Map.Make (Char)

Then, using your list of tuples:

let alphabet =
  [ ('A', "._" ); ('B', "_..." ); ('C', "_._.");
    ('D', "_.." ); ('E', "." ); ('F', ".._." );
    ('G', "__." ); ('H', "...." );( 'I', ".." );
    ('J', ".___" ); ('K', "_._" ); ('L', "._.." );
    ('M', "__" );  ('N', "_." ); ('O', "___" );
    ('P', ".__."); ( 'Q', "__._" );( 'R', "._.");
    ('S', "..." ); ('T', "_" ); ('U', ".._" );
    ('V', "..._" ); ('W', ".__" ); ('X', "_.._");
    ('Y', "_.__" ); ('Z', "__.." )
   ]

We can create a map from the mappings you've created with a bit of help from the Seq (sequence) module.

let map = alphabet |> List.to_seq |> CMap.of_seq

(Note that the |> operator allows us to write the above, rather than CMap.of_seq (List.to_seq alphabet). This becomes more helpful in the following code.)

Now, really we just need to map an input string to the Morse code for each character. To do that we'll turn a string int a sequence, map, and then convert to a list.

"Hello" 
|> String.to_seq 
|> Seq.map Char.uppercase_ascii
|> Seq.map (fun ch -> CMap.find ch map) 
|> List.of_seq

Result:

["...."; "."; "._.."; "._.."; "___"]

You would now simply need to join these together into a single string.

You might still received a Not_found exception if you try to encode a string which includes characters for which there are not Morse code mappings. You'd either want to handle this exeception, or add more Morse code bindings to your map.