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.
- 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
- Part Three proved the suitability of the zipping definitions in Part Two.
This post shows how to restore the
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.
- 2009-02-15: Simplified
WithCont, collapsing two type parameters into one. Added functor comment about
Continue reading ‘Enhancing a Zip’ »
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’ »
Lately I’ve been playing again with parametric surfaces in Haskell.
Surface rendering requires normals, which can be constructed from partial derivatives, which brings up automatic differentiation (AD).
Playing with some refactoring, I’ve stumbled across a terser, lovelier formulation for the derivative rules than I’ve seen before.
- 2008-05-08: Added source files: NumInstances.hs and Dif.hs.
- 2008-05-20: Changed some variable names for clarity and consistency. For instance,
x@(D x0 x') instead of
p@(D x x').
- 2008-05-20: Removed extraneous
Fractional constraint in the
Floating instance of
Continue reading ‘Beautiful differentiation’ »
When I first started playing with functional reactivity in Fran and its predecessors, I didn’t realize that much of the functionality of events and reactive behaviors could be packaged via standard type classes.
Then Conor McBride & Ross Paterson introduced us to applicative functors, and I remembered using that pattern to reduce all of the lifting operators in Fran to just two, which correspond to
(< *>) in the
So, in working on a new library for functional reactive programming (FRP), I thought I’d modernize the interface to use standard type classes as much as possible.
While spelling out a precise (denotational) semantics for the FRP instances of these classes, I noticed a lovely recurring pattern:
The meaning of each method corresponds to the same method for the meaning.
In this post, I’ll give some examples of this principle and muse a bit over its usefulness.
For more details, see the paper Simply efficient functional reactivity.
Another post will start exploring type class morphisms and type composition, and ask questions I’m wondering about.
Continue reading ‘Simplifying semantics with type class morphisms’ »
I submitted a paper Simply efficient functional reactivity to ICFP 2008.
Functional reactive programming (FRP) has simple and powerful semantics, but has resisted efficient implementation. In particular, most past implementations have used demand-driven sampling, which accommodates FRP’s continuous time semantics and fits well with the nature of functional programming. Consequently, values are wastefully recomputed even when inputs don’t change, and reaction latency can be as high as the sampling period.
This paper presents a way to implement FRP that combines data- and demand-driven evaluation, in which values are recomputed only when necessary, and reactions are nearly instantaneous. The implementation is rooted in a new simple formulation of FRP and its semantics and so is easy to understand and reason about.
On the road to efficiency and simplicity, we’ll meet some old friends (monoids, functors, applicative functors, monads, morphisms, and improving values) and make some new friends (functional future values, reactive normal form, and concurrent “unambiguous choice”).
In Functional reactive partner dancing, I mentioned that (a) the partially applied leading and following types have boilerplate
Applicative instances, and (b) the leading type corresponds to varying (reactive) values. Today I realized that those boilerplate instances are not very useful, and that they do not correspond to the
Applicative instance of
Reactive. In this post, I give a useful
Applicative instance that does correspond to the
Reactive instance. The instance definition is expressed in terms of the pair editor bot shown at the end of the “dancing” post, which seems to have a variety of applications.
Applicative instance has one awkward aspect that suggests a tweak to the formulation of leading. I give simplified versions of pair editing and
Applicative for the revised type. This change is in version 0.1 of the Bot libary.
Edit 2008-02-15: added FRP tags; prose tweak.
Continue reading ‘Applicative bots’ »
This note continues an exploration of arrow-friendly formulations of functional reactive programming. I refine the previous representations into an interactive dance with dynamically interchanging roles of follow and lead. These two roles correspond to the events and reactive values in the (non-arrow) library Reactive described in a few previous posts. The post ends with some examples.
The code described (with documentation and examples) here may be found in the new, experimental library Bot (which also covers mutant-bots and chatter-bots).
Continue reading ‘Functional reactive partner dancing’ »