id: 06105529
dt: a
an: 06105529
au: Straka, Milan
ti: Adams’ trees revisited. Correctness proof and efficient implementation.
so: Peña, Ricardo (ed.) et al., Trends in functional programming. 12th
    international symposium, TFP 2011, Madrid, Spain, May 16‒18, 2011.
    Revised selected papers. Berlin: Springer (ISBN 978-3-642-32036-1/pbk).
    Lecture Notes in Computer Science 7193, 130-145 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: data structures; balanced binary search trees; Haskell
ci: 
li: doi:10.1007/978-3-642-32037-8_9
ab: Summary: We present a correctness proof of Adams’ trees of bounded
    balance, which are used in Haskell to implement Data.Map and Data.Set.
    Our analysis includes the previously ignored join operation, and also
    guarantees trees with smaller depth than the original one. Because the
    Adams’ trees can be parametrized, we use benchmarking to find the
    best choice of parameters. Finally, a saving memory technique based on
    introducing additional data constructor is evaluated.
rv: