#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