A demo of memorizing functions in ATS


#1

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.


#2

Please change

memo1

to

memo1<int, int>

Also, please delete the line "staload …/gorder_int.dats"On Sunday, July 10, 2016 at 9:15:10 PM UTC-4, 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.


#3

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
https://www.google.com/url?q=https%3A%2F%2Fglot.io%2Fsnippets%2Fegflakau5h&sa=D&sntz=1&usg=AFQjCNGtSHUrsoRyTWQSVUv0fTRp4Ue6dw,
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:


#4

Thanks, I forgot to save it after debug. Now it works.On Sunday, July 10, 2016 at 9:38:49 PM UTC-4, gmhwxi wrote:

Please change

memo1

to

memo1<int, int>

Also, please delete the line “staload …/gorder_int.dats”

On Sunday, July 10, 2016 at 9:15:10 PM UTC-4, 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.


#5

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

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:

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
https://www.google.com/url?q=https%3A%2F%2Fglot.io%2Fsnippets%2Fegflakau5h&sa=D&sntz=1&usg=AFQjCNGtSHUrsoRyTWQSVUv0fTRp4Ue6dw,
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


#6

I would say that a hash table (instead of a binary search tree) is more
suitable for this form of memoization.On Wednesday, July 13, 2016 at 9:29:42 AM UTC-4, Artyom Shalkhakov wrote:

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
https://www.google.com/url?q=https%3A%2F%2Fglot.io%2Fsnippets%2Fegflakau5h&sa=D&sntz=1&usg=AFQjCNGtSHUrsoRyTWQSVUv0fTRp4Ue6dw,
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