1 (* [memoize (hash, eq, f)] builds a memoizing version of the function [f],
 2    using an internal hash table based on the provided hash and equality
 3    functions. *)
 4 
 5 (* If [f] has type [a -> b], the types [a] and [b] must be duplicable,
 6    because arguments and results will be stored in the internal hash
 7    table. *)
 8 
 9 (* The function [f] may have a side effect, represented by [s]. This must be
10    used with caution: it often does not make sense to memoize a function that
11    has a side effect. Furthermore, when it does make sense, one might prefer
12    to hide the side effect before applying [memoize], so [memoize] is applied
13    to a function that does not require a permission. The parameter [s] is
14    useful only when memoizing a function that has an intentionally non-hidden
15    side effect. *)
16 
17 val memoize:
18   [a, b, s : perm]
19   duplicable a => duplicable b =>
20   (hash: a -> int, eq: (a, a) -> bool, f: (a | s) -> b) ->
21   (a | s) -> b
22 
23 (* Now, a memoizing fixpoint combinator. Here, the argument [f] is not a
24    closed function, but an open recursive function, i.e., it is parameterized
25    over [self]. So, [f] should have type [(self: a -> b, x: a) -> y: b]. *)
26 
27 (* Actually, we require [f] to have a slightly more general type, which is
28    parametric in an unknown permission [p]. Thus, we tell our client that
29    [self] may have a side effect, and that (of course) we expect the
30    application of [f] to [self] to have the same side effect. Incidentally,
31    note that this type prevents [f] from storing [self] and re-using after
32    [f] has returned! So, we are telling [f], ``you can use [self] now if
33    you wish, but you are not allowed to use it later''. *)
34 
35 val fix:
36   [a, b]
37   duplicable a => duplicable b =>
38   (
39     hash: a -> int,
40     eq: (a, a) -> bool,
41     f: [p : perm] ((a | p) -> b, a | p) -> b
42   ) ->
43   a -> b
44