Finding a sub-trie by edge in OCaml - T9 predictive text implementation

I’m very new to OCaml and having a difficult time implementing a series of functions to build a T9 predictive text program. For example if my word is “Dog” - as an integer list would be [3;6;4]. I already have a pattern matching function to relate words to int lists. I’m using the data type trie to map numbers to the possible word outcomes possible:

type ('a, 'b) trie = Node of 'b list * ('a * ('a, 'b) trie) list

A trie with edges labelled with keys of type 'a and nodes labeled with lists of words of type 'b

I need to write a function with parameters trie and edge label that returns a trie at the end of the edge.

val trie_of_key : (’a, ’b) trie -> ’a -> (’a, ’b) trie = <fun>

How do I traverse the edges to arrive at a given node? Functional programming is still disorienting to me, so I am unsure of the recursive steps needed to arrive at the expected sub-trie.

It seems to me that if you don't want to modify the trie, functional programming is the same as regular old imperative programming. A lookup function that doesn't do any restructuring along the way should be pretty straightforward. Maybe you're just overthinking the problem?

It's hard to say more without seeing an example of what you've tried.

Update

Here's a lookup function I just wrote for a B-Tree structure. There are some similarities to the problem you're trying to solve, so maybe it will give you some ideas.

type ('a, 'b) btree = Node of ('a * 'b) list * ('a, 'b) btree list

let rec lookup bt k =
    match bt with
    | Node ([], _) -> raise Not_found
    | Node (keyvals, subtrees) ->
        let rec look kvs sts =
            match kvs with
            | [] ->
                lookup (List.hd sts) k (* Rightmost subtree *)
            | (hdk, hdv) :: tlkv ->
                if hdk = k then hdv
                else if hdk < k then look tlkv (List.tl sts)
                else lookup (List.hd sts) k
        in  
        look keyvals subtrees

I don't think the details are important, but if you're trying to understand the code carefully, it's based on the invariant that a node with no key/value pairs is a leaf node with no subtrees. Otherwise if there are n key/value pairs in the node, there are exactly n + 1 subtrees. (These subtrees can be empty.)