The F# Computation Expression Zoo (PADL'14)
F# computation expressions are the syntactic language mechanism that is used by features like sequence expressions and asynchronous workflows. The aim of F# computation expressions is to provide a single syntactic mechanism that provides convenient notation for writing a wide range of computations.
The syntactic mechanisms that are unified by computation expressions include Haskell do
notation and list comprehensions, C# iterators, asynchronous methods and LINQ queries,
Scala for
comprehensions and Python generators to name just a few.
Some time ago, I started working on an academic article to explain what makes computation expressions unique  and I think there is quite a few interesting aspects. Sadly, this is often not very well explained and so the general perception is more like this...
Published: Friday, 8 November 2013, 7:42 AM
Tags:
haskell, research, f#, functional programming
Read the complete article
Processing trees with F# zipper computation
One of the less frequently advertised new features in F# 3.0 is the query syntax.
It is an extension that makes it possible to add custom operations in an F#
computation expression. The standard query { .. }
computation uses this to define
operations such as sorting (sortBy
and sortByDescending
) or operations for taking
and skipping elements (take
, takeWhile
, ...). For example, you can write:
1: 2: 3: 

In this article I'll use the same notation for processing trees using the zipper pattern. I'll show how to define a computation that allows you to traverse a tree and perform transformations on (parts) of the tree. For example, we'll be able to say "Go to the left subtree, multiply all values by 2. Then go back and to the right subtree and divide all values by 2" as follows:
1: 2: 3: 4: 5: 6: 7: 

This example behaves quite differently to the usual query
computation. It mostly
relies on custom operations like left
, right
and up
that allow us to navigate
through a tree (descend along the left or right subtree, go back to the parent node).
The only operation that does something is the map
operation which transforms the
current subtree.
This was just a brief introduction to what is possible, so let's take a detailed look at how this works...
Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.query
Calls Linq.QueryBuilder.Take
Calls Linq.QueryBuilder.SortByDescending
 Node of Tree<'T> * Tree<'T>
 Leaf of 'T
override ToString : unit > string
Full name: Treezipperquery.aspx.Tree<_>
Full name: Treezipperquery.aspx.Tree`1.ToString
 Node(l, r) > sprintf "(%O, %O)" l r
 Leaf v > sprintf "%O" v
 Top
 Left of Path<'T> * Tree<'T>
 Right of Path<'T> * Tree<'T>
override ToString : unit > string
Full name: Treezipperquery.aspx.Path<_>
Full name: Treezipperquery.aspx.Path`1.ToString
 Top > "T"
 Left(p, t) > sprintf "L(%O, %O)" p t
 Right(p, t) > sprintf "R(%O, %O)" p t
 TZ of Tree<'T> * Path<'T>
