Takeover of AvlTree and COrdering

Announcements
1

I’d like to take over Hackage packages COrdering: An algebraic data type similar to Prelude Ordering. and AvlTree: Balanced binary trees using the AVL algorithm.. Last uploads were in 2008. Both packages fail to compile with modern GHCs; my intention is to bring them back to life.

There are no maintainer contacts and no source code repository linked, so I cannot reach out to the maintainer to offer my services.

9 Likes
2

This is great to hear!

I made use of these packages a few years ago and forked it to get it to compile with modern GHCs.
My code is here:

3 Likes
3

Since the only package depending on these is gmap (acme-everything doesn’t count), also untouched in almost 20 years, why go through a package takeover instead of forks with new names?

2 Likes
4

I’m in no hurry, so why waste more package names instead of recycling existing ones?.. It seems reasonable to have a working implementation of AVL trees in a package named AvlTree, and I hardly see a public benefit in leaving it unmaintained forever and forking as AvlTree-new, AvlTrees or avl-tree — it will only cause more confusion and ambiguity for users.

15 Likes
5

I’ve pushed new releases of both COrdering: An algebraic data type similar to Prelude Ordering. and AvlTree: Balanced binary trees using the AVL algorithm., making them compile with modern GHCs.

That said, the interface of AVL tree is very much from 2004 and does not follow any current conventions. The library is designed to represent both ordered and unordered trees: in the latter case you essentially have an efficient implementation of double-ended queue, much like Data.Sequence. And since unordered trees has no need to evaluate their elements, the library does not enforce WHNF, meaning that there is no bang in the definition data AVL. It’s probably not a terribly big deal, given that polymorphic types won’t be unpacked even if defined as strict, but requires strict discipline to avoid accidental thunks.

Another problem is that the same structure is used to implement both sets and maps, and in the latter case one is supposed to use a tuple as an element and some COrdering-based contraption to search keys and update values. This is unergonomic and bad for performance, of course.

I guess the next step is to write a wrapper for representing sets as AVL trees and benchmark if it’s even comparable with Data.Set.

3 Likes