infinite lazy-lists and folding them in f#

On key-feature in Haskell is it’s laziness, meaning that it does it’s evaluations in normal-order (an expression is evaluated when the value is needed). F# on the other hand uses applicative evaluation (for example: parameters to a function are evaluated before the function is called – so not the expressions but their values are passed).

Normally this is fine and there is no problem, but if you want to work with infinite lists things are getting interesting.

Look at this example in Haskell:

let natN = [0..] 
let posN = foldr (\ a s -> (a+1):s) [] natN

It creates the natural numbers (starting at 0) – a infinite list natN and uses a right-fold to just increment each value by 1 (getting the positive natural numbers) – aside from the fact that this is a rather stupid example it shows that – being lazy – Haskell has no problem folding infinite lists under certain circumstances.

This article tries to explain how you could do something similar in F#, introducing the nice lazy-computation syntax on the go.

Defining a lazy-list type

So let’s start by introducing our own lazy-list – as each list those can be either empty or can be a “cons” – a pair of a value and the rest of the list (another lazy-list) but in our case the rest or tail should be lazy (i.e. only constructed on demand). You could either use functions of type unit –> ‘a for the laziness, or – as I choose – use the lazy computations F# comes bundled with:

type LazyList<'a> = 
   | Empty 
   | Cons of 'a * Lazy<LazyList<'a>> 
   with 
   member l.Head = 
      match l with 
      | Cons (h, _) -> h 
      | Empty -> failwith "empty list" 
   member l.Tail = 
      match l with 
      | Cons (_, t) -> t.Force() 
      | Empty -> failwith "empty list"

As you can see I implemented two simple properties to get to the Head/Tail part of the list.

Maybe you haven’t seen the lazy syntax yet. It’s very simple: if you wrap a expression inside a lazy( … ) F# won’t evaluate the expression till you call .Force() on the resulting value. Force() will return the evaluated value and even memoize it so that it’s only computed once – nice.

The basics

Of course you should provide the common primitives, namely singleton, cons, map and iter for this list, and it’s almost a no-brainer (“let the types guide you…”):