override ToString : unit > string
Full name: Treezipperquery.aspx.TreeZipper<_>
Full name: Treezipperquery.aspx.TreeZipper`1.ToString
Full name: Treezipperquery.aspx.left
Navigates to the left subtree
Full name: Microsoft.FSharp.Core.Operators.failwith
Full name: Treezipperquery.aspx.right
Navigates to the right subtree
Full name: Treezipperquery.aspx.current
Gets the value at the current position
Full name: Treezipperquery.aspx.up
Full name: Treezipperquery.aspx.top
val unit : v:'a > TreeZipper<'a>
Full name: Treezipperquery.aspx.unit
Build tree zipper with singleton tree

type unit = Unit
Full name: Microsoft.FSharp.Core.unit
Full name: Treezipperquery.aspx.bindSub
Transform leaves in the current subtree of 'treeZip'
into other trees using the provided function 'f'
type TreeZipperBuilder =
new : unit > TreeZipperBuilder
member Current : tz:TreeZipper<'a> > 'a
member Current : tz:TreeZipper<'a> > 'a
member For : tz:TreeZipper<'T> * f:('T > TreeZipper<'T>) > TreeZipper<'T>
member Left : tz:TreeZipper<'a> > TreeZipper<'a>
member Left : tz:TreeZipper<'a> > TreeZipper<'a>
member Right : tz:TreeZipper<'a> > TreeZipper<'a>
member Right : tz:TreeZipper<'a> > TreeZipper<'a>
member Select : tz:TreeZipper<'a> * f:('a > 'a) > TreeZipper<'a>
member Select : tz:TreeZipper<'a> * f:('a > 'a) > TreeZipper<'a>
...
Full name: Treezipperquery.aspx.TreeZipperBuilder

new : unit > TreeZipperBuilder
Full name: Treezipperquery.aspx.TreeZipperBuilder.For
Enables the 'for x in xs do ..' syntax
Full name: Treezipperquery.aspx.TreeZipperBuilder.Yield
Enables the 'yield x' syntax
Full name: Treezipperquery.aspx.tree
Global instance of the computation builder
type CustomOperationAttribute =
inherit Attribute
new : name:string > CustomOperationAttribute
member AllowIntoPattern : bool
member IsLikeGroupJoin : bool
member IsLikeJoin : bool
member IsLikeZip : bool
member JoinConditionWord : string
member MaintainsVariableSpace : bool
member MaintainsVariableSpaceUsingBind : bool
member Name : string
...
Full name: Microsoft.FSharp.Core.CustomOperationAttribute

new : name:string > CustomOperationAttribute
Full name: Treezipperquery.aspx.TreeZipperBuilder.Left
Full name: Treezipperquery.aspx.TreeZipperBuilder.Right
Full name: Treezipperquery.aspx.TreeZipperBuilder.Up
Full name: Treezipperquery.aspx.TreeZipperBuilder.Top
Full name: Treezipperquery.aspx.TreeZipperBuilder.Current
Extracts the current value and returns it
Full name: Treezipperquery.aspx.TreeZipperBuilder.Select
Transform the current subtree using 'f'
type ProjectionParameterAttribute =
inherit Attribute
new : unit > ProjectionParameterAttribute
Full name: Microsoft.FSharp.Core.ProjectionParameterAttribute

new : unit > ProjectionParameterAttribute
Calls TreeZipperBuilder.Left
Calls TreeZipperBuilder.Select
Transform the current subtree using 'f'
Calls TreeZipperBuilder.Up
Calls TreeZipperBuilder.Right
Calls TreeZipperBuilder.Top
Published: Wednesday, 19 December 2012, 2:22 PM
Tags:
f#, haskell, research, monads, linq
Read the complete article
Applicative functors: definition and syntax
In a recent blog post, Edward Z. Yang talks about applicative functors.
He mentions two equivalent definitions of applicative functors  the standard
definition used in Haskell libraries (Applicative
) and an alternative that
has been also presented in the original paper, but is generally less
familiar (Monoidal
).
The standard definition makes a perfect sense with the standard uses in Haskell,
however I always preferred the alternative definition. Edward uses the alternative
(Monoidal
) definition to explain the laws that should hold about applicative
functors and to explain commutative applicative functors, but I think it
is even more useful.
The Monoidal
definition fits nicely with a trick that you can use to
encode applicative functors in C# using LINQ and I also used it as
a basis for an F# syntax extension that allows writing code using applicative
functors in a similar style as using monads (which is discussed in my draft
paper about writing abstract computations in F#). And I also think that
commutative applicative functors deserve more attention.
Published: Tuesday, 21 August 2012, 2:23 PM
Tags:
research, haskell, f#
Read the complete article
F# in Academia: Present at upcoming events!
The F# language was born as a combination of the pragmatic and realworld .NET platform and functional programming, which had a long tradition in academia. Many useful ideas or libraries in F# (like asynchronous workflows and firstclass events) are inspored by research in functional programming (namely, the work on monads, continuations and functional reactive programming).
Exchanging the ideas between the research community and the realworld is one of the areas where F# excels. Indeed, the first applicatiosn of F# inside Microsoft (in the Machine Learning group at Cambridge) were all about this  combining research in machine learning with a language that can be easily used in practice.
However, F# and the F# users also made numerous contributions to the programming language research community. Influential ideas that come from F# include active patterns and the F# style of metaprogramming for translating F# to JavaScript). I think there is a lot more that the academic community can learn from the F# community, so I'd like to invite you to talk about your ideas at two upcoming academic events!
What, why, when, where and how? Continue reading!
Published: Monday, 16 April 2012, 12:19 AM
Tags:
presentations, f#, haskell, research
Read the complete article
Extending Monads with Pattern Matching (Haskell 2011)
Some time ago, I wrote a paper about joinads and the match!
extension
of the F# language. The paper was quite practically oriented and didn't go into much details about
the theory behind joinads. Many of the examples from the F# version relied on some
imperative features of F#. I believe that this is useful for parctical programming, but I
also wanted to show that the same idea can work in the purely functional context.
To show that joinads work in the pure setting, I created a Haskell version of the idea. The implementation (available below) is quite simple and consists of a preprocessor for Haskell source files and numerous examples. However, more important part of the recent work of joinads is a more detailed theoretical background.
The theory of joinads, together with the language design of Haskell extension that implements it is discussed in a paper Extending Monads with Pattern Matching, which was accepted for publication at the Haskell Symposium 2011. Here is the abstract of the paper:
Sequencing of effectful computations can be neatly captured using monads and elegantly written using
do
notation. In practice such monads often allow additional ways of composing computations,
which have to be written explicitly using combinators.
We identify joinads, an abstract notion of computation that is stronger than monads and captures
many such adhoc extensions. In particular, joinads are monads with three additional operations:
one of type m a > m b > m (a, b)
captures various forms of parallel composition,
one of type m a > m a > m a
that is inspired by choice and one of type m a > m (m a)
that captures aliasing of computations. Algebraically, the first two operations form a
nearsemiring with commutative multiplication.
We introduce docase
notation that can be viewed as a monadic version of case
. Joinad laws
make it possible to prove various syntactic equivalences of programs written using docase
that are analogous to equivalences about case
. Examples of joinads that benefit from the notation
include speculative parallelism, waiting for a combination of user interface events, but also
encoding of validation rules using the intersection of parsers.
Links to the full paper, source code and additional materials are available below.
Published: Wednesday, 20 July 2011, 12:19 AM
Tags:
parallel, writing, research, haskell, joinads
Read the complete article
Fun with parallel monad comprehensions (The Monad.Reader)
This article is a republication of an article that I wrote some time ago for The Monad.Reader magazine, which is an online magazine about functional programming and Haskell. You can also read the article in the original PDF format as part of the Issue 18 (together with two other interesting articles). The samples from the article can be found on Github.
Monad comprehensions have an interesting history. They were the first syntactic extension for
programming with monads. They were implemented in Haskell, but later replaced with plain list
comprehensions and monadic do
notation. Now, monad comprehensions are back in Haskell,
more powerful than ever before!
Redesigned monad comprehensions generalize the syntax for working with lists. Quite interestingly, they also generalize syntax for zipping, grouping and ordering of lists. This article shows how to use some of the new expressive power when working with wellknown monads. You'll learn what "parallel composition" means for parsers, a poor man's concurrency monad and an evaluation order monad.
Published: Tuesday, 19 July 2011, 11:28 PM
Tags:
haskell, research, parallel
Read the complete article
Explicit speculative parallelism for Haskell's Par monad
Haskell provides quite a few ways for writing parallel programs, but none of them is fully automatic. The programmer has to use some annotations or library to run computations in parallel explicitly. The most recent paper (and library) for writing parallel programs follows the latter approach. You can find more information about the library in a paper by Simon Marlow et al. A monad for deterministic parallelism and it is also available on Hackage. However, I'll explain all the important bits that I'll use in this article.
The library provides an explicit way for writing parallel programs using a Par
monad. The library contains
constructs for spawning computations and sharing state using blocking variables. However, the whole programming model
is fully deterministic. I believe that it is sometimes useful to lift the determinacy requirement.
Some programs are deterministic, but the fact cannot be (easily) automatically verified. For example, say you have two functions
fib1
and fib2
. They both give the same result, but each of them is more efficient
than the other one on certain inputs. To calculate a Fibonacci number, the program could speculatively
try to evaluate both functions in parallel and return the result of the one that finishes first.
Unfortunately, this cannot be safely implemented using a fully deterministic library. In this article, I'll show some
examples where speculative parallelism can be useful and I'll talk about an extension to the Par
monad
that I implemented (available on GitHub). The extension allows
programmers to write speculative computations, provided that they manually verify that their code is
deterministic.
Published: Tuesday, 17 May 2011, 1:59 PM
Tags:
research, haskell, parallel
Read the complete article