26th July 2010, 04:14 pm
In Non-strict memoization, I sketched out a means of memoizing non-strict functions.
I gave the essential insight but did not show the details of how a nonstrict memoization library comes together.
In this new post, I give details, which are a bit delicate, in terms of the implementation described in Elegant memoization with higher-order types.
Near the end, I run into some trouble with regular data types, which I don’t know how to resolve cleanly and efficiently.
Continue reading ‘Details for non-strict memoization, part 1’ »
21st July 2010, 07:41 am
Memoization incrementally converts functions into data structures.
It pays off when a function is repeatedly applied to the same arguments and applying the function is more expensive than accessing the corresponding data structure.
In lazy functional memoization, the conversion from function to data structure happens all at once from a denotational perspective, and incrementally from an operational perspective.
See Elegant memoization with functional memo tries and Elegant memoization with higher-order types.
As Ralf Hinze presented in Generalizing Generalized Tries, trie-based memoization follows from three simple isomorphisms involving functions types:
which correspond to the familiar laws of exponents
When applied as a transformation from left to right, each law simplifies the domain part of a function type.
Repeated application of the rules then eliminate all function types or reduce them to functions of atomic types.
These atomic domains are eliminated as well by additional mappings, such as between a natural number and a list of bits (as in patricia trees).
Algebraic data types corresponding to sums of products and so are eliminated by the sum and product rules.
Recursive algebraic data types (lists, trees, etc) give rise to correspondingly recursive trie types.
So, with a few simple and familiar rules, we can memoize functions over an infinite variety of common types.
Have we missed any?
Yes.
What about functions over functions?
Edits:
- 2010-07-22: Made the memoization example polymorphic and switched from pairs to lists. The old example accidentally coincided with a specialized version of
trie itself.
Continue reading ‘Memoizing higher-order functions’ »
20th July 2010, 08:48 pm
A while back, I got interested in functional memoization, especially after seeing some code from Spencer Janssen using the essential idea of Ralf Hinze’s paper Generalizing Generalized Tries.
The blog post Elegant memoization with functional memo tries describes a library, MemoTrie, based on both of these sources, and using associated data types.
I would have rather used associated type synonyms and standard types, but I couldn’t see how to get the details to work out.
Recently, while playing with functor combinators, I realized that they might work for memoization, which they do quite nicely.
This blog post shows how functor combinators lead to an even more elegant formulation of functional memoization.
The code is available as part of the functor-combo package.
The techniques in this post are not so much new as they are ones that have recently been sinking in for me.
See Generalizing Generalized Tries, as well as Generic programming with fixed points for mutually recursive datatypes.
Continue reading ‘Elegant memoization with higher-order types’ »
13th July 2010, 06:46 pm
I’ve written a few posts about functional memoization.
In one of them, Luke Palmer commented that the memoization methods are correct only for strict functions, which I had not noticed before.
In this note, I correct this flaw, extending correct memoization to non-strict functions as well.
The semantic notion of least upper bound (which can be built of unambiguous choice) plays a crucial role.
Edits:
- 2010-07-13: Fixed the non-strict memoization example to use an argument of
undefined (⊥) as intended.
- 2010-07-23: Changed spelling from “nonstrict” to the much more popular “non-strict”.
Continue reading ‘Non-strict memoization’ »
18th February 2009, 06:34 pm
I’ve just finished a draft of a paper called Denotational design with type class morphisms, for submission to ICFP 2009.
The paper is on a theme I’ve explored in several posts, which is semantics-based design, guided by type class morphisms.
I’d love to get some readings and feedback.
Pointers to related work would be particularly appreciated, as well as what’s unclear and what could be cut.
It’s an entire page over the limit, so I’ll have to do some trimming before submitting.
The abstract:
Type classes provide a mechanism for varied implementations of standard
interfaces. Many of these interfaces are founded in mathematical
tradition and so have regularity not only of types but also of
properties (laws) that must hold. Types and properties give strong
guidance to the library implementor, while leaving freedom as well. Some
of the remaining freedom is in how the implementation works, and some
is in what it accomplishes.
To give additional guidance to the what, without impinging on the
how, this paper proposes a principle of type class morphisms (TCMs),
which further refines the compositional style of denotational
semantics. The TCM idea is simply that the instance’s meaning is the
meaning’s instance. This principle determines the meaning of each type
class instance, and hence defines correctness of implementation. In some
cases, it also provides a systematic guide to implementation, and in
some cases, valuable design feedback.
The paper is illustrated with several examples of type, meanings, and
morphisms.
You can get the paper and see current errata here.
The submission deadline is March 2, so comments before then are most helpful to me.
Enjoy, and thanks!
19th October 2008, 05:26 pm
A previous post described a data type of functional linear maps.
As Andy Gill pointed out, we had a heck of a time trying to get good performance.
This note describes a new representation that is very simple and much more efficient.
It’s terribly obvious in retrospect but took me a good while to stumble onto.
The Haskell module described here is part of the vector-space library (version 0.5 or later) and requires ghc version 6.10 or better (for associated types).
Edits:
- 2008-11-09: Changed remarks about versions. The vector-space version 0.5 depends on ghc 6.10.
- 2008-10-21: Fixed the vector-space library link in the teaser.
Continue reading ‘Simpler, more efficient, functional linear maps’ »
15th October 2008, 06:18 pm
The post Elegant memoization with functional memo tries showed a simple type of search tries and their use for functional memoization of functions.
This post provides some composition tools for memo tries, whose definitions are inevitable, in that they are determined by the principle presented in Simplifying semantics with type class morphisms.
Continue reading ‘Composing memo tries’ »
