After reading Francesco's original post, I immediately thought of Ömer's proposed approach, of using Template Haskell to produce the right data family instances. But I don't see why you'd need quoting at constructor calls. Couldn't you just have a type class like `PointFamily`? I'd be more interested to see client code in Ömer's version than the TH generation code.
The TH approach would seem to require having a fixed set of specializations, which is a downside. But I'm not sure it's so much of a downside that the approach is unusable. Richard On Nov 15, 2015, at 10:08 AM, Ömer Sinan Ağacan <omeraga...@gmail.com> wrote: > I had started working on exactly the same thing at some point. I had a > TemplateHaskell-based implementation which _almost_ worked. > > The problem was that the syntax was very, very heavy. Because I had to use > quotes for _every_ constructor application(with explicitly passed types). > (because I had a specialized constructor for every instantiation of this > generic type) > > Another problem was that because of how TemplateHaskell quotes evaluated, I > couldn't use a `List Int` where `List` is a template without first manually > adding a line for generating specialized version of `List` on `Int`. > > When all of these combined it became very hard to use. But it was a > proof-of-concept and I think it worked. > > (Code is horrible so I won't share it here :) I had to maintain a state shared > with different TH quote evaluations etc.) > > 2015-11-15 5:26 GMT-05:00 Francesco Mazzoli <f...@mazzo.li>: >> (A nicely rendered version of this email can be found at >> <https://gist.github.com/bitonic/52cfe54a2dcdbee1b7f3>) >> >> ## Macro types >> >> I very often find myself wanting unboxed polymorphic types >> (e.g. types that contain `UNPACK`ed type variables). I find >> it extremely frustrating that it's easier to write fast _and_ >> generic code in C++ than in Haskell. >> >> I'd like to submit to the mailing list a very rough proposal >> on how this could be achieved in a pretty straightforward way >> in GHC. >> >> The proposal is meant to be a proof of concept, just to show that >> this could be done rather easily. I did not think about a nice >> interface or the implementation details in GHC. My goal is to >> check the feasibility of this plan with GHC developers. >> >> I'll call such types "macro types", since their effect is similar >> to defining a macro that defines a new type for each type >> variable instantiation. >> >> Consider >> >> ``` >> data #Point a = Point >> { x :: {-# UNPACK #-} !a >> , y :: {-# UNPACK #-} !a >> } >> ``` >> >> This definition defines the macro type `#Point`, with one parameter >> `a`. >> >> Macro types definition would be allowed only for single-constructor >> records. The intent is that if we mention `#Point Double`, it will >> be equivalent to >> >> ``` >> data PointDouble = PointDouble >> { x :: {-# UNPACK #-} !Double >> , y :: {-# UNPACK #-} !Double >> } >> ``` >> >> To use `#Point` generically, the following type class would be >> generated: >> >> ``` >> class PointFamily a where >> data #Point a :: * -- Family of types generated by @data #Point a@. >> #Point :: a -> a -> #Point a -- Constructor. >> #x :: #Point a -> a -- Projection @x@. >> #y :: #Point a -> a -- Projection @y@. >> ``` >> >> Thi type class lets us work with `#Point`s generically, for example >> >> ``` >> distance :: (PointFamily a, Fractional a) => #Point a -> #Point a -> a >> distance p1 p2 = >> let dx = #x p1 - #x p2 >> dy = #y p1 - #y p2 >> in sqrt (dx*dx + dy*dy) >> ``` >> >> Internally, for every type appearing for `a`, e.g. `#Point Double`, >> a new type equivalent to the `PointDouble` above would be generated >> by GHC, with the corresponding instance >> >> ``` >> instance PointFamily Double where >> data #Point Double = PointDouble >> #x = x >> #y = x >> ``` >> >> If it's not possible to instantiate `#Point` with the provided type >> (for example because the type is not `UNPACK`able, e.g. >> `#Point (Maybe A)`), GHC would throw an error. >> >> Note that we can compile `distance` in its polymorphic version >> (as opposed to C++ templates, where template functions _must_ be >> instantiated at every use). The polymorphic `distance` would >> require a call to "virtual functions" `#x` and `#y`, as provided by >> the `PointFamily` dictionary. But if we use >> `INLINE` or `SPECIALIZE` pragmas the virtual calls to `#x` and `#y` >> would disappear, making this as efficient as if we were to define >> `distance` on the manually defined `PointDouble`. Compiler hints >> would be put in place to always inline functions using macro types, >> if possible. >> >> Note that the inlining is only important so that the `PointFamily` >> dictionary disappears, e.g. functions containing recursive >> helpers are fine, such as >> >> ``` >> {-# INLINE leftmost #-} >> leftmost :: forall a. (PointFamily a, Ord a) => [#Point a] -> #Point a >> leftmost [] = error "leftmost: no points" >> leftmost (p0 : ps0) = go p0 ps0 >> where >> go :: #Point a -> [#Point a] -> Point# a >> go candidate (p : ps) = >> if #x p < #x candidate >> then go p ps >> else go candidate ps >> ``` >> >> It might be worth considering throwing a warning when a top-level >> definition whose type contains a macro type cannot be inlined, since >> the main performance benefit of using macro types would be lost. >> >> We can define instances for these types as normal, for instance >> >> ``` >> instance (Show a, PointFamily a) => Show (#Point a) where >> {-# INLINE show #-} >> show pt = "Point{x = " ++ #x pt ++ ", y = " ++ #y pt ++ "}" >> ``` >> >> `deriving` support could also be added. >> >> ## Further ideas >> >> ### Hide or remove `PointFamily` from the user >> >> In the examples above `PointFamily` is manipulated explicitely >> (e.g. in the type signature for `distance`). >> In most cases the right constraint could be generated >> automatically by GHC, although I think direct access to the >> type class would be beneficial (history shows that direct >> access to these facilities is good, see upcoming explicit >> type applications). >> >> Maybe the type class associated to a macro type should not even >> exist -- for example we could simply represent `#Point` as a type >> family and treat construction and destruction as built-in syntax >> (the `#` prefix). >> >> ### Pattern matching >> >> Sugar could be added to pattern match, e.g. >> >> ``` >> foo :: Point# a -> ... >> distance (Point# x1 y1) = ... >> or >> dinstance Point#{..} = ... -- #x and #y are available >> ``` >> >> ### No "record types" limitation >> >> Instead of restricting ourselves to single-constructor records, >> we could simply generate >> >> ``` >> data Point a = Point a >> { x :: !a >> , y :: !a >> } >> >> class PointFamily a where >> data Point# a :: * >> destruct :: Point# a -> Point a >> construct :: Point a -> Point# a >> ``` >> >> However, I think it would be harder to guarantee the well-behavedness >> of the inlined functions if we had this intermediate type. I also >> don't think macro types would be very useful beyond polymorphic >> unboxed types. >> _______________________________________________ >> ghc-devs mailing list >> ghc-devs@haskell.org >> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs > _______________________________________________ > ghc-devs mailing list > ghc-devs@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs _______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
