Какой древовидный словарь проще всего реализовать функционально?

Question

Я ищу древовидную структуру данных словаря, которую легко реализовать в Haskell.

Есть ли у вас опыт реализации деревьев AVL или деревьев RB? Я также думаю о деревьях сплайнов, но не понимаю, как их можно реализовать с использованием неизменяемых данных.

Answer 1

Красно-черные деревья очень легко реализовать на функциональном языке, так как вам не нужно тратить усилия, пытаясь сбрить несколько заданий, а обычное описание алгоритмов очень хорошо соответствует сопоставление с образцом См. Окасаки, Красно-черные деревья в функциональной обстановке . Фактически, его книга , которая является пересмотренной и расширенной версией его тезиса , является отличным справочным материалом для многих чисто функциональных структур данных.