search

dmwit / universe

Classes for types where we know all the values
BSD 3-Clause "New" or "Revised" License
37 stars 17 forks source link

Containers #22

Closed phadej closed 8 years ago

phadej commented 8 years ago

Set implementation for https://github.com/dmwit/universe/issues/20

Contains commits from #21

dmwit commented 8 years ago

For the Finite instance, it might be worth considering this implementation:

    universe = map S.fromAscList $ filterM (const [False, True]) (sort universe)

This results in only one sort, as opposed to approximately half of a "sort" for each inhabitant. The cost is probably a bigger memory footprint.

Anyway, :+1: on this.

phadej commented 8 years ago

universe for Finite is only finite, it can be quite large (e.g. even for Int64). So I don't like sorting it.

A bit unrelated, we could have FiniteSize a :: Nat type family on GHC's supporting it.

dmwit commented 8 years ago

Right. It depends a lot on the usage whether it's okay to store the whole thing in memory -- e.g. certainly if you walk the entire universe it must be okay, since you're explicitly constructing a Set containing the whole sub-universe, but one might not always want to walk the whole thing.

Perhaps it is time for our first newtype.

phadej commented 8 years ago

I'd say it's almost never ok to store the whole universe in memory, only iterate (in some constant space) over it. If one would like to have everything in memory it would be still possible.

dmwit commented 8 years ago

Let's try to be clear about which types of universe we're talking about.

When constructing universe :: [Set a], some element in this list will contain every element in universe :: [a]. This is unavoidable. In those cases where that element will eventually be inspected, it is perfectly reasonable for the code that constructs universe :: [Set a] to store all of universe :: [a] in memory -- since it absolutely must do that anyway.

phadej commented 8 years ago

OTOH if you inspect only some prefix of universe :: [Set a] you'd need to have only some prefix of universe :: [a]. E.g. Would still be nice to inspect some header of universe :: [Set Int] even universe :: [Int] cannot fit into memory.

dmwit commented 8 years ago

Indeed, that is the tradeoff. I'm not sure it's possible to make that design decision correctly inside the library -- which is why a newtype may be needed. Probably your streaming implementation should be the default one, and the newtype should be the one that calls sort.

dmwit commented 8 years ago

...I'm also happy with leaving a TODO comment in the file for future spelunkers, and not implementing the newtype until it's needed!

phadej commented 8 years ago

I'll merge this. Let's discuss how to proceed in https://github.com/dmwit/universe/issues/23