<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><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><div><span style="font-size:12.8px">> type family T2 where T2 = T1 Int Int</span><br></div></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><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><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><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><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><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>