RE: Advent of Code Day 11 [spoilers], Inclusion-Exclusion, and Haskell's odd design decisions

You are viewing a single comment's thread from:

Advent of Code Day 11 [spoilers], Inclusion-Exclusion, and Haskell's odd design decisions

in adventofcode •  6 years ago 

I mean, seriously, Haskell, WTF? Who need a maximum that is right-associative and lazy?

    maximum :: forall a . Ord a => t a -> a
    maximum = fromMaybe (errorWithoutStackTrace "maximum: empty structure") .
       getMax . foldMap (Max #. (Just :: a -> Maybe a))

foldMap uses foldr so maximum and maximumBy use different orders! Who wanted that!?

Note [maximumBy/minimumBy space usage]
When the type signatures of maximumBy and minimumBy were generalized to work over any Foldable instance (instead of just lists), they were defined using foldr1. This was problematic for space usage, as the semantics of maximumBy and minimumBy essentially require that they examine every element of the data structure. Using foldr1 to examine every element results in space usage proportional to the size of the data structure. For the common case of lists, this could be particularly bad (see Trac #10830).
For the common case of lists, switching the implementations of maximumBy and minimumBy to foldl1 solves the issue, as GHC's strictness analysis can then make these functions only use O(1) stack space. It is perhaps not the optimal way to fix this problem, as there are other conceivable data structures (besides lists) which might benefit from specialized implementations for maximumBy and minimumBy (see
https://ghc.haskell.org/trac/ghc/ticket/10830#comment:26 for a further discussion). But using foldl1 is at least always better than using foldr1, so GHC has chosen to adopt that approach for now.

Source: http://hackage.haskell.org/package/base-4.12.0.0/docs/src/Data.Foldable.html#maximum

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!