[GHC] #13280: Consider deriving more Foldable methods
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: (none) Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Runtime Unknown/Multiple | performance bug Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- We currently derive `foldMap` and `foldr`, but some others may deserve attention as well. * The most critical spots are probably `length` and `null`. Deriving these instead of using the defaults can change the orders of growth! Given `data Tree a = Bin !(Tree a) a !(Tree a) | Tip`, we surely don't want `null` to traverse the whole spine of the tree when it's quite immediately obvious that `Bin` is never null. And if a constructor contains a type with a very efficient `length` or `null` implementation (e.g., one that stores its own size), we certainly want to use that. * `foldl` typically ends up with rather different code than `foldr` (for a recursive type) even after simplification. We need to check whether this has a performance impact, but my bet is that it will in cases where the optimizer can't understand what's going on well enough. * `foldl'` and `foldr'` are a bit tricky. Ideally, if we have something like `data T a = C (G a) a | ...` then we'd like to be able to use `G`'s `foldl'` definition to define `T`'s. Unfortunately, different types in the wild have different `foldl'` semantics (and indeed the semantics for `[]` changed by mistake fairly recently). So we have to decide to what extent the derived semantics should depend on the choices of included types. I think we should probably just depend, because that seems likely what people will expect and want. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13280 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * owner: (none) => dfeuer -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13280#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) * keywords: => deriving-perf -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13280#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by dfeuer): Note about `length`, so I don't forget: For the nested case, {{{#!hs Con ... f (g a) ... }}} the way to make sure we never do worse than the default `length` definition (assuming the recursively called `length` is good) is to use {{{#!hs length (Con ... fga ...) = ... + foldl' (\acc x -> acc + length x) 0 fga + ... }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13280#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#13280: Consider deriving more Foldable methods
-------------------------------------+-------------------------------------
Reporter: dfeuer | Owner: dfeuer
Type: task | Status: new
Priority: normal | Milestone: 8.2.1
Component: Compiler | Version: 8.0.1
Resolution: | Keywords: deriving-perf
Operating System: Unknown/Multiple | Architecture:
Type of failure: Runtime | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by David Feuer
#13280: Consider deriving more Foldable methods -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 8.8.1 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: 8.6.1 => 8.8.1 Comment: Is there anything else to be done here? Perhaps `length`? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/13280#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC