[GHC] #12618: Add saturated constructor applications to Core

[GHC]

#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