哪個基於樹的字典是最容易實現的功能？

Question

我正在尋找一個容易在Haskell中實現的基於樹的字典數據結構。

你有實施AVL樹或RB樹的經驗嗎？我也在考慮splay樹，但沒有看到如何使用不可變數據來實現它們。

Answer 1

紅黑樹在功能性語言中很容易實現，因爲您不需要花費精力嘗試削減一些分配，並且the usual description of algorithms非常適合模式匹配。參見Okasaki，Red-Black Trees in a Functional Setting。實際上，他的是thesis的修訂和擴展版本，是許多純功能數據結構的絕佳參考。