Stateful computations in F# with update monads

Most discussions about monads, even in F#, start by looking at the well-known standard monads for handling state from Haskell. The reader monad gives us a way to propagate some read-only state, the writer monad makes it possible to (imperatively) produce values such as logs and the state monad encapsulates state that can be read and changed.

These are no doubt useful in Haskell, but I never found them as important for F#. The first reason is that F# supports state and mutation and often it is just easier to use a mutable state. The second reason is that you have to implement three different computation builders for them. This does not fit very well with the F# style where you need to name the computation explicitly, e.g. by writing async { ... } (See also my recent blog about the F# Computation Zoo paper).

When visiting the Tallinn university in December (thanks to James Chapman, Juhan Ernits & Tarmo Uustalu for hosting me!), I discovered the work on update monads by Danel Ahman and Tarmo Uustalu on update monads, which elegantly unifies reader, writer and state monads using a single abstraction.

In this article, I implement the idea of update monads in F#. Update monads are parameterized by acts that capture the operations that can be done on the state. This means that we can define just a single computation expression update { ... } and use it for writing computations of all three aforementioned kinds.

Published: Tuesday, 13 May 2014, 3:41 PM
Tags: f#, research, functional programming, monads
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:

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:

tree { for x in sample do
       map (x * 2) 
       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.Tree`1.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.Path`1.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.TreeZipper`1.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:
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
Tags: f#, haskell, research, monads, linq
Read the complete article

All blog posts by tag

f# (112), functional (66), research (44), c# (37), asynchronous (27), parallel (23), academic (22), functional programming (20), universe (20), programming languages (18), meta-programming (18), philosophy (15), links (15), presentations (14), data science (12), writing (12), joinads (12), thegamma (11), web (10), data journalism (9), math and numerics (9), random thoughts (9), talks (8), phalanger (8), haskell (7), mono (7), webcast (7), fslab (5), open source (5), visualization (4), fun (4), accelerator (4), design (3), type providers (3), linq (3), f# data (3), .net (3), training (2), coeffects (2), deedle (2), monads (2), art (2), fractals (2), funscript (2), new york (2), manning (2), books (2), teaching (1), fable (1), machine learning (1), comonads (1), fake (1), f# formatting (1), deep dives (1), async (1), events (1), trainings (1), london (1), literate (1)