module LazyList = 

   let single a = Cons (a, lazy ( Empty )) 

   let cons (a : 'a) (l : LazyList<'a>) = Cons (a, lazy ( l )) 

   let rec map (f : 'a -> 'b) (l : LazyList<'a>) : LazyList<'b> = 
      match l with 
      | Empty -> Empty 
      | Cons (a, t) -> Cons (f a, lazy (map f (t.Force()))) 

   let rec iter (f : 'a -> unit) (l : LazyList<'a>) : unit = 
      match l with 
      | Empty -> () 
      | Cons (a, t) -> f a iter f (t.Force())

Ok – the lazy/force and it’s parentheses somewhat clutter the code (you certainly could improve here) but I think its succinct enough.

To really do something similar with a infinite list I need take too (well iter endlessly… well):

module LazyList = 

   let rec take nr (l : LazyList<'a>) : LazyList<'a> = 
      match l with 
      | Empty -> Empty 
      | Cons (a, t) -> 
         if nr = 0 then Empty 
         else Cons (a, lazy (take (nr-1) (t.Force()))) [/sourcecode

Unfolding the naturals

So how to we get the infinite naturals in the first place? Well this is what unfold is for:

module LazyList = 

   let rec unfold (f : 's -> ('a*'s) option) (init : 's) : LazyList<'a> = 
      match f init with 
      | None -> Empty 
      | Some (a, s) -> Cons (a, lazy ( unfold f s))

with this you can define the naturals by calling

let natNumbers = LazyList.unfold (fun n -> Some (n, n+1)) 0

Defining the right-fold

This is somewhat more tricky as we have to simulate Haskell’s laziness in just the right place. If you implement foldr the usual way:

let rec foldr' (f : 'a -> 's -> 's) (init : 's) (l : LazyList<'a>) : 's = 
   match l with 
   | Empty -> init 
   | Cons (a, t) -> f a (foldr' f init (t.Force()))

you get the problem that F# begins to evaluate the current state for the call of the fold function f (in the Cons-case) and this will get you a nice stack-overflow exception in no time.

So we have to introduce laziness here:

let rec foldr (f : 'a -> Lazy<'s> -> 's) (init : 's) (l : LazyList<'a>) : 's = 
   match l with 
   | Empty -> init 
   | Cons (a, t) -> f a (lazy (foldr f init (t.Force())))

That’s it – now we can to the Haskell equivalent:

let posNatNumbers = 
   LazyList.foldr (fun n l -> Cons ((n+1), l)) Empty natNumbers 

posNatNumbers |> LazyList.take 20 |> LazyList.iter (printf "%d, ")

giving us the desired output:

> posNatNumbers |> LazyList.take 20 |> LazyList.iter (printf "%d, ");;

 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, val it: unit = ()

Disclaimer:

This is not meant to be production code or performance-optimized but I think it shows that there is a lot more to F# than you would expect but just toying around with seqs and lists.

a simple fractal using Paper.js

Currently I’m trying to get a bit more JavaScript and HTML5 exposure (no use denying it I guess – it’s here to stay) and found the Paper.js framework which seems to be really nice.

An easy way to test a vector-based framework often are fractals where you can get visual pleasing images that are easy to generate and are often very taxing on the frameworks and render-engines.

The fractal’s construction

The easiest one I can think of is Sierpinski’s triangle:

PaperJsSierpinski

It’s really easy to generate:

given 3 Points (of a triangle) A, B, C just create the midpoints on AB, AC and BC and create 3 new triangles (A, AB, AC), (AB, B, BC) and (AC, BC, C) from it – repeat recursively for each of those and you’ve got your fractal:

SierpinskiKonstruction

Implementing this using Paper.js

After all this is very straight-forward, as Paper.js is capable of performing basic vector.operations – so all there is to do is including the paper.js script into your page, adding a canvas-element in the body and doing the drawing in a special “text/paperscript” script:

<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title>Simple Fractal with Paper.Js</title>
    
    <script type="text/javascript" src="Assets/paper.js"></script>
    <script type="text/paperscript" src="Fractal.js" canvas="myCanvas"></script>

</head>
<body>
    <canvas id="myCanvas" resize="true"></canvas>
</body>
</html>

Here is the code for the fractals-drawing (fractal.js):

function genFractal (a, b, c, depth) {
    if (depth == 0) drawTriangle(a, b, c);
    else {
        var ab = (a + b) / 2;
        var ac = (a + c) / 2;
        var bc = (b + c) / 2;

        genFractal(a, ab, ac, depth - 1);
        genFractal(ab, b, bc, depth - 1);
        genFractal(ac, bc, c, depth - 1);
    }
}

function drawTriangle(a, b, c) {
    var path = new Path();
    path.strokeColor = 'red';
    path.moveTo(a);
    path.lineTo(b);
    path.lineTo(c);
    path.lineTo(a);
}

genFractal(new Point(10, 610), new Point(610, 610), new Point(310, 10), 7);

As you can see it’s very easy – just create the new points, generate another iteration of triangles and draw them on the final recursion depth – this will produce the red triangle you see above.

How-to: Setup your XAML-Project using multiple resource dictionaries

If you ever worked with a larger XAML Project the entries in your resource dictionaries will start to pile up and it’s really a pain to find where you put some Brush or Style or whatever.

Wouldn’t it be nice if you could separate your resources into different kinds and manage them in there own files? Well of course you can – and it’s very easy but there are some steps to remember.

I like having my resource dictionaries in a separate folder within my projects – I guess most people call this “Assets” but name mine “Resources” (go figure) – so first create a new folder with whatever name you want and put a new “Resource Dictionary” in there:

AddResourceDictionary

(Note I’m using the VS11 beta but it’s exactly the same in VS2010)

The file opens like this:

<ResourceDictionary xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
                    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml">
    
</ResourceDictionary>

And you can begin filling your resources in there (of course there is support in Blend for this too).

The next step is telling your main resource-dictionary (usually in the App.xaml file) to merge with your newly created dictionary. This is done using something like the following:

    <Application.Resources>
        <ResourceDictionary>
            <ResourceDictionary.MergedDictionaries>
                <ResourceDictionary>
                    <Color x:Key="Redish" R="155" />
                </ResourceDictionary>
                <ResourceDictionary Source="Resources/Templates.xaml" />
            </ResourceDictionary.MergedDictionaries>
        </ResourceDictionary>
    </Application.Resources>

As you can see – all that there is to it is using the ResourceDictionary.MergedDictionaries collection and adding dictionaries. In this case I use one “in-place” and the Templates dictionary I created in the last step (setting the Source property).

That’s it – now you can use those resources as if you had defined them in your local or App resources.