[Haskell-cafe] Memoization in Type Calculation

[Rahul Muttineni]

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,
Rahul

On Mon, Jul 17, 2017 at 11:19 AM, Dmitry Olshansky <olshanskydr at gmail.com>
wrote:

> 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
> memoization.
>
> 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,
> Dmitry
>
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
>



-- 
Rahul Muttineni
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20170717/44fca236/attachment.html>