<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><div>On Nov 11, 2015, at 10:43 AM, Dmitry Olshansky <<a href="mailto:olshanskydr@gmail.com">olshanskydr@gmail.com</a>> wrote:</div><div><br class="Apple-interchange-newline"><blockquote type="cite"><div dir="ltr">There are some questions / notes:<div><br><div>1. Could ghc use reduced "vanila types" for calculation with definition stored somewhere specially for error messages?</div></div></div></blockquote><div><br></div><div>Perhaps. But I'm not yet convinced that the current treatment of type synonyms is causing your slowdown.</div><br><blockquote type="cite"><div dir="ltr"><div><div><br></div><div>2.  I didn't expect that type families can be without any parameters. But they really can. So instead of</div></div><div><span style="font-size:12.8px">> type T2 = T1 Int Int</span><br></div><div><span style="font-size:12.8px">I can write </span></div><div><span style="font-size:12.8px">> type family T2 where T2 = T1 Int Int</span><br></div><div><span style="font-size:12.8px">which is rather strange though.</span></div><div><span style="font-size:12.8px">Moreover in this case ghc asks me for TypeFamilies and UndecidableInstances.</span><br></div><div><span style="font-size:12.8px">In my scenario such code should write library-user. So including these (especially </span><span style="font-size:12.8px">UndecidableInstances) extensions in his/her code is Undesirable.</span></div></div></blockquote><div><br></div><div>If your clients will have to include fancy type-level definitions, they will probably need UndecidableInstances. We're open to improving the termination checker if you have a good approach to how. :)</div><br><blockquote type="cite"><div dir="ltr"><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">3. For type families more natural to have parameters but in this case we often can't reduce it deeply I suppose. </span></div><div><span style="font-size:12.8px">Short simple example:</span></div><div><span style="font-size:12.8px">type family L a b where </span></div><div><span style="font-size:12.8px">  L a () = (a,())</span></div><div><span style="font-size:12.8px">  L a (b,c) = (a,(b,c))</span></div><div><span style="font-size:12.8px">type T1 = L Int ()</span></div><div>type T2 = L Int T1</div><div>type T3 = L Int T2</div><div>type T3_Char = L Char T2</div><div>and so on...<br></div></div></blockquote><div><br></div><div>I'm not sure what you're getting at here. Type synonyms and type families should behave the same (other than in error messages). Do you have an example where the compile time with type synonyms is demonstrably slower than the time with type families?</div><br><blockquote type="cite"><div dir="ltr"><div><br></div><div><br></div><div><span style="font-size:12.8px">Well, about my "complicated type-level program" now.  I start to play/work with well-known "named-fields" problem. My code is <a href="https://github.com/odr/pers">here</a>.</span></div></div></blockquote><div><br></div><div>Thanks for sharing your code. But it's very hard to understand what to look at here. I see in your "user application" link below that you have times. Are these compile times? Under what tests? Which version of GHC? We need to be really concrete so that I (or some other GHC dev) can reproduce what you're experiencing.</div><div><br></div><div>Thanks!</div><div>Richard</div><br><blockquote type="cite"><div dir="ltr"><div><span style="font-size:12.8px">I hoped to find decision with properties:</span></div><div><span style="font-size:12.8px">- O(log n) time to get field from record by name</span></div><div><span style="font-size:12.8px">- record construction independent from order of fields definitions</span></div><div><span style="font-size:12.8px">- no TH preferrable, some TH possible</span></div><div><span style="font-size:12.8px">- projections and joins are desirable</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">I tried to implement it using "very-well balanced tree" (I don't know the right name) on type level. </span></div><div><span style="font-size:12.8px">This is a binary search (by name) tree with count of left items is the same or one more than on the right side (for each subtree).</span></div><div><span style="font-size:12.8px">The problem is construction. I realized it with <a href="https://github.com/odr/pers/blob/master/src/NamedBTree.hs">FunDeps</a> and  with <a href="https://github.com/odr/pers/blob/master/src/NamedBTree2.hs">TF</a>. User should write </span></div><div><span style="font-size:12.8px">> type Rec = () <+ "a":>Int <+ "b":>Char <+ "c":>String</span></div><div><span style="font-size:12.8px">> rec = () <+ (V "c" :: </span><span style="font-size:12.8px">"c":>String)</span><span style="font-size:12.8px"> <+ (V 1 :: "a":>Int) <+ (V 'b' :: "b":>Char)</span></div><div><span style="font-size:12.8px">or</span></div><div><span style="font-size:12.8px">> rec = () <+ (V "c" :: </span><span style="font-size:12.8px">"c":>String)</span><span style="font-size:12.8px"> <+ (V 1 :: "a":>Int) <+ (V 'b' :: "b":>Char) :: Rec</span></div><div><span style="font-size:12.8px">and got </span></div><div><span style="font-size:12.8px">rec = (((),V 1,()),V'b',((),V "c")) :: (((),"a":>Int,()),"b":>Char,((),"c":>String,()) </span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">(Constructions like (V 1 :: "a" :> Int) rather ugly. Any ideas are welcomed... Perhaps some TH?)</span></div><div><br></div><div><span style="font-size:12.8px">But compile time for <a href="https://github.com/odr/pers/blob/master/app/Main.hs">user application</a> is absolutely blocked this idea!</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">I tried also to make a type-level <a href="https://github.com/odr/pers/blob/master/src/List.hs">sorted list</a> but it is also too complicated for ghc.</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">I didn't check time with no-parameters-TF as you suggested. I will.</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px">Best regards,</span><br></div><div><span style="font-size:12.8px">Dmitry</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px"><br></span></div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-11-11 16:43 GMT+03:00 Richard Eisenberg <span dir="ltr"><<a href="mailto:eir@cis.upenn.edu" target="_blank">eir@cis.upenn.edu</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Users often introduce so-called "vanilla" type synonyms (with `type` but not `type instance`) to be helpful abbreviations in code. As such, GHC actually takes quite a bit of effort *not* to expand these, so that error messages can report the synonyms instead of their expansions. On the other hand, type /families/ tend to be used for type-level computation. So GHC has decided to try to reduce all type families, while preserving all type synonyms. This is all a bit arbitrary, and it should have no end-user consequence except for error messages and, perhaps, performance.<br>
<br>
If you have a complicated type-level program whose compile time is increasing faster than the program size, we'd love to know about it. We (GHC devs) want type-level computation to be efficient!<br>
<br>
Thanks,<br>
Richard<br>
<div><div class="h5"><br>
On Nov 10, 2015, at 3:59 PM, Dmitry Olshansky <<a href="mailto:olshanskydr@gmail.com">olshanskydr@gmail.com</a>> wrote:<br>
<br>
> Hello!<br>
><br>
> It seems that types without parameters are not reduced in ghc unlike CAFs.<br>
><br>
> I.e. if we have<br>
><br>
> type T1 a b = ...<br>
> type T2 = T1 Int Int<br>
><br>
> than T2 will be calculated on each utilization.<br>
><br>
> Is my statement correct? If so, why is it?<br>
> With complicated type-calculation compile time is growing too fast.<br>
><br>
> Best regards,<br>
> Dmitry<br>
><br>
><br>
><br>
</div></div>> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
> <a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
<br>
</blockquote></div><br></div>
</blockquote></div><br></body></html>