Both critbit and qp tries are wonderful. I have pure-functional implementations of the central critbit algorithms in OCaml (https://github.com/tonyg/ml-critbit

Both critbit and qp tries are wonderful. I have pure-functional implementations of the central critbit algorithms in OCaml (https://github.com/tonyg/ml-critbit/blob/master/critbit.ml https://github.com/tonyg/ml-critbit/blob/master/critbit.ml) and Typed Racket (https://github.com/tonyg/racket-critbit/blob/master/critbit.rkt https://github.com/tonyg/racket-critbit/blob/master/critbit....). I was surprised to find the OCaml implementation is competitive speedwise with the built-in Set implementation over strings.