Which reminds me that some time ago I build a simple [kd-tree library in haskell](https://github.com/fhaust/kdtree).

The interesting part is that it's easy to construct a (lazy) list of all points ordered based on the distance to the query point. Other queries (n-nearest neighbours, points in radius) are just derived from that function and traverse only the first some elements of the list.