#9674: Foldable doesn't have any laws -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: new Priority: normal | Milestone: 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): The laws should be given in terms of `foldMap` and various monoids from `Data.Monoid` rather than `foldr` or `toList`, otherwise the laws will be inaccurate where infinite snoc-lists and the like are involved. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9674#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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

#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 dfeuer): I just realized the better law is the last: `foldMap f = fold . fmap f` implies the other two. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9674#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Changes (by dfeuer): * milestone: 7.12.1 => 7.10.1 Comment: This was mostly fixed by https://ghc.haskell.org/trac/ghc/browser/ghc/libraries/base/Data/Foldable.hs... but `foldr'`, `foldl'`, `foldl1`, and `foldr1`, at least, remain insufficiently documented. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9674#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9674: Foldable doesn't have any laws -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: task | Status: new Priority: normal | Milestone: 7.12.1 Component: Core Libraries | Version: 7.8.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Documentation | Unknown/Multiple bug | Test Case: Blocked By: | Blocking: Related Tickets: #10063 | Differential Revisions: -------------------------------------+------------------------------------- Comment (by gershomb): Also c.f. the proposed law here, pending discussion and tweaking: https://www.haskell.org/pipermail/libraries/2015-February/024943.html -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9674#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler