Proposal: change the Bits instance for Bool to align with other basic types and support branchless calculations

[Edward Kmett]

We currently as a culture tolerate wildly varying strictness in Num's (+),
Applicative's (<*>), Monoid's mappend, etc.

Keep in mind the strictness analyzer isn't going to see through those (or
this) when you are working polymorphically.

Should we require every Monoid's mappend to be strict in both to maybe get
a few percentage points improvement on fold when you have a strict
container?

After all only finitary containers exist, right?

But you *can* foldMap over an infinite list with the subset of Monoids that
are lazy in their right argument. Folks don't seem to have a problem
employing Foldable/Monoid in this scenario in practice, or using foldr to
build a lazy natural when they want to do a lazy list length comparison for
a list that might be infinite.

What distinguishes Bits in this regard?

-Edward

On Mon, Sep 29, 2014 at 10:14 AM, Anthony Cowley <acowley at seas.upenn.edu>
wrote:

> On Sun, Sep 28, 2014 at 11:06 PM, Gershom B <gershomb at gmail.com> wrote:
> > Did I miss in this thread an actual use-case for strict and/or for Bool
> such that it might occur in a tight inner loop? Absent such a use case, I’m
> -1 on this proposal. If I wanted to use something that I felt had strict
> bitwise behaviour, I’d never reach for a bool, no matter what operator set
> I was working with. My instinct would be to reach for a Word8 or the like,
> since on any real implementation it would take up the same space regardless?
> >
> > Essentially, to my laziness-infected brain, the current instance obeys
> the principle of least surprise, and the proposed instance violates the
> sort of wall of “abstraction intuitions” I’ve built up regarding when I
> should and shouldn’t expect lazy behaviour.
> >
> > -g
>
> The problem is that Bool is the odd duck with respect to the Data.Bits
> operations, so the only way your intuition would serve you is if you
> were sure you would only be working with Bool, in which case the
> question is why you were reaching for Data.Bits.
>
> Anthony
>
>
> >
> >
> > On September 27, 2014 at 1:59:43 PM, David Feuer (david.feuer at gmail.com)
> wrote:
> >> Currently, the (.&.) and (.|.) methods for Bool are short-circuiting,
> >> defined like this:
> >>
> >> instance Bits Bool where
> >> (.&.) = (&&)
> >>
> >> (.|.) = (||)
> >>
> >> Unlike the instances for Int, Word, etc., this gives short-circuiting
> >> behavior (conditionally lazy in the second operand). Unfortunately, this
> >> requires a conditional branch to implement, which can sometimes be bad.
> >> Since (&&) and (||) are readily available to anyone who wants
> >> short-circuiting, I propose that we use the following instead. Note that
> >> the Bits class does not specify anything about this aspect of instance
> >> behavior.
> >>
> >> x .&. y = tagToEnum# (dataToTag# x `andI#` dataToTag# y)
> >>
> >> x .|. y = tagToEnum# (dataToTag# x `orI#` dataToTag# y)
> >>
> >> The rest of the operations look like this:
> >>
> >> x `xor` y = tagToEnum# (dataToTag# x `xorI#` dataToTag# y)
> >>
> >> complement x = tagToEnum# (dataToTag# x `xorI#` 1#)
> >>
> >> shift x s = testBit x s
> >>
> >> rotate x _ = x
> >>
> >> -- I don't think we gain anything changing this one.
> >> bit 0 = True
> >> bit _ = False
> >>
> >> testBit x b = tagToEnum# (dataToTag# x `andI#` (dataToTag# b ==# 0#))
> >>
> >> bitSizeMaybe _ = Just 1
> >>
> >> bitSize _ = 1
> >>
> >> isSigned _ = False
> >>
> >> popCount x = I# (dataToTag# x)
> >>
> >> instance FiniteBits Bool where
> >> finiteBitSize _ = 1
> >> countTrailingZeros x = I# (dataToTag# x `xorI#` 1#)
> >> countLeadingZeros x = I# (dataToTag# x `xorI#` 1#)
> >> _______________________________________________
> >> Libraries mailing list
> >> Libraries at haskell.org
> >> http://www.haskell.org/mailman/listinfo/libraries
> >>
> >
> > _______________________________________________
> > Libraries mailing list
> > Libraries at haskell.org
> > http://www.haskell.org/mailman/listinfo/libraries
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20140929/02c775d0/attachment.html>