<div dir="ltr">Hi Dmitry,<div><br></div><div>You can effectively think of the type-level language of Haskell as a strict functional language with almost no syntactic sugar, and recursion is the *only* way of getting the behaviour of a loop. The best you can do to improve the performance of that type family is to write it in tail-recursive form using a helper function and which will make the type family reduction look more linear vs a tree like it is now and make it easier for the type checker to quickly spit out the result.</div><div><br></div><div><div style="font-size:13px">type family Fib (n::Nat) :: Nat where<br></div><div style="font-size:13px"><div>  Fib n = GoFib 0 1 n</div><div><br></div><div>type family GoFib (a :: Nat) (b :: Nat) (n :: Nat) where<br></div><div>  GoFib a _ 0 = a</div><div>  GoFib a b n = GoFib b (a + b) (n - 1)</div></div></div><div><br></div><div>Hope that helps,</div><div>Rahul</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jul 17, 2017 at 11:19 AM, Dmitry Olshansky <span dir="ltr"><<a href="mailto:olshanskydr@gmail.com" target="_blank">olshanskydr@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hello, cafe!<div><br></div><div>I wonder is there some possibility to get Memoization in Type Calculation (e.g. in closed Type Families)?</div><div><br></div><div>Can we make something more efficient for famous Fib function then</div><div><br></div><div>type family Fib (n::Nat) :: Nat where<br></div><div><div>  Fib 1 = 1</div><div>  Fib 2 = 1</div><div>  Fib n = Fib (n-1) + Fib (n-2)</div></div><div><br></div><div>This Fib has obviously exponential calculation time and we need some memoization.</div><div><br></div><div>If it is impossible right now, maybe there is a ticket for this? It seems to me very important things, no?</div><div><br></div><div>Probably in this case we can write TypeChecker Plugin, but it looks like the common problem.</div><div><br></div><div>Best regards,</div><div>Dmitry</div><div><br></div><div><br></div><div><br></div></div>
<br>______________________________<wbr>_________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/haskell-<wbr>cafe</a><br>
Only members subscribed via the mailman list are allowed to post.<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature" data-smartmail="gmail_signature">Rahul Muttineni</div>
</div>