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

Manning: F# Deep Dives deal of the day

The F# language has been around for longer than many people suspect. My first, completely outdated, blog post was from May 2006. The Microsoft Research releases, sometime around 2006 were the first stable versions that gained some interest and slowly attracted commercial users.

A lot has changed since the early days. F# now includes powerful features like computation expressions and asynchronous workflows and F# 3.0 comes with unique type provider mechanism.

There is an increasing number of users from diverse domains: F# is used to model complex domains in finance and science; asynchronous and concurrent features are used to write server-side components of social games and trading systems, but also in web programming; the expressivity of F# is used by machine learning experts to handle dirty data or classify XBox players. Moreover, the F# Software Foundation has been recently founded to support the collaboration between different commercial users, open-source community and academia.

There is an increasing interest in F#, but many of those who approach it ask (excellent) questions such as: "In what problem domains can I benefit from F#?" or "How do I use F# in finance/science/gaming or web programming?" and most importantly "How do I approach different problems in F#?"

Published: Tuesday, 18 December 2012, 5:19 PM
Tags: manning, f#, writing, books
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)