Actually upon reflection, this does appear to help with implementing some things in my code with a much reduced unsafeCoerce count, though it remains orthogonal to the issue of how to lift these things through third-party types that I raised above.<div>
<br></div><div>-Edward<br><br><div class="gmail_quote">On Mon, Jan 14, 2013 at 5:40 PM, Edward Kmett <span dir="ltr"><<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
It sounds like the solution you are proposing then is to an issue largely orthogonal to the one I'm talking about.<div><br></div><div>As far as I can tell, I derive no immediate benefit from this version.</div><div class="HOEnZb">
<div class="h5"><div><br>
</div><div>-Edward<br><br><div class="gmail_quote">On Mon, Jan 14, 2013 at 4:09 PM, Simon Peyton-Jones <span dir="ltr"><<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div lang="EN-GB" link="blue" vlink="purple">
<div>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d">If you are worrying about #1496, don’t worry; we must fix that, and the fix will apply to newtype wrappers.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"><br>
If you are worrying about something else, can you articulate what the something else is?<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d">I don’t want to involve type classes, nor Functor. We don’t even have a good way to say “is a functor of its second type argument” for a type constructor of
three arguments.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d">Simon<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Verdana","sans-serif";color:#1f497d"><u></u> <u></u></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0cm 0cm 0cm 4.0pt">
<div>
<div style="border:none;border-top:solid #b5c4df 1.0pt;padding:3.0pt 0cm 0cm 0cm">
<p class="MsoNormal"><b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif"">From:</span></b><span lang="EN-US" style="font-size:10.0pt;font-family:"Tahoma","sans-serif""> Edward Kmett [mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>]
<br>
<b>Sent:</b> 14 January 2013 18:39<br>
<b>To:</b> Simon Peyton-Jones<br>
<b>Cc:</b> GHC users<br>
<b>Subject:</b> Re: Newtype wrappers<u></u><u></u></span></p>
</div>
</div><div><div>
<p class="MsoNormal"><u></u> <u></u></p>
<p class="MsoNormal">Many of us definitely care. =)<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">The main concern that I would have is that the existing solutions to this problem could be implemented while retaining SafeHaskell, and I don't see how a library that uses this can ever recover its SafeHaskell guarantee.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Here is a straw man example of a solution that permits SafeHaskell in the resulting code that may be useful in addition to or in lieu of your proposed approach:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">We could extend Data.Functor with an fmap# operation that was only, say, exposed via Data.Functor.Unsafe:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">{-# LANGUAGE Unsafe, MagicHash #-}<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">module Data.Functor.Unsafe where<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">class Functor f where<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> fmap# :: (a -> b) -> f a -> f b<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> fmap :: (a -> b) -> f a -> f b<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> (<$) :: b -> f a -> f b<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> fmap# = \f -> \fa -> fa `seq` fmap f p<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Then we flag Data.Functor as Trustworthy and export just the safe subset:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">{-# LANGUAGE Trustworthy #-}<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">module Data.Functor (Functor(fmap,(<$))) where<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">import Data.Functor.Unsafe<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">then fmap# from Data.Functor.Unsafe is allowed to be fmap# _ = unsafeCoerce for any Functor that doesn't perform GADT-like interrogation of its argument (this could be assumed automatically in DeriveFunctor, which can't handle those cases
anyways!)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Then any user who wants to enable a more efficient fmap for fmapping over his data type with a newtype instantiates fmap# for his Functor. They'd have to claim Trustworthy (or use the enhanced DeriveFunctor), to discharge the obligation
that they aren't introducing an unsafeCoerce that is visible to the user. (After all the user has to import another Unsafe module to get access to fmap# to invoke it.)<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Finally then code that is willing to trust other trustworthy code can claim to be Trustworthy in turn, import Data.Functor.Unsafe and use fmap# for newtypes and impossible arguments:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">{-# LANGUAGE Trustworthy #-}<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">module Data.Void where<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">import Data.Functor.Unsafe<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">newtype Void = Void Void deriving Functor<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">absurd :: Void -> a<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">absurd (Void a) = absurd a<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">vacuous :: Functor f => f Void -> f a<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">vacuous = fmap# absurd<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">This becomes valuable when data types like Void are used to mark the absence of variables in a syntax tree, which could be quite large.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Currently we have to fmap absurd over the tree, paying an asymptotic cost for not using (forall a. Expr a) or some newtype wrapped equivalent as our empty-expression type.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">This would dramatically improve the performance of libraries like bound which commonly use constructions like Expr Void.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Its safety could be built upon by making another class for tracking newtypes etc so we can know whats safe to pass to fmap#, and you might be able to spot opportunities to rewrite an explicit fmap of something that is a `cast` in the core
to a call to fmap#.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">-Edward<u></u><u></u></p>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<p class="MsoNormal">On Mon, Jan 14, 2013 at 1:09 PM, Simon Peyton-Jones <<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>> wrote:<u></u><u></u></p>
<div>
<div>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">Friends</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">I’d like to propose a way to “promote” newtypes over their enclosing type. Here’s the writeup</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">
<a href="http://hackage.haskell.org/trac/ghc/wiki/NewtypeWrappers" target="_blank">
http://hackage.haskell.org/trac/ghc/wiki/NewtypeWrappers</a></span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">Any comments? Below is the problem statement, taken from the above page.</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">I’d appreciate</span><u></u><u></u></p>
<p><span style="font-family:Symbol">·</span><span style="font-size:7.0pt">
</span><span style="font-family:"Verdana","sans-serif"">A sense of whether you care. Does this matter?</span><u></u><u></u></p>
<p><span style="font-family:Symbol">·</span><span style="font-size:7.0pt">
</span><span style="font-family:"Verdana","sans-serif"">Improvements to the design I propose</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif"">Simon</span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
<p class="MsoNormal"><b><span style="font-family:"Verdana","sans-serif"">The problem</span></b><u></u><u></u></p>
<p>Suppose we have <u></u><u></u></p>
<pre>newtype Age = MkAge Int<u></u><u></u></pre>
<p>Then if <tt><span style="font-size:10.0pt">n :: Int</span></tt>, we can convert
<tt><span style="font-size:10.0pt">n</span></tt> to an <tt><span style="font-size:10.0pt">Age</span></tt> thus:
<tt><span style="font-size:10.0pt">MkAge n :: Age</span></tt>. Moreover, this conversion is a type conversion only, and involves no runtime instructions whatsoever. This cost model -- that newtypes are free -- is important to Haskell programmers, and encourages
them to use newtypes freely to express type distinctions without introducing runtime overhead.
<u></u><u></u></p>
<p>Alas, the newtype cost model breaks down when we involve other data structures. Suppose we have these declarations
<u></u><u></u></p>
<pre>data T a = TLeaf a | TNode (Tree a) (Tree a)<u></u><u></u></pre>
<pre>data S m a = SLeaf (m a) | SNode (S m a) (S m a)<u></u><u></u></pre>
<p>and we have these variables in scope <u></u><u></u></p>
<pre>x1 :: [Int]<u></u><u></u></pre>
<pre>x2 :: Char -> Int<u></u><u></u></pre>
<pre>x3 :: T Int<u></u><u></u></pre>
<pre>x4 :: S IO Int<u></u><u></u></pre>
<p>Can we convert these into the corresponding forms where the <tt><span style="font-size:10.0pt">Int</span></tt> is replaced by
<tt><span style="font-size:10.0pt">Age</span></tt>? Alas, not easily, and certainly not without overhead.
<u></u><u></u></p>
<ul type="disc">
<li class="MsoNormal">
For <tt><span style="font-size:10.0pt">x1</span></tt> we can write <tt><span style="font-size:10.0pt">map MkAge x1 :: [Age]</span></tt>. But this does not follow the newtype cost model: there will be runtime overhead from executing the
<tt><span style="font-size:10.0pt">map</span></tt> at runtime, and sharing will be lost too. Could GHC optimise the
<tt><span style="font-size:10.0pt">map</span></tt> somehow? This is hard; apart from anything else, how would GHC know that
<tt><span style="font-size:10.0pt">map</span></tt> was special? And it it gets worse.
<u></u><u></u></li></ul>
<ul type="disc">
<li class="MsoNormal">
For <tt><span style="font-size:10.0pt">x2</span></tt> we'd have to eta-expand: <tt>
<span style="font-size:10.0pt">(\y -> MkAge (x2 y)) :: Char -> Age</span></tt>. But this isn't good either, because eta exapansion isn't semantically valid (if
<tt><span style="font-size:10.0pt">x2</span></tt> was bottom, <tt><span style="font-size:10.0pt">seq</span></tt> could distinguish the two). See
<a href="http://hackage.haskell.org/trac/ghc/ticket/7542" title="bug: GHC doesn't optimize (strict) composition with id (new)" target="_blank">
#7542</a> for a real life example. <u></u><u></u></li></ul>
<ul type="disc">
<li class="MsoNormal">
For <tt><span style="font-size:10.0pt">x3</span></tt>, we'd have to map over <tt>
<span style="font-size:10.0pt">T</span></tt>, thus <tt><span style="font-size:10.0pt">mapT MkAge x3</span></tt>. But what if
<tt><span style="font-size:10.0pt">mapT</span></tt> didn't exist? We'd have to make it. And not all data types have maps.
<tt><span style="font-size:10.0pt">S</span></tt> is a harder one: you could only map over S-values if
<tt><span style="font-size:10.0pt">m</span></tt> was a functor. There's a lot of discussion abou this on
<a href="http://hackage.haskell.org/trac/ghc/ticket/2110" title="feature request: Rules to eliminate casted id's (new)" target="_blank">
#2110</a>. <u></u><u></u></li></ul>
<p class="MsoNormal"><span style="font-family:"Verdana","sans-serif""> </span><u></u><u></u></p>
</div>
</div>
<p class="MsoNormal" style="margin-bottom:12.0pt"><br>
_______________________________________________<br>
Glasgow-haskell-users mailing list<br>
<a href="mailto:Glasgow-haskell-users@haskell.org" target="_blank">Glasgow-haskell-users@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/glasgow-haskell-users" target="_blank">http://www.haskell.org/mailman/listinfo/glasgow-haskell-users</a><u></u><u></u></p>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
</div></div></div>
</div>
</div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>