15th November 2008, 05:09 pm
This post is part four of the zip folding series inspired by Max Rabkin’s Beautiful folding post.
I meant to write one little post, but one post turned into four.
When I sense that something can be made simpler/clearer, I can’t leave it be.
To review:
- Part One related Max’s data representation of left folds to type class morphisms, a pattern that’s been steering me lately toward natural (inevitable) design of libraries.
- Part Two simplified that representation to help get to the essence of zipping, and in doing so lost the expressiveness necessary to define
Functorand Applicative instaces.
- Part Three proved the suitability of the zipping definitions in Part Two.
This post shows how to restore the Functor and Applicative (very useful composition tools) to folds but does so in a way that leaves the zipping functionality untouched.
This new layer is independent of folding and can be layered onto any zippable type.
You can get the code described below.
Continue reading ‘Enhancing a Zip’ »
15th November 2008, 01:30 pm
The post More beautiful fold zipping showed a formulation of left-fold zipping, simplified from the ideas in Max Rabkin’s Beautiful folding. I claimed that the semantic functions are the inevitable (natural) ones in that they preserve zipping stucture.
This post gives the promised proofs.
Continue reading ‘Proofs for left fold zipping’ »
14th November 2008, 11:24 pm
My previous post, Another lovely example of type class morphisms, placed some standard structure around Max Rabkin’s Beautiful folding, using type class morphisms to confirm that the Functor and Applicative instances agreed with their inevitable meanings.
In the process of working out the Applicative case, I realized the essence of fold zipping was getting a bit obscured.
This post simplifies Max’s Fold data type a bit and shows how to zip strict left folds in the simpler setting.
You can get the code described here.
Edits:
- 2008-11-15: I renamed the
Pair and Pair' classes to Zip and Zip'.
Continue reading ‘More beautiful fold zipping’ »
13th November 2008, 10:20 pm
I read Max Rabkin’s recent post Beautiful folding with great excitement.
He shows how to make combine multiple folds over the same list into a single pass, which can then drastically reduce memory requirements of a lazy functional program.
Max’s trick is giving folds a data representation and a way to combine representations that corresponds to combining the folds.
Peeking out from behind Max’s definitions is a lovely pattern I’ve been noticing more and more over the last couple of years, namely type class morphisms.
Continue reading ‘Another lovely example of type class morphisms’ »
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’ »
19th October 2008, 05:23 pm
A basis B of a vector space V is a subset B of V, such that the elements of B are linearly independent and span V.
That is to say, every element (vector) of V is a linear combination of elements of B, and no element of B is a linear combination of the other elements of B.
Moreover, every basis determines a unique decomposition of any member of V into coordinates relative to B.
This post gives a simple Haskell implementation for a canonical basis of a vector space, and a means of decomposing vectors into coordinates.
It uses indexed type families (associated types), and is quite general, despite its simplicity.
The Haskell module described here is part of the vector-space library (version 0.4 or later), which available on Hackage and a darcs repository.
See the wiki page, interface documentation, and source code.
The library version described below (0.5 or later) relies on ghc 6.10.
Edits:
- 2008-11-09: Tweaked comment above about version.
- 2008-02-09: just fiddling around
Continue reading ‘Vector space bases via type families’ »
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’ »