[Haskell-cafe] Explanation of Data.Set, please

Galaxy Being borgauf at gmail.com
Sun Aug 1 22:12:25 UTC 2021


I'm looking at this
<https://hackage.haskell.org/package/containers-0.6.5.1/docs/src/Data.Set.Internal.html>
code and wondering, first, about the strategy behind the data type Set
itself

data Set a    = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a) | Tip

It says it's a "balanced tree." I found this
<http://groups.csail.mit.edu/mac/users/adams/BB/index.html> talking about
maybe why that is. Will read. But in the meantime, any explanation in plain
English as to why we're doing it as a tree and not some other structure
would be helpful. And why are we bringing Size along, and in general, why
all the strictness !'s? All this might have something to do with why a
balanced tree is better than quick-and-dirty list representation like I see
in beginner tutorials? Next, is this ZFC? I've seen treatments that
supposedly are ZFC-friendly. Finally, I've taken a preliminary look at
Agda, and right from the start there's Set, and no doubt an entirely
alternative, category universe approach to the concept of set theory. Any
contrast and compare between Haskell and Agda's set notions would be
appreciated. Haskell seems to dance in and out of Category Theory, while
Agda seems pretty much just CT....

-- 
⨽
Lawrence Bottorff
Grand Marais, MN, USA
borgauf at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20210801/f5127785/attachment.html>


More information about the Haskell-Cafe mailing list