Strictness of Semigroup instance for Maybe
Donnacha Oisín Kidney
mail at doisinkidney.com
Wed May 23 19:39:17 UTC 2018
Not sure if I’m correct on this, but wouldn’t you get space leaks in the right-strict version as well? Because the Just constructor itself isn’t strict, you still build up a long chain of <>. In the right-lazy version, you build up a long chain of maybe a (a<>), which is more expensive, yes, but not asymptotically. In other words, if you’ve got a space leak in the right-lazy version, you’ll also have one in the right-strict version.
> On 23 May 2018, at 14:54, Carter Schonwald <carter.schonwald at gmail.com> wrote:
>
> yeah ... i agreed with Eric,
> we almost need Lazy and Strict versions of monoid and each blows up in different ways. I definitely had epic space leaks from the lazy Maybe Monoid
>
> -1 :)
>
> On Wed, May 23, 2018 at 11:14 AM, Eric Mertens <emertens at gmail.com <mailto:emertens at gmail.com>> wrote:
> Hello,
>
> I think changing the strictness of this function could have potentially dramatic performance effects on a wide range of existing code. Exploring existing code to understand the exact impacts would be a huge challenge, and this is a change that would be hard to phase in.
>
> The arbitrariness of decisions like this is part of what makes the Monoid class a mess in the first place. Attaching instances like this to otherwise generic types forces us to make arbitrary choices, which are often not documented on the instances themselves.
>
> While the left-bias behavior might make sense in the case of an instance like we have for First, I don't see why it would be considered more correct in this case.
>
> I'm -1 on this proposal.
>
> Best regards,
> Eric Mertens
>
> On Wed, May 23, 2018 at 4:21 AM Andrew Martin <andrew.thaddeus at gmail.com <mailto:andrew.thaddeus at gmail.com>> wrote:
> I feel the the way concerning being lazy as possible and being left-strict where there is a symmetric choice to be made. This seems to be a common theme is base, although I’ve never seen it officially endorsed. I have seen Edward Kmett talk about this on reddit (contrasting it with the Monoid classes in strict-by-default languages), but I cannot find the thread.
>
> Sent from my iPhone
>
> On May 22, 2018, at 7:57 PM, Tikhon Jelvis <tikhon at jelv.is <mailto:tikhon at jelv.is>> wrote:
>
>> I think the extra laziness makes sense here—it matches the behavior of common functions like &&. My general expectation is that functions are as lazy as they can be and, in the case of operators with two arguments, that evaluation goes left-to-right. (Again like &&.)
>>
>> On Tue, May 22, 2018 at 4:37 PM, David Feuer <david.feuer at gmail.com <mailto:david.feuer at gmail.com>> wrote:
>> I think extra laziness here would be a bit surprising.
>>
>> On Tue, May 22, 2018 at 5:57 PM, Donnacha Oisín Kidney
>> <mail at doisinkidney.com <mailto:mail at doisinkidney.com>> wrote:
>> > The current semigroup instance for Maybe looks like this:
>> >
>> > instance Semigroup a => Semigroup (Maybe a) where
>> > Nothing <> b = b
>> > a <> Nothing = a
>> > Just a <> Just b = Just (a <> b)
>> >
>> > However, it could be lazier:
>> >
>> > instance Semigroup a => Semigroup (Maybe a) where
>> > Nothing <> b = b
>> > Just a <> b = Just (maybe a (a<>) b)
>> >
>> > This causes different behaviour for Data.Semigroup.First and
>> > Data.Monoid.First:
>> >
>> > >>> Data.Monoid.getFirst . foldMap pure $ [1..]
>> > Just 1
>> > >>> fmap Data.Semigroup.getFirst . Data.Semigroup.getOption . foldMap
>> > (pure.pure) $ [1..]
>> > _|_
>> >
>> > A different definition for `Option` gets back the old behaviour:
>> >
>> > newtype LeftOption a = LeftOption { getLeftOption :: Maybe a }
>> >
>> > instance Semigroup a => Semigroup (LeftOption a) where
>> > LeftOption Nothing <> ys = ys
>> > LeftOption (Just x) <> LeftOption ys = LeftOption (Just (maybe x (x<>)
>> > ys))
>> >
>> > instance Semigroup a => Monoid (LeftOption a) where
>> > mempty = LeftOption Nothing
>> > mappend = (<>)
>> >
>> > >>> fmap Data.Semigroup.getFirst . getLeftOption . foldMap (LeftOption .
>> > Just . Data.Semigroup.First) $ [1..]
>> > Just 1
>> >
>> > Is there any benefit to the extra strictness? Should this be changed?
>> >
>> > Another consideration is that the definition could equivalently be
>> > right-strict, to get the desired behaviour for Last, but I think the
>> > left-strict definition probably follows the conventions more.
>> >
>> > I originally posted this to reddit
>> > (https://www.reddit.com/r/haskell/comments/8lbzan/semigroup_maybe_too_strict/ <https://www.reddit.com/r/haskell/comments/8lbzan/semigroup_maybe_too_strict/>)
>> > and was encouraged to post it here.
>> >
>> > _______________________________________________
>> > Libraries mailing list
>> > Libraries at haskell.org <mailto:Libraries at haskell.org>
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
>> >
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org <mailto:Libraries at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
>>
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org <mailto:Libraries at haskell.org>
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org <mailto:Libraries at haskell.org>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org <mailto:Libraries at haskell.org>
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20180523/a71d5429/attachment.html>
More information about the Libraries
mailing list