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

Improve Rational instance #35

Closed treeowl closed 5 years ago

treeowl commented 5 years ago

Mostly unrelatedly: I'd really like to expose both positiveRationals and a version thereof that uses Ratio Natural instead of Ratio Integer. Any thoughts on where such should go? Also, I really think Ratio Natural deserves a Universe instance. I know that'll hamper type inference somewhat, but it feels like the right thing to do.

phadej commented 5 years ago

Please rebase on top of current master, the travis is green there.

phadej commented 5 years ago

How about


class UniverseRatio a where
   positiveRationalStream :: Stream (Ratio a)
   rationalStream :: Stream (Ratio a)

instance UniverseRatio Integer where ...
instance UniverseRatio Natural where ...

instance UniverseRatio a => Universe (Ratio a) where universe = ... rationalStream
treeowl commented 5 years ago

Hrmmmm.... Can we do better? We should probably be able to get more sharing by taking advantage of the fact that each row of the Calkin-Wilf tree consists of a finite sequence and its reversed reciprocal. That could even win some sharing on the negative side. I don't know if that will actually help in practice.

treeowl commented 5 years ago

@phadej, that was the sort of thing I was talking about. If we wanted, we could probably also add instances for Word64 and Int64 using the same construction; they shouldn't overflow until somewhere around the 2^64th element (the fusc function maxes out around the identity function), which seems good enough for most real calculations. To get the exact full sequences for bounded integral types, we could probably be a bit careful and check for overflow.

phadej commented 5 years ago

Int64 there should be a proper justification (both correctness, and practical value), or let's leave it out.

treeowl commented 5 years ago

How tied are we to the current order? I strongly suspect we can get some improvements by changing it a bit, interleaving among the intervals (-∞, -1), (-1, 0), (0, 1), and (1, ∞). Basically, we can generate coprime pairs (m,n) with m < n (the left side of the Calkin-Wilf tree) and from each produce m / n, n / m, -m / n, and -n / m.

treeowl commented 5 years ago

Er, sorry, I guess I was wrong about m < n; that's not guaranteed, but it's also not important.

treeowl commented 5 years ago

Yeah, changing the order seems to make quite a big difference. I think we should do it.

treeowl commented 5 years ago

@dmwit, are you okay with my proposed reordering? My informal tests suggest it helps a lot.

phadej commented 5 years ago

Merged as part of #41