How can I solve this Ocaml dictionary problem?

Question

I have to write a function that has as parameters a dictionary and a character. The dictionary is string to string and you should look at it as a function. For example f("a")="b" in ("a", "b"). The function returns a max number for which f^number(character) is defined and an exception if f(character) cycles at infinity.

so if I have for eg this dictionary [("a", "b");("b", "c");("d", "e");("e", "f");("f", "e")] my function appelead with this dictionary and charcater 'a' will give the result 2(a goes in b, b goes is c and it stops); for 'x' it will give 0 beacuse there's no such key; for 'b' the result will be 1(b goes in c and stops); for 'd' it will raise an exception(d goes in e, e goes in f, f goes in e and returns in e so infinite cycle); same exception for 'e' or 'f'

module MS = Map.Make(String);; let d = MS.add "a" "b" (MS.add "b" "c" (MS.add "d" "e" (MS.add "e" "f" (MS.add "f" "e" MS.empty))));; let f d c =

I just created the dictionary because I don't have any idea how could I implement this problem, but I think I need MS.Fold function for going through the dictionary.

Jeffrey Scofield Jeffrey Scofield · Accepted Answer · 2020-11-08T17:11:52

The purpose of a fold is to "visit" all the elements of a structure, while accumulating some desired result. Your goal isn't to visit all the elements of your dictionary (which secretly is a graph). So a fold probably isn't what you want.

I'd say your main problem is in detecting cycles so you can raise an exception. To do this you need to track the places you've been. Then you raise the exception when you come to a place for the second time.

Otherwise this is a standard graph traversal problem, I'd say. You can solve it with a recursive function that visits nodes (i.e., looks up strings in the dictionary) until it gets a resolution. A resolution is a string that isn't in the dictionary, or a visit to a string that has already been visited.

Update

OK, I'll write some code that shows how to move through the dictionary. This function returns a string that is the concatenation of the first 10 strings it encounters. If it reaches a dead end before 10 it returns what it has seen so far. It uses your module MS.

 let what_i_saw dict str =
     let rec look sofar n s =
         if n <= 0 then
             sofar
         else
             match MS.find_opt s dict with
             | None -> sofar
             | Some s2 -> look (sofar ^ s2) (n - 1) s2
     in
     look str 9 str

Here's how it looks when you call the function:

# what_i_saw d "d";;
- : MS.key = "defefefefe"
# what_i_saw d "a";;
- : MS.key = "abc"

By the way, you say your function takes a character but your dictionary has keys that are strings. Strings and characters aren't the same thing in OCaml. I'm using strings everywhere in this example.

How can I solve this Ocaml dictionary problem?

1 Answers