[Haskell-cafe] Fwd: Memoization in Type Calculation
olshanskydr at gmail.com
Mon Jul 17 19:03:50 UTC 2017
Rahul, thanks! It is really simple!
2017-07-17 21:33 GMT+03:00 Rahul Muttineni <rahulmutt at gmail.com>:
> Hi Dmitry,
> 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.
> type family Fib (n::Nat) :: Nat where
> Fib n = GoFib 0 1 n
> type family GoFib (a :: Nat) (b :: Nat) (n :: Nat) where
> GoFib a _ 0 = a
> GoFib a b n = GoFib b (a + b) (n - 1)
> Hope that helps,
> On Mon, Jul 17, 2017 at 11:19 AM, Dmitry Olshansky <olshanskydr at gmail.com>
>> Hello, cafe!
>> I wonder is there some possibility to get Memoization in Type Calculation
>> (e.g. in closed Type Families)?
>> Can we make something more efficient for famous Fib function then
>> type family Fib (n::Nat) :: Nat where
>> Fib 1 = 1
>> Fib 2 = 1
>> Fib n = Fib (n-1) + Fib (n-2)
>> This Fib has obviously exponential calculation time and we need some
>> If it is impossible right now, maybe there is a ticket for this? It seems
>> to me very important things, no?
>> Probably in this case we can write TypeChecker Plugin, but it looks like
>> the common problem.
>> Best regards,
>> Haskell-Cafe mailing list
>> To (un)subscribe, modify options or view archives go to:
>> Only members subscribed via the mailman list are allowed to post.
> Rahul Muttineni
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe