{"comment":{"url":"https://api.github.com/repos/sweirich/dth/comments/13120699","html_url":"https://github.com/sweirich/dth/commit/b888942f33425a871d46105862683e8950d15b23#commitcomment-13120699","id":13120699,"user":{"login":"danieldietrich","id":743833,"avatar_url":"https://avatars.githubusercontent.com/u/743833?v=3","gravatar_id":"","url":"https://api.github.com/users/danieldietrich","html_url":"https://github.com/danieldietrich","followers_url":"https://api.github.com/users/danieldietrich/followers","following_url":"https://api.github.com/users/danieldietrich/following{/other_user}","gists_url":"https://api.github.com/users/danieldietrich/gists{/gist_id}","starred_url":"https://api.github.com/users/danieldietrich/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/danieldietrich/subscriptions","organizations_url":"https://api.github.com/users/danieldietrich/orgs","repos_url":"https://api.github.com/users/danieldietrich/repos","events_url":"https://api.github.com/users/danieldietrich/events{/privacy}","received_events_url":"https://api.github.com/users/danieldietrich/received_events","type":"User","site_admin":false},"position":1,"line":1,"path":"examples/red-black/RedBlack.lhs","commit_id":"b888942f33425a871d46105862683e8950d15b23","created_at":"2015-09-08T19:48:25Z","updated_at":"2015-09-08T19:48:25Z","body":"Hi Stephanie,\n\nthank you very much for pointing me in the right direction.\n\nI implemented Kahrs version in Java. Here is the current result:\nhttps://github.com/javaslang/javaslang/blob/master/src/main/java/javaslang/collection/RedBlackTree.java <https://github.com/javaslang/javaslang/blob/master/src/main/java/javaslang/collection/RedBlackTree.java>\n\nAn existing Haskell implementation by Kazu Yamamoto helped me regarding the delete method (see Haskell version of Stefan Kahr's algorithm <https://github.com/danieldietrich/llrbtree/blob/master/Data/Set/RBTree.hs>).\n\nSincerely,\n\nDaniel\n\n> On Aug 11, 2015, at 3:27 PM, Stephanie Weirich <notifications@github.com> wrote:\n> \n> Hi Daniel, \n> \n> I have found Matt’s implementation of delete simpler to understand than Kahrs (though see Andrew Appel’s version of Kahrs too (https://www.cs.princeton.edu/~appel/papers/redblack.pdf).) Part of that is due to Matt’s clear write up of the algorithm in his blog: http://matt.might.net/articles/red-black-delete/\n> \n> However, Matt and his student benchmarked both his version and the Kahrs version and found the latter to be more efficient. See: http://matt.might.net/papers/germane2014deletion.pdf\n> \n> Best,\n> Stephanie\n> \n> \n> \n> > On Aug 10, 2015, at 6:50 PM , Daniel Dietrich <notifications@github.com> wrote:\n> > \n> > @sweirich Hi Stephanie,\n> > \n> > thank you for sharing the delete algorithms for Red Black Trees. I'm about to implement a Red Black Tree in Java 8. However, the delete method is still missing.\n> > \n> > Please let me ask one question: Which solution for delete do you recommend, the one from Stefan Kahrs or the one from Matt Might. Both, conciseness and efficiency, are important for me. In Java, we cannot take advantage of GADT's.\n> > \n> > I'm about to give the algorithm of Matt Might a try but am also curious (without having dived into it, yet) how Stephan Kahrs algorithm does compare to it.\n> > \n> > A little hint would be great.\n> > \n> > Thanks in advance,\n> > \n> > Daniel\n> > \n> > —\n> > Reply to this email directly or view it on GitHub.\n> > \n> \n> —\n> Reply to this email directly or view it on GitHub <https://github.com/sweirich/dth/commit/b888942f33425a871d46105862683e8950d15b23#commitcomment-12640115>.\n> \n\n"}}