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, 4: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:
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 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: |
|
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...
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: Tree-zipper-query.aspx.Tree<_>
Full name: Tree-zipper-query.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: Tree-zipper-query.aspx.Path<_>
Full name: Tree-zipper-query.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: Tree-zipper-query.aspx.TreeZipper<_>
Full name: Tree-zipper-query.aspx.TreeZipper`1.ToString
Full name: Tree-zipper-query.aspx.left
Navigates to the left sub-tree
Full name: Microsoft.FSharp.Core.Operators.failwith
Full name: Tree-zipper-query.aspx.right
Navigates to the right sub-tree
Full name: Tree-zipper-query.aspx.current
Gets the value at the current position
Full name: Tree-zipper-query.aspx.up
Full name: Tree-zipper-query.aspx.top
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
Full name: Tree-zipper-query.aspx.bindSub
Transform leaves in the current sub-tree 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: Tree-zipper-query.aspx.TreeZipperBuilder
--------------------
new : unit -> TreeZipperBuilder
Full name: Tree-zipper-query.aspx.TreeZipperBuilder.For
Enables the 'for x in xs do ..' syntax
Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Yield
Enables the 'yield x' syntax
Full name: Tree-zipper-query.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: Tree-zipper-query.aspx.TreeZipperBuilder.Left
Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Right
Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Up
Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Top
Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Current
Extracts the current value and returns it
Full name: Tree-zipper-query.aspx.TreeZipperBuilder.Select
Transform the current sub-tree 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 sub-tree 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