<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>I made two MRs for GHC:<br>
<br>
- new class Bits b => Complement b in <a
href="https://gitlab.haskell.org/ghc/ghc/merge_requests/2261">https://gitlab.haskell.org/ghc/ghc/merge_requests/2261</a><br>
- or also class Bits b => PopCount b in <a
href="https://gitlab.haskell.org/ghc/ghc/merge_requests/2270">https://gitlab.haskell.org/ghc/ghc/merge_requests/2270</a><br>
<br>
The patches are quite direct, nothing surprising. GHC compiles
fine itself, Few tests are failing: I'll fix them, if we decide
to go with either.<br>
<br>
- Oleg<br>
</p>
<div class="moz-cite-prefix">On 2.12.2019 18.47, Edward Kmett wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAJumaK9US2v=37M9Sf5UJQg-M4MsCdpmQgpO8qJJUmRwd17YUA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">I'm not averse to the idea of factoring out
complementation into a separate class to make the Bits instance
for Natural total. It strikes me as a laudable goal and it comes
very close to encoding what Stone called a "Generalized Boolean
Algebra" in the 30s, which hints to me that we might be onto the
right abstraction here. Consider me a weak +1 there.
<div><br>
</div>
<div>
<div>
<div>-Edward</div>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, Dec 2, 2019 at 6:01 AM
Oleg Grenrus <<a href="mailto:oleg.grenrus@iki.fi"
moz-do-not-send="true">oleg.grenrus@iki.fi</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF">
<p>I'd refine the documentation of `Bits` class to say that
it's a class for integral types with finite count of bits
toggled, i.e. finite popCount.<br>
Than many things work out, except complementInteger is
actually used.<br>
<br>
It's not a big change codewise: <a
href="https://gitlab.haskell.org/ghc/ghc/merge_requests/2261"
target="_blank" moz-do-not-send="true">https://gitlab.haskell.org/ghc/ghc/merge_requests/2261</a>
(GHC actually uses complementInteger for something
itself).<br>
<br>
Without complement, Bits Natural would total instance,
without partial methods. If complement for Integer is very
important, then I'd propose to introduce classes to form
diamond shape:<br>
<br>
-- instance can be defined for Integer<br>
class Bits b => Complement b where<br>
complement :: b -> b<br>
<br>
-- instance can be defined for Natural<br>
class Bits b => PopCount b where<br>
popCount :: b -> b<br>
<br>
class Complement b => FiniteBits b where<br>
...<br>
<br>
I think this is worth the trouble, this wart should been
fixed when Natural was brought to base. And in fact,
because of complement is in Bits, clearBit :: Natural
-> Natural is broken in base-4.9.0.0 bundled with
GHC-8.0: It went unnoticed, because there were default
implementation using complement. If Haskell2020 will
happen, it really should explain what the complement ::
Natural -> Natural does otherwise. Haskell2010 just
mentions that there is Bits Integer. For the report
defense, popCount isn't in its Bits version.<br>
<br>
So, we made warts by both adding popCount to Bits and
adding Natural Bits instance. Let's just fix them.<br>
<br>
- Oleg<br>
</p>
<div>On 1.12.2019 5.21, Brent Yorgey wrote:<br>
</div>
<blockquote type="cite">
<div dir="ltr">
<div>A few points:</div>
<div><br>
</div>
<div>1. The Bits instance for Integer essentially
already behaves as if they are the 2-adic numbers.
For example, if you use testBit you can discover that
(-2 :: Integer) is treated as if it were an infinite
sequence of 1's followed by a single 0.</div>
<div>2. However, because testBit takes an Int index,
instances of Bits actually can't have an infinite
number of 1 bits---at least not in practice---since
you cannot observe anything past the (maxBound ::
Int)th bit.</div>
<div>3. Currently, popCount on negative Integer values
satisfies popCount (-x) = -(popCount x) which does
not seem very well motivated and does not match the
way negative values are presented via testBit.</div>
<div><br>
</div>
<div>I am strongly -1 on moving popCount to FiniteBits.
popCount on positive Integers is useful and
well-defined. I am mildly +1 on Zemlya's proposal to
change the behavior of popCount for negative Integer
values, though I am not sure it is really worth the
trouble.</div>
<div><br>
</div>
<div>-Brent<br>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sat, Nov 30, 2019
at 10:10 AM Zemyla <<a
href="mailto:zemyla@gmail.com" target="_blank"
moz-do-not-send="true">zemyla@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px
0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div dir="auto">popCount is a perfectly sensible
method for Natural, and it could theoretically
become one for Integer as well if we say that,
whenever there's an infinite number of 1s and a
finite number of 0s, then the result is -(1 + count
of 0s), as though it were maxBound :: Word bits in
size and merely converted to an Int (a sensible
assumption, considering memory limits). The results
for types where there can be both infinite 0s and 1s
should still be an error.</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sat, Nov 30,
2019, 09:21 Oleg Grenrus <<a
href="mailto:oleg.grenrus@iki.fi"
target="_blank" moz-do-not-send="true">oleg.grenrus@iki.fi</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px
0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Although,
popCount for Integer/Natural kind of makes sense,
as they <br>
aren't infinite list of [Bit]s, but smarter
structure.<br>
<br>
On 30.11.2019 17.17, Oleg Grenrus wrote:<br>
> I propose to change it to be member of
FiniteBits<br>
><br>
> I recall, there was a proposal to remove
bitSize from Bits, so it's an <br>
> opportunity to introduce another small, yet
breaking change at the <br>
> same time.<br>
><br>
> Discussion time 2 week.<br>
><br>
> - Oleg<br>
><br>
>
_______________________________________________<br>
> Libraries mailing list<br>
> <a href="mailto:Libraries@haskell.org"
rel="noreferrer" target="_blank"
moz-do-not-send="true">Libraries@haskell.org</a><br>
> <a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org"
rel="noreferrer" target="_blank"
moz-do-not-send="true">Libraries@haskell.org</a><br>
<a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote>
</div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank"
moz-do-not-send="true">Libraries@haskell.org</a><br>
<a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer" target="_blank"
moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote>
</div>
</blockquote>
</div>
_______________________________________________<br>
Libraries mailing list<br>
<a href="mailto:Libraries@haskell.org" target="_blank"
moz-do-not-send="true">Libraries@haskell.org</a><br>
<a
href="http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries"
rel="noreferrer" target="_blank" moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries</a><br>
</blockquote>
</div>
</blockquote>
</body>
</html>