Strictness of Semigroup instance for Maybe

Discussion:

Donnacha Oisín Kidney

2018-05-22 21:57:29 UTC

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)

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.

David Feuer

2018-05-22 23:37:42 UTC

Permalink

I think extra laziness here would be a bit surprising.

On Tue, May 22, 2018 at 5:57 PM, Donnacha Oisín Kidney

Post by Donnacha OisÃn Kidney
instance Semigroup a => Semigroup (Maybe a) where
Nothing <> b = b
a <> Nothing = a
Just a <> Just b = Just (a <> b)
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.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption . foldMap

(pure.pure) $ [1..]
_|_
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/)
and was encouraged to post it here.
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Tikhon Jelvis

2018-05-22 23:57:32 UTC

Permalink

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 &&.)

Post by David Feuer
I think extra laziness here would be a bit surprising.
On Tue, May 22, 2018 at 5:57 PM, Donnacha OisÃn Kidney

Data.Monoid.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption .

foldMap

Post by Donnacha OisÃn Kidney
(pure.pure) $ [1..]
_|_
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<>)

Post by Donnacha OisÃn Kidney
ys))
instance Semigroup a => Monoid (LeftOption a) where
mempty = LeftOption Nothing
mappend = (<>)

fmap Data.Semigroup.getFirst . getLeftOption . foldMap

(LeftOption .

Post by Donnacha OisÃn Kidney
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/)

Post by Donnacha OisÃn Kidney
and was encouraged to post it here.
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Ryan Reich

2018-05-23 01:19:19 UTC

Permalink

I second this expectation. I've recently had a hard time ensuring laziness
in my work and it's been comforting in rooting out failures to know that
the standard libraries, at least, are concerned about it.

Post by Tikhon Jelvis
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 &&.)

Post by David Feuer
I think extra laziness here would be a bit surprising.
On Tue, May 22, 2018 at 5:57 PM, Donnacha OisÃn Kidney

Data.Monoid.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption .

foldMap

(x<>)

Post by Donnacha OisÃn Kidney
ys))
instance Semigroup a => Monoid (LeftOption a) where
mempty = LeftOption Nothing
mappend = (<>)

fmap Data.Semigroup.getFirst . getLeftOption . foldMap

(LeftOption .

https://www.reddit.com/r/haskell/comments/8lbzan/semigroup_maybe_too_strict/
)

Post by Donnacha OisÃn Kidney
and was encouraged to post it here.
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andrew Martin

2018-05-23 11:21:04 UTC

Permalink

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

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 &&.)

Post by David Feuer
I think extra laziness here would be a bit surprising.
On Tue, May 22, 2018 at 5:57 PM, Donnacha OisÃn Kidney

Data.Monoid.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption . foldMap

fmap Data.Semigroup.getFirst . getLeftOption . foldMap (LeftOption .

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Eric Mertens

2018-05-23 15:14:33 UTC

Permalink

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

Post by Andrew Martin
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
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 &&.)

Post by David Feuer
I think extra laziness here would be a bit surprising.
On Tue, May 22, 2018 at 5:57 PM, Donnacha OisÃn Kidney

Data.Monoid.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption .

foldMap

(x<>)

Post by Donnacha OisÃn Kidney
ys))
instance Semigroup a => Monoid (LeftOption a) where
mempty = LeftOption Nothing
mappend = (<>)

fmap Data.Semigroup.getFirst . getLeftOption . foldMap

(LeftOption .

https://www.reddit.com/r/haskell/comments/8lbzan/semigroup_maybe_too_strict/
)

Post by Donnacha OisÃn Kidney
and was encouraged to post it here.
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Carter Schonwald

2018-05-23 18:54:48 UTC

Permalink

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 :)

Post by Eric Mertens
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

Post by Andrew Martin
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
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 &&.)

Post by David Feuer
I think extra laziness here would be a bit surprising.
On Tue, May 22, 2018 at 5:57 PM, Donnacha OisÃn Kidney

Data.Monoid.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption .

foldMap

(x<>)

Post by Donnacha OisÃn Kidney
ys))
instance Semigroup a => Monoid (LeftOption a) where
mempty = LeftOption Nothing
mappend = (<>)

fmap Data.Semigroup.getFirst . getLeftOption . foldMap

(LeftOption .

semigroup_maybe_too_strict/)

Post by Donnacha OisÃn Kidney
and was encouraged to post it here.
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Donnacha Oisín Kidney

2018-05-23 19:39:17 UTC

Permalink

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.

Post by Carter Schonwald
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 :)
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
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

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 &&.)
I think extra laziness here would be a bit surprising.
On Tue, May 22, 2018 at 5:57 PM, Donnacha OisÃn Kidney

Data.Monoid.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption . foldMap

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
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries <http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries>

Andrew Martin

2018-05-24 14:05:07 UTC

Permalink

Ah, here it is:
https://www.reddit.com/r/haskell/comments/7nmcrj/what_evaluation_strategy_to_use_for_a_new/ds3ykie/.
Relevant excerpt:

I often see people saying they can get away with working with a "Lazy"
annotation in a strict language all the time. Strict languages with
"opt-in" laziness tend to lack the courage of their conviction after making
that statement, though. You can get a sense for how honest that appraisal
is by looking at the definition of Monoid in their language. If you wanted
to capture all of the power of a lazy language, it'd need to be marked Lazy
in one or both of its arguments. If its only one then Dual gets hosed. (See
many of the versions of scalaz) If neither then you dare not implement any
or all via the Any or All monoid, lest you lose short-circuiting (&&)
evaluation, if you have it at all. So you now have an abstraction, but dare
not use it. You find that in a language that is strict, these notions like
Monoid, Applicative, etc. all really need to pick up variants based on your
strictness in each argument, and frankly, nobody bothers and it all gets
swept under the rug.

Post by David Feuer
I think extra laziness here would be a bit surprising.
On Tue, May 22, 2018 at 5:57 PM, Donnacha OisÃn Kidney

Data.Monoid.getFirst . foldMap pure $ [1..]

Just 1

fmap Data.Semigroup.getFirst . Data.Semigroup.getOption .

foldMap

(x<>)

Post by Donnacha OisÃn Kidney
ys))
instance Semigroup a => Monoid (LeftOption a) where
mempty = LeftOption Nothing
mappend = (<>)

fmap Data.Semigroup.getFirst . getLeftOption . foldMap

(LeftOption .

maybe_too_strict/)

Post by Donnacha OisÃn Kidney
and was encouraged to post it here.
_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
-Andrew Thaddeus Martin