Hi,<br><br>I&#39;m trying to implement a fast kd-tree in Haskell.&nbsp; <a href="http://en.wikipedia.org/wiki/Kd-tree">http://en.wikipedia.org/wiki/Kd-tree</a>&nbsp; It&#39;s a binary tree representing space partitions.<br><br>One of the fastest ways to build kd-trees is outlined in this paper: 
<a href="http://www.cgg.cvut.cz/~havran/ARTICLES/ingo06rtKdtree.pdf">http://www.cgg.cvut.cz/~havran/ARTICLES/ingo06rtKdtree.pdf</a>&nbsp; (I&#39;m trying to implement Algorithm 5 on page 5 and the steps outlined in section 4.3.1
.)<br><br>I&#39;ll try to outline a simplified analogous algorithm to demonstrate my problem.&nbsp; It&#39;s all about classifying which children should go in a left or right branch using heuristics.<br><br>Say I want to put the words &#39;foo&#39;, &#39;bar&#39; and &#39;baz&#39; into a binary tree.&nbsp; The heuristic requires I split the words into letters and sort them:
<br>&#39;aabbfoorz&#39;.&nbsp; The heuristic then may decide, based on the sorted letters, that &#39;bar&#39; and &#39;foo&#39; should go in the left child and &#39;baz&#39; goes in the right.&nbsp; Typically we&#39;d then simply recurse and for example, the left child&#39;s words would be re-sorted into &#39;abfoor&#39; and the heuristic is reapplied.
<br><br>If we assume that sorting is relatively expensive, we can avoid the re-sort for the children by unmerging the parent&#39;s sorted list of letters.&nbsp; Two sublists of a sorted list should already be sorted.&nbsp; If we know which word each letter belongs to it would be more efficient to tag the letters with &#39;left&#39; or &#39;right&#39; as the words are classified.&nbsp; Then we can iterate down the sorted letter list and&nbsp; produce new sorted sublists rather simply.
<br><br>So it&#39;s not actually that complicated, and I can imagine exactly how it could be done in C but I really don&#39;t know how to approach this in Haskell.&nbsp; The problem I&#39;m having is how to keep a map between the words and its letters (which in the real problem is a map between a list of vectors and 6 tuples containing Doubles and enumerations) while keeping in mind you can&#39;t just map any letter to a word, but specific letters.&nbsp; 
e.g., the &#39;b&#39;s in the example must remember specifically whether they belong to &#39;bar&#39; or &#39;baz&#39;.<br><br>Thanks for any insights,<br>Toby.<br><br>