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...

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#?"

All blog posts by tag