[Haskell-cafe] Memoization in Type Calculation
rahulmutt at gmail.com
Mon Jul 17 18:33:35 UTC 2017
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe