[Haskell-cafe] Enforcing data structures invariant in the type system

Frank Staals frank at fstaals.net
Mon Mar 30 18:28:39 UTC 2015

Nicola Gigante <nicola.gigante at gmail.com> writes:

>> Il giorno 30/mar/2015, alle ore 19:17, Oliver Charles <ollie at ocharles.org.uk> ha scritto:
>> You're in the right ballpark that's for sure - and your experience with
>> hard-to-decode error messages is not a new one either! Haskell is somewhat
>> "experiemental" in this domain, as its only now starting to learn the
>> features necessary to do what you want to do.
> Having some compilers background I understand very well the difficulties in making sensible error messages,
> especially when dealing with such advanced features. The point was more that I don’t know the basics on
> how those features work (and what is involved in the job of the type checker) so I can’t even parse what 
> GHC try to tell me (skolem what?).
>> I think some of the best work to learn the latest techniques is described
>> here: https://github.com/jstolarek/dep-typed-wbl-heaps-hs
>> <https://github.com/jstolarek/dep-typed-wbl-heaps-hs>
> Thank you that looks very useful!
>> -- ocharles
> Greetings,
> Nicola
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Stephanie Stephanie Weirich gave an invited talk about maintaining color
and height invariants for Red-Black trees at ICFP this year [1]. Connor
McBride had a talk and paper about also maintinging order invariants
[2]. You might want to have a look at them.  

As for getting used to the error messages. I think the only way to learn
is to get your hands dirty yourself. I can highly reccommend also just
doing the red-black trees yourself. Getting insertions to work is not
too difficult. Deletions are a bit harder. I also did so some time ago
[3] (before seeing the ICFP talk even; I found it very cool that I had
pretty much the same solution :)).


[1] https://www.youtube.com/watch?v=rhWMhTjQzsU&index=22&list=PL4UWOFngo5DVBqifWX6ZlXJ7idxWaOP69

[2] https://www.youtube.com/watch?v=pNBPCnZEdSs

[3] http://fstaals.net/RedBlackTree.html


- Frank

More information about the Haskell-Cafe mailing list