OCaml Beginner here.
I have a trie with signature
type ('k, 'v) trie = Trie of 'v option * (('k * ('k, 'v) trie) list)
I need the insert method below, but am clueless. What is the best approach to go about implementing this with OCaml(Standard libs are fine)? Should I recurse over the trie, or the array inside of it? If so how do I do it with OCaml?:
val insert : ('k, 'v) trie -> 'k list -> 'v -> ('k, 'v) trie
insert t ks v returns a new trie that is the same as t, but ks is mapped to v.
Here are examples of a tries with mappings:
(* maps ['a'] to 1 *)
Trie (None, ['a', Trie (Some 1, [])])
(* maps [] to 1, ['a'] to 2, ['a'; 'b'] to 3 and ['a'; 'c'] to 4 *)
Trie (Some 1, ['a', Trie (Some 2, ['b', Trie (Some 3, []); 'c', Trie (Some 4, [])])])
It doesn't make any sense to say "recurse over the trie," at least not to me.
An obvious opportunity for recursion is when there is an internal structure with the same type as the containing structure. Your definition of a trie, for example, has a list of (key, trie) pairs inside it. It would stand to reason that your recursion would involve picking the appropriate one of these internal pairs and making a recursive call involving its trie.
Update
Some answers to new comments/questions.
I'm going to assume you keep your list of pairs sorted by key. You definitely do need to test whether the key is already there or not. This is no different, in essence, from adding a new element to a sorted list.
(If you don't keep the list sorted, you need to check whether your key is there and if not add the new key to the beginning. It's not much different, in the big picture.)
OCaml lists are immutable, so you can't actually add an element to a list. What you do instead is return a new list that has all the old elements plus the new one. The old list is not changed in the process (being immutable, it can't be changed).
I don't want to just write your code for you. But here's a function that "adds" a new element to a sorted list.
let rec add_to_list l e =
match l with
| [] -> [e]
| h :: t -> if e < h then e :: l else h :: add_to_list t e