A demo of memorizing functions in ATS

[Steinway Wu]

Hi, 

In a practice, I encountered a problem of memorizing functions. Given a function `f`, a memorized version of `f`, called `memo f` should cache the results of `f` applying on some `input`. I tried a demo here https://glot.io/snippets/egflakau5h, which shows a generic implementation of the function `memo0` (for memorizing a function of no arguments) and `memo1` (for memorizing a function with one argument). Comments are welcomed.

[gmhwxi]

Please change

memo1

to

memo1<int, int>

Also, please delete the line "staload .../gorder_int.dats"

[Steinway Wu]

Thanks, I forgot to save it after debug. Now it works. 

[Artyom Shalkhakov]

Hello Steinway,

On Monday, July 11, 2016 at 7:15:10 AM UTC+6, Steinway Wu wrote:

Hi, 

In a practice, I encountered a problem of memorizing functions. Given a function `f`, a memorized version of `f`, called `memo f` should cache the results of `f` applying on some `input`. I tried a demo here https://glot.io/snippets/egflakau5h, which shows a generic implementation of the function `memo0` (for memorizing a function of no arguments) and `memo1` (for memorizing a function with one argument). Comments are welcomed.

Thanks for the example! Reminds of hash-consing technique (say you memoize unary constructors for a datatype).

I've changed the code a tiny bit to make the [memo1] function return type fully generic. Here's the code:

https://glot.io/snippets/egid4pae37

[gmhwxi]

I would say that a hash table (instead of a binary search tree) is more
suitable for this form of memoization.

[gmhwxi]

Memoization is a very interesting topic. Here is an example involving
the handling of a recursively defined function:

https://github.com/githwxi/ATS-Postiats/blob/master/doc/EXAMPLE/MISC/memoization.dats

I will try to write about it once I get some free time.

On Wednesday, July 13, 2016 at 9:29:42 AM UTC-4, Artyom Shalkhakov wrote: