
#12618: Add saturated constructor applications to Core -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nomeata): Replying to [comment:5 nomeata]:
What is special about a data constructor that allows this, that a function (like, say, `flip`) does not have?
Let me try to answer that myself: Essentially, you are proposing a way of compressing the representation of Core, by omitting (type) arguments that can easily and in a syntax- directed manner be recovered. You are implying here the existence of a pair of functions {{{ compressArgs :: DataCon -> [Expr v] -> [Expr v] decompressArgs :: DataCon -> [Expr v] -> [Expr v] }}} that remove and recover implied arguments. For example `compressArgs "Left" [Bool,Int,True] = [Bool, True]`. We obviously want to following identity to hold: {{{ length args == dcArity dc ==> decompressArgs dc (compressArgs dc args) == args }}} What does `compressArgs` and `decompressArgs` need from `DataCon`? Two bits of information: * It’s type (`forall a b. a -> Either a b`) and * its arity (3, counting type arguments). Well, `compressArgs` does not need the arity, because it is just the length of the input list, if the application is saturated. But `decompressArgs` does (why? see example later). So really, we have a pair of functions {{{ compressArgs :: Type -> [Expr v] -> [Expr v] decompressArgs :: Type -> Arity -> [Expr v] -> [Expr v] }}} Here, we want {{{ decompressArgs ty (length args) (compressArgs ty args) == args }}} And with this I can see how the above proposal easily generalizes to functions: Have {{{ | Apps (Expr v) Arity [Expr v] -- NEW }}} Instead of {{{f `App` x `App` y `App` z}}} you can use `Apps f 3 (compressArgs (exprType f) [x,y,z])`. No information is lost (because of the above identity), but any redundant information can be removed by `compressArgs`. Why do we need to store the arity? Because `compressArgs` can produce the same compressed list for different input lists: {{{ compressArgs "forall a. a -> a" [Bool,True] == [True] compressArgs "forall a. a -> a" [Bool] == [Bool] compressArgs "forall a. a -> a" [Type, Bool] == [Bool] }}} I imagine getting rid of all (well, many more) of the redundant type applications throughout Core can be big win, so maybe this generalization should be considered. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12618#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler