Conal Elliott

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.

Edits:

• 2009-02-15: Simplified WithCont, collapsing two type parameters into one. Added functor comment about cfoldlc'.

Continue reading ‘Enhancing a Zip’ »

: http://squing.blogspot.com/2008/11/beautiful-folding.html "blog post by Max Rabkin" : http://conal.net/blog/posts/another-lovely-example-of-type-class-morphisms "blog post" : http://conal.net/blog/posts/more-beautiful-fold-zipping "blog post" : http://conal.net/blog/posts/proofs-for-left-fold-zipping/ "blog post" : http://conal.net/blog/posts/simplifying-semantics-with-type-class-morphisms "blog post" : http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ZipFold "the ZipFold package" : http://hackage.haskell.org/packages/archive/ZipFold/latest/doc/html/Data-Zip-FoldL.html "module from the ZipFold package" This post is part four of the 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’ »

: http://conal.net/blog/posts/simplifying-semantics-with-type-class-morphisms "blog post" : http://squing.blogspot.com/2008/11/beautiful-folding.html "blog post by Max Rabkin" I read Max Rabkin's recent post 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 ...

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.

Edits:

• 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 Dif.

Continue reading ‘Beautiful differentiation’ »

: http://citeseer.ist.psu.edu/karczmarczuk98functional.html "ICFP '98 paper "Functional Differentiation of Computer Programs" by Jerzy Karczmarczuk" : http://augustss.blogspot.com/2007/04/overloading-haskell-numbers-part-2.html "Blog post: "Overloading Haskell numbers, part 2, Forward Automatic Differentiation"" : http://sigfpe.blogspot.com/2005/07/automatic-differentiation.html : http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Applicative.html "Documentation for Control.Applicative: applicative functors" : http://vandreev.wordpress.com/2006/12/04/non-standard-analysis-and-automatic-differentiation/ "Blog post by Vlad Andreev" Lately I've ...

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 pure and (< *>) in the Applicative class. 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’ »

: http://conal.net/blog/posts/simply-efficient-functional-reactivity/ "Blog post: "Simply efficient functional reactivity"" : http://conal.net/Pan "The Pan gallery -- functional image synthesis" : http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Applicative.html "Documentation for Control.Applicative: applicative functors" : http://www.haskell.org/haskellwiki/Category_theory/Natural_transformation "Haskell wiki page: "Haskell wiki page on natural transformations"" : http://conal.net/blog/posts/future-values/ "Blog post: "Future values"" : http://conal.net/blog/posts/reactive-values-from-the-future/ "Blog post: ...

I submitted a paper Simply efficient functional reactivity to ICFP 2008.

Abstract:

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”).

: http://conal.net/papers/simply-reactive "Paper: "Simply efficient functional reactivity"" : http://www.icfpconference.org/icfp2008 "ICFP 2008 conference page" I submitted a paper ** to . **Abstract:** > 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 ...

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.

The 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’ »

: http://conal.net/blog/posts/functional-reactive-partner-dancing/ "Blog post: "Functional reactive partner dancing"" : http://conal.net/blog/posts/reactive-values-from-the-future/ "Blog post: "Reactive values from the future"" : http://haskell.org/haskellwiki/TypeCompose "Wiki page for the TypeCompose library" : http://conal.net/blog/posts/reactive-normal-form/ "Blog post: "Reactive normal form"" : http://haskell.org/haskellwiki/Bot "Wiki page for the Bot library" : http://hackage.haskell.org/cgi-bin/hackage-scripts/package/bot-0.1 "Haskell package: bot" In , ...

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’ »

: http://haskell.org/haskellwiki/Bot "Wiki page for the Bot library" : http://conal.net/blog/posts/functional-reactive-chatter-bots/ "Blog post: "Functional reactive chatter-bots"" : http://conal.net/blog/posts/accumulation-for-functional-reactive-chatter-bots/ "Blog post: "Accumulation for functional reactive chatter-bots"" : http://haskell.org/haskellwiki/Reactive "Wiki page for the Reactive library" : http://hackage.haskell.org/cgi-bin/hackage-scripts/package/arrows "Haskell package: arrows" : http://haskell.org/ghc/docs/latest/html/libraries/base/Control-Arrow.html "Library documentation: `Control.Arrow`" : http://www.md.chalmers.se/Cs/Research/Functional/Fudgets/ "Fudgets home page" : http://haskell.org/arrows/biblio.html#Hug00 "Paper: "Generalizing ...