TP

# 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, 6:42 AM
Tags: haskell, research, f#, functional programming

# 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:  query { for x in 1 .. 10 do take 3 sortByDescending x } 

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 sub-tree, multiply all values by 2. Then go back and to the right sub-tree and divide all values by 2" as follows:

 1: 2: 3: 4: 5: 6: 7:  tree { for x in sample do left map (x * 2) up right map (x / 2) top } 

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 sub-tree, go back to the parent node). The only operation that does something is the map operation which transforms the current sub-tree.

This was just a brief introduction to what is possible, so let's take a detailed look at how this works...

val query : Linq.QueryBuilder

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.query
val x : int
custom operation: take (int)

Calls Linq.QueryBuilder.Take
custom operation: sortByDescending ('Key)

Calls Linq.QueryBuilder.SortByDescending
type Tree<'T> =
| Node of Tree<'T> * Tree<'T>
| Leaf of 'T
override ToString : unit -> string

Full name: Tree-zipper-query.aspx.Tree<_>
union case Tree.Node: Tree<'T> * Tree<'T> -> Tree<'T>
union case Tree.Leaf: 'T -> Tree<'T>
val x : Tree<'T>
override Tree.ToString : unit -> string

Full name: Tree-zipper-query.aspx.Tree1.ToString
match x with
| Node(l, r) -> sprintf "(%O, %O)" l r
| Leaf v -> sprintf "%O" v
type Path<'T> =
| Top
| Left of Path<'T> * Tree<'T>
| Right of Path<'T> * Tree<'T>
override ToString : unit -> string

Full name: Tree-zipper-query.aspx.Path<_>
union case Path.Top: Path<'T>
union case Path.Left: Path<'T> * Tree<'T> -> Path<'T>
union case Path.Right: Path<'T> * Tree<'T> -> Path<'T>
val x : Path<'T>
override Path.ToString : unit -> string

Full name: Tree-zipper-query.aspx.Path1.ToString
match x with
| Top -> "T"
| Left(p, t) -> sprintf "L(%O, %O)" p t
| Right(p, t) -> sprintf "R(%O, %O)" p t
type TreeZipper<'T> =
| TZ of Tree<'T> * Path<'T>
override ToString : unit -> string

Full name: Tree-zipper-query.aspx.TreeZipper<_>
union case TreeZipper.TZ: Tree<'T> * Path<'T> -> TreeZipper<'T>
val x : TreeZipper<'T>
override TreeZipper.ToString : unit -> string

Full name: Tree-zipper-query.aspx.TreeZipper1.ToString
let (TZ(t, p)) = x in sprintf "%O [%O]" t p
val left : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.left

Navigates to the left sub-tree
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val l : Tree<'a>
val r : Tree<'a>
val p : Path<'a>
val right : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.right

Navigates to the right sub-tree
val current : _arg1:TreeZipper<'a> -> 'a

Full name: Tree-zipper-query.aspx.current

Gets the value at the current position
val x : 'a
val up : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.up
val top : _arg1:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.top
val t : TreeZipper<'a>
val tz : TreeZipper<'a>
Multiple items
val unit : v:'a -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.unit

Build tree zipper with singleton tree

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
val v : 'a
val bindSub : f:('a -> TreeZipper<'a>) -> treeZip:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.bindSub

Transform leaves in the current sub-tree of 'treeZip'
into other trees using the provided function 'f'
val f : ('a -> TreeZipper<'a>)
val treeZip : TreeZipper<'a>
val bindT : (Tree<'a> -> Tree<'a>)
val t : Tree<'a>
val current : Tree<'a>
val path : Path<'a>
Multiple items
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: Tree-zipper-query.aspx.TreeZipperBuilder

--------------------
new : unit -> TreeZipperBuilder
val x : TreeZipperBuilder
member TreeZipperBuilder.For : tz:TreeZipper<'T> * f:('T -> TreeZipper<'T>) -> TreeZipper<'T>

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.For

Enables the 'for x in xs do ..' syntax
val tz : TreeZipper<'T>
val f : ('T -> TreeZipper<'T>)
member TreeZipperBuilder.Yield : v:'a -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Yield

Enables the 'yield x' syntax
val tree : TreeZipperBuilder

Full name: Tree-zipper-query.aspx.tree

Global instance of the computation builder
Multiple items
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
member TreeZipperBuilder.Left : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Left
member TreeZipperBuilder.Right : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Right
member TreeZipperBuilder.Up : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Up
member TreeZipperBuilder.Top : tz:TreeZipper<'a> -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Top
member TreeZipperBuilder.Current : tz:TreeZipper<'a> -> 'a

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Current

Extracts the current value and returns it
member TreeZipperBuilder.Select : tz:TreeZipper<'a> * f:('a -> 'a) -> TreeZipper<'a>

Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Select

Transform the current sub-tree using 'f'
Multiple items
type ProjectionParameterAttribute =
inherit Attribute
new : unit -> ProjectionParameterAttribute

Full name: Microsoft.FSharp.Core.ProjectionParameterAttribute

--------------------
new : unit -> ProjectionParameterAttribute
val f : ('a -> 'a)
custom operation: left

Calls TreeZipperBuilder.Left
custom operation: map ('a)

Calls TreeZipperBuilder.Select

Transform the current sub-tree using 'f'
custom operation: up

Calls TreeZipperBuilder.Up
custom operation: right

Calls TreeZipperBuilder.Right
custom operation: top

Calls TreeZipperBuilder.Top

Published: Wednesday, 19 December 2012, 2:22 PM

# 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

# F# in Academia: Present at upcoming events!

The F# language was born as a combination of the pragmatic and real-world .NET platform and functional programming, which had a long tradition in academia. Many useful ideas or libraries in F# (like asynchronous workflows and first-class 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 real-world 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 meta-programming 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

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 pre-processor 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 ad-hoc 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 near-semiring 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

This article is a re-publication 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 well-known 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

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