<div>Thanks for the link, it seems a lot more complicated than I thought, but understandable since the Peano arithmetic is fully recursive, it may has the same performance issue even at value level. </div><div><br></div><div>This make type level Nat less attractive, I think. With TypeLits (assuming it doesn't have the slow performance issue) it is impossible to write something like:</div><div><br></div><div>add :: a -> b -> a+b</div><div>add a b = a+b</div><div><br></div><div>?</div><div><br></div><div>Thanks </div><div>Baojun<br><div class="gmail_quote"><div>On Mon, Apr 17, 2017 at 13:48 Will Yager <<a href="mailto:will.yager@gmail.com">will.yager@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div></div><div>As I recall from the Idris paper, the compiler has special knowledge about types like Nat. As you have noticed, actually computing peano numbers is quite slow. Take a look at <a href="https://hackage.haskell.org/package/ghc-typelits-natnormalise" target="_blank">https://hackage.haskell.org/package/ghc-typelits-natnormalise</a> for an example of "cheating" and embedding integers at the type level with special support. </div><div><br></div><div>Will </div></div><div><div><br>On Apr 17, 2017, at 3:34 PM, Baojun Wang <<a href="mailto:wangbj@gmail.com" target="_blank">wangbj@gmail.com</a>> wrote:<br><br></div><blockquote type="cite"><div><div>Hello cafe,<div><br></div><div>I tried to play with some type level natural numbers, and it seems type level function is quite slow, for instance:</div><div><br></div><div>(full source)</div><div><a href="https://gist.github.com/wangbj/5939aa7a30c3d756d98f5b5775e162a6" target="_blank">https://gist.github.com/wangbj/5939aa7a30c3d756d98f5b5775e162a6</a><br></div><div><br></div><div><div><font face="monospace">data Z</font></div><div><font face="monospace">data S n</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">class KnownNat n where</font></div><div><font face="monospace">  natSing :: n -> Integer</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">instance KnownNat Z where</font></div><div><font face="monospace">  natSing _ = 0</font></div><div><font face="monospace">instance KnownNat n => KnownNat (S n) where</font></div><div><font face="monospace">  natSing _ = 1 + natSing (undefined :: n)</font></div><div><font face="monospace"><br></font></div><div><font face="monospace">natVal :: KnownNat n => n -> Integer</font></div><div><font face="monospace">natVal = natSing</font></div></div><div><br></div><div>natSing doesn't seems to know how to optimize when KnownNat is very big (i.e: 10000), I tried Peano Add/Mul, and they are very slow to be really useful. Is there any ways to improve this? How fully dependent typed language such as Adga/Idris handle this, do they have the same performance issue?</div><div><br></div><div>Thanks</div><div>baojun</div></div>
</div></blockquote></div><div><blockquote type="cite"><div><span>_______________________________________________</span><br><span>Haskell-Cafe mailing list</span><br><span>To (un)subscribe, modify options or view archives go to:</span><br><span><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a></span><br><span>Only members subscribed via the mailman list are allowed to post.</span></div></blockquote></div></blockquote></div></div>