Hacker GitHub

← All repos

yairchu/red-black-tree

View on GitHub ↗ ★ 8 Haskell

Type-Guaranteed balanced search tree

9 mentions on Hacker News by 3 people: 0 stories, 9 comments · first 2011-04-10 · latest 2015-12-22

Mentions per year 9 mentions · busiest year 2011 (3)
20082026
AllStoriesComments NewestTopOldest
  1. …how you leveraged the type system. For example, if you define a red black tree as is defined here: https://github.com/yairchu/red-black-tree/blob/master/RedBla... You know code will never generate trees that break the red/black invariants.…
    comment by Peaker · 2015-12-22 · in Is Sound Gradual Typing Dead? [pdf]
  2. https://github.com/yairchu/red-black-tree Has implementations of some binary search trees with GADTs to guarantee, at compile-time, that most of the tree's invariants always hold.
    comment by Peaker · 2015-01-07 · in Detecting use cases for GADTs in OCaml
  3. Code review time! https://github.com/yairchu/red-black-tree/blob/master/RedBla... First we create two differently typed tags for Red and Black. data Red data Black Note this differs from something like data Color = Red | Black in that Red…
    comment by tel · 2013-07-09 · in What I learned using unit tests/TDD
  4. …about correctness, even of the exact feature under test. Consider the 10 lines starting from https://github.com/yairchu/red-black-tree/blob/master/RedBla... They guarantee the correctness of the invariants of the Red Black Tree, and they…
    comment by Peaker · 2013-07-03 · in Frameworks Round 6
  5. …you wouldn't expect to catch with a mere type system. In Haskell, I can write this (lines 27-37): https://github.com/yairchu/red-black-tree/blob/master/RedBla... to specify my red black tree, with type-level enforcement of all of the…
    comment by Peaker · 2013-06-03 · in On Go
  6. …of extensions which you can use to do really crazy stuff (like verifiably correct red-black trees, https://github.com/yairchu/red-black-tree/blob/master/RedBla... ).
    comment by njs12345 · 2012-03-20 · in Functional Programming For The Rest of Us
  7. Here's an interesting partial implementation (no delete): https://github.com/yairchu/red-black-tree/blob/master/RedBla... The AVL has a fuller implementation: https://github.com/yairchu/red-black-tree/blob/master/AvlTre... It's…
    comment by Peaker · 2011-09-11 · in Treaps: A Simple Balanced Binary Tree
  8. I wonder if Qi can express GADTs to allow proof of balance properties, as in this Haskell example: https://github.com/yairchu/red-black-tree/blob/master/RedBla...
    comment by Peaker · 2011-06-29 · in Purely Functional Data Structures : Red Black Trees in Qi
  9. …type system can also express interesting things most languages' type systems can't. For example: https://github.com/yairchu/red-black-tree/blob/master/AvlTre... -- in lines 13..21, an AVLTree type is defined -- with its invariants encoded…
    comment by Peaker · 2011-04-10 · in Trying Haskell