[Haskell-cafe] Fwd: Memoization in Type Calculation

[Dmitry Olshansky]

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,
> 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/853c69b8/attachment.html>