Skip to content

Instantly share code, notes, and snippets.

@gavinking
Last active September 7, 2017 15:21
Show Gist options
  • Save gavinking/8885535 to your computer and use it in GitHub Desktop.
Save gavinking/8885535 to your computer and use it in GitHub Desktop.
A useful generic function to memoize a function or method, or canonicalize a class. (Tested on Ceylon 1.1 - may not work in 1.0.)
"A generic function that produces a memoized version
of the given [[function|fun]]. Works for any function
arity."
Callable<Return,Args> memoize<Return,Args>(Callable<Return,Args> fun)
given Args satisfies Anything[] {
value cache = HashMap<Args,Return&Object|Finished>();
function callFun(Args args) {
//we'll use finished as a convenient
//unit value to represent the case
//that the function returned null
if (exists result = cache[args]) {
if (!is Finished result) {
return result;
}
else {
assert (is Return null);
return null;
}
}
else {
value result = fun(*args);
cache.put(args, result else finished);
return result;
}
}
return flatten(callFun);
}
"Example class that has a [[memoized|memoize]] method."
class Store(String* strings) {
"The expensive method to be memoized."
function internalCount(Integer integer, String pattern) {
print("calling");
return strings[integer]?.inclusions(pattern) else {};
}
"The reference to the memoized function."
shared {Integer*} count(Integer integer, String pattern);
count = memoize(internalCount);
}
void testStore() {
value store = Store("hello", "world", "goodbye");
print(store.count(0, "ll"));
print(store.count(0, "ll"));
print(store.count(0, "ll"));
print(store.count(1, "ll"));
print(store.count(1, "ll"));
print(store.count(2, "o"));
print(store.count(2, "o"));
}
"A class to be canonicalized."
class Canonical(String string) {
print("instantiating " + string);
}
void testCanonical() {
Canonical newCanonical(String string);
newCanonical = memoize(Canonical);
assert (newCanonical("hello")==newCanonical("hello"));
assert (newCanonical("hello")!=newCanonical("bye"));
}
@ePaul
Copy link

ePaul commented Nov 1, 2015

That needs an import of HashMap, I think.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment