[GHC] #9674: Foldable doesn't have any laws

[GHC]

#9674: Foldable doesn't have any laws
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:  ekmett
                  Type:  task        |           Status:  new
              Priority:  normal      |        Milestone:  7.10.1
             Component:  Core        |          Version:  7.8.3
  Libraries                          |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Unknown
  Unknown/Multiple                   |       Blocked By:
       Type of failure:              |  Related Tickets:
  Documentation bug                  |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by ekmett):

 `Foldable` is anything for which `foldMap` is defined, with a bunch of
 coherence conditions on how the other members relate to `foldMap`.

 `foldr` defines directly in terms of `foldMap`

 {{{
 foldr f z t = appEndo (foldMap (Endo . f) t) z
 }}}

 Then `toList` defines in terms of `foldr` without any infinite re-
 association concerns, because of the properties of `(:)`

 {{{
 toList = foldr (:) []
 }}}

 The numerical members added as a result of the latest proposal can be
 defined in terms of `foldMap`, and are definable to be equal to the
 following up to a finite number of reassociations of `(+)` and `(*)`.

 {{{
 sum = getSum . foldMap Sum
 product = getProduct . foldMap Product
 }}}

 This statement allows both the `foldl` and `foldr` interpretations of
 `sum` and `product` as employed now and doesn't rule out the existence of
 infinite containers -- like, you know, lists.

 It is preferable to define these this way in terms of `foldMap` rather
 than the more obvious definition in terms of `sum = sum . toList` because
 the latter definition may be undefined for infinite snoc-lists or Foldable
 containers where the infinite recursion occurs some place other than the
 right, so these laws are more defined.

 The class offers you the ability to define `foldMap` in terms of `foldr`
 and vice versa. However, defining `foldMap` in terms of `foldr` is only
 really specifiable in the finite case, so really ultimately the behavior
 up to finite reassociation is given by `foldMap` and the behavior of
 `foldr` is induced. This default definition of `foldMap` in terms of
 `foldr` only works for structures with infinite recursion only occurring
 on the right, so it doesn't work out to state it properly as a law in the
 infinite case.

 I'd need to go through in more detail, but in general the remaining laws
 should be be able to be stated as claiming the answers provided should be
 equivalent to what you'd get with the default definitions under minor
 assumptions about the fact that dictionaries passed for things like `Ord`
 in the case of things like `maximum`/`minimum` are law abiding.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9674#comment:3>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler