Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
by Mathias 11. March 2012 11:29

I am midway through the highly-recommended “Real-world functional programming: with examples in C# and F#”, which inspired me to play with graphics using F# and WinForms (hadn’t touched that one in a long, long time), and I figured it would be fun to try generating a Sierpinski Triangle.

The Sierpinski Triangle is generated starting from an initial triangle. 3 half-size copies of the triangle are created and placed outside of the original triangle, each of them having a corner “touching” the middle of one side of the triangle.

Sierpinski-original

That procedure is then repeated for each of the 3 new triangles, creating more and more smaller triangles, which progressively fill in an enclosing triangular shape. The figure below uses the same starting point, stopped after 6 “generations”:

 

Sierpinski-6

The Sierpinski Triangle is an example of a fractal figure, displaying self-similarity: if we were to run the procedure ad infinitum, each part of the Triangle would look like the whole “triangle” itself.

So how could we go about creating this in F#?

I figured this would be a good case for Seq.unfold: given a state (the triangles that have been produced for generation n), and an initial state to start from, provide a function which defines how the next generation of triangles should be produced, defining a “virtual” infinite sequence of triangles – and then use Seq.take to request the number of generations to be plotted.

Here is the entire code I used; you’ll need to add a reference to System.Windows.Forms and System.Drawings for it to run:

open System
open System.Drawing
open System.Windows.Forms

type Point = { X:float32; Y:float32 }
type Triangle = { A:Point; B:Point; C:Point }

let transform (p1, p2, p3) =
   let x1 = p1.X + 0.5f * (p2.X - p1.X) + 0.5f * (p3.X - p1.X)
   let y1 = p1.Y + 0.5f * (p2.Y - p1.Y) + 0.5f * (p3.Y - p1.Y)
   let x2 = p1.X + 1.0f * (p2.X - p1.X) + 0.5f * (p3.X - p1.X)
   let y2 = p1.Y + 1.0f * (p2.Y - p1.Y) + 0.5f * (p3.Y - p1.Y)
   let x3 = p1.X + 0.5f * (p2.X - p1.X) + 1.0f * (p3.X - p1.X)
   let y3 = p1.Y + 0.5f * (p2.Y - p1.Y) + 1.0f * (p3.Y - p1.Y)
   { A = { X = x1; Y = y1 }; B = { X = x2; Y = y2 }; C= { X = x3; Y = y3 }}

let generateFrom triangle = seq {
      yield transform (triangle.A, triangle.B, triangle.C)
      yield transform (triangle.B, triangle.C, triangle.A)
      yield transform (triangle.C, triangle.A, triangle.B)
   }

let nextGeneration triangles =
   Seq.collect generateFrom triangles 
      
let render (target:Graphics) (brush:Brush) triangle =
   let p1 = new PointF(triangle.A.X, triangle.A.Y)
   let p2 = new PointF(triangle.B.X, triangle.B.Y)
   let p3 = new PointF(triangle.C.X, triangle.C.Y)
   let points = List.toArray <| [ p1; p2; p3 ]
   target.FillPolygon(brush, points)
   
let form = new Form(Width=500, Height=500)
let box = new PictureBox(BackColor=Color.White, Dock=DockStyle.Fill)
let image = new Bitmap(500, 500)
let graphics = Graphics.FromImage(image)
let brush = new SolidBrush(Color.FromArgb(0,0,0))
let renderTriangle = render graphics brush

let p1 = { X = 190.0f; Y = 170.0f }
let p2 = { X = 410.0f; Y = 210.0f}
let p3 = { X = 220.0f; Y = 360.0f}
let triangle = { A = p1; B = p2; C = p3 }

let root = seq { yield triangle }
let generations = 
   Seq.unfold (fun state -> Some(state, (nextGeneration state))) root
   |> Seq.take 7
Seq.iter (fun gen -> Seq.iter renderTriangle gen) generations

box.Image <- image
form.Controls.Add(box)

[<STAThread>]
do
   Application.Run(form)

A few comments on the code. I first define 2 types, a Point with 2 float32 coordinates (float32 chosen because that’s what System.Drawing.PointF takes), , and a Triangle defined by 3 Points. The transform function is pretty ugly, and can certainly be cleaned up / prettified. It takes a tuple of 3 Points, and returns the corresponding transformed triangle, shrunk by half and located at the middle of the p1, p2 edge. We can now build up on this with the nextGeneration function, which takes in a Sequence of Triangles (generation n), transforms each of them into 3 new Triangles and uses collect to “flatten” the result into a new Sequence, generation n+1.

The rendering code has been mostly lifted with slight modifications from Chapter 4 of Real-world functional programming. The render function retrieves the 3 points of a Triangle and create a filled Polygon, displayed on a Graphics object which we create in a form.

Running that particular example generates the following Sierpinski triangle; you can play with the coordinates of the root triangle, and the number of generations, to build your own!

As an aside, I was a bit disappointed by the quality of the graphics; beyond 7 or 8 generations, the result gets fairly blurry. I’ll probably give a shot at moving this to XAML, and see if it’s any better.

 

Sierpinski-example

As usual, comments, questions or criticisms are welcome!

by Mathias 4. December 2011 15:47

I am in the middle of “Working Effectively with Legacy Code”, and found it every bit as great as it was said to be. In the book, Feathers introduces the concept of Seams and Enabling Points:

a Seam is a place where you can alter behavior in your program without editing it in that place

every seam has an enabling point, a place where you can make the decision to use one behavior or another.

The idea - as I understand it - is that an enabling point is a hook for testability, a place where you can replace the behavior of a piece of code with your own controlled behavior, and validate that the results are as expected.

The reason I am bringing this up is that I have been writing lots of F# lately, and it made me realize that a functional style provides lots of enabling points, and can be much easier to test than object-oriented code.

Here is a simplified, but representative, example of the problem I was looking at: I needed to pick a random item in a list. In C#, a method along these lines would do the job:

public T PickFrom(IList<T> list)
{
   var random = new Random();
   return list[random.Next(list.Count())];
}

However, this code is utterly untestable; it’s also probably a terrible idea to instantiate a new Random every time this is called, so we modify it this way:

public T PickFrom(IList<T> list, Random random)
{
   return list[random.Next(list.Count())];
}

This is much better: now we have a decent Enabling Point, because the list of arguments of the method contains everything that is used inside the method. However, this is still untestable, but for a different reason: by definition, Random.Next() will return different values every time PickFrom is called, and expecting a repeatable result from PickFrom is a bit of a desperate enterprise.

More...

by Mathias 5. July 2010 16:16

In our last post, we saw how to use F# to read historical stock quotes from Yahoo. Today we’ll take the raw response, which is a big block of text, and break it up into a list of individual quotes.

Breaking up the response into lines

The function we wrote last time, GetResponse, receives one chunk of text from the web service, formatted like this:


Date,Open,High,Low,Close,Volume,Adj Close
2010-03-08,28.52,28.93,28.50,28.63,39414500,28.50
2010-03-05,28.66,28.68,28.42,28.59,56001800,28.46
2010-03-04,28.46,28.65,28.27,28.63,42890600,28.50

What we need to do now is break up this into individual lines of text, and parse them to read individual quotes. The first part is straightforward: the function BreakIntoLines calls String.Split(), using char(10), the code for line break, as a delimiter, and returns an Array of strings.

let BreakIntoLines (response:string) =
  response.Split((char)10)

Note the type annotation on the function argument: without context, F# cannot infer the type of “response”, and we need to specify that this function expects a string argument.

Parsing valid lines into Quote records

The second part is a bit more complex. We need to break each line into 7 components (date, open, etc…), deal with lines that are not valid, like the header, and store the result in an appropriate structure.

We will store individual quotes into records. A Record is a data type somewhat similar to the C# struct. It has named fields, which makes it more expressive than Tuples, and is less involved than a class. Here is the declaration for our Quote record – concise, and pretty self-explanatory:

type Quote={
  Symbol:string;
  Date:DateTime;
  Open:double;
  Close:double;
  Low:double;
  High:double;
  Volume:int64}

More...

by Mathias 21. June 2010 13:12

Lately I have spent time on a pet project, which requires access to historical financial data. Mads Kristensen has a nice post where he shows how to read  stock quotes from Yahoo finance using C#, which was very helpful to get started. I figured it would be interesting to try out a conversion to F# and see what the result looked like.

Mads focus is on getting quasi real-time updates of a quote; my interest is in an easier problem: retrieving historical data. Fortunately, Yahoo provides a free service for that, too. Given a quote symbol and two dates, it returns a comma-separated file list of all the values for the quote between these 2 dates.

So what do we need to do? Given a valid symbol and 2 dates, we want to create the WebRequest to send to Yahoo, retrieve the response, break it into lines, and parse each line into a quote, which will be added to a list. The core of the resulting program will be the ReadQuotes function, which will look like this:

let ReadQuotes symbol date1 date2 = 
  CreateRequest symbol date1 date2 
  |> GetResponse 
  |> BreakIntoLines
  |> CreateQuotes symbol

Creating the WebRequest

The web request required to obtain historical data from Yahoo follows this pattern:

http://ichart.finance.yahoo.com/table.csv?s=S&a=A&b=B&c=C&d=D&e=E&f=F&g=d&ignore=.csv

where:

  • S is the symbol (ex: MSFT)
  • A, B, C are the start month, day and year, the month being coded in base 0 (i.e. January is 0)
  • D, E, F are the end month, day and year, the month being coded in base 0 (i.e. January is 0)

For instance, replacing S with MSFT, A with 0, B with 1, C with 2010, D with 1, E with 15, F with 2010, will return all the available quotes for Microsoft between January 1 and February 15, 2010.

Let’s start by creating a Console application, by selecting new F# project > F# Application, and typing in the following code:

open System;
open System.Net
open System.IO
open System.Text

let RetrieveDateInfo (date:DateTime) =
  (date.Day, date.Month-1, date.Year)

let CreateRequest symbol startDate endDate =

  let startDay, startMonth, startYear = RetrieveDateInfo startDate
  let endDay, endMonth, endYear = RetrieveDateInfo endDate

  let query = String.Format("&a={0}&b={1}&c={2}&d={3}&e={4}&f={5}&g=d&ignore=.csv", startMonth, startDay, startYear, endMonth, endDay, endYear)
  let url = "http://ichart.finance.yahoo.com/table.csv?s=" + symbol + query
  WebRequest.Create(url)

More...

by Mathias 23. January 2010 00:21

One of the immediate benefits I saw in digging into F# is that it gave me a much better understanding of LINQ and lambdas in C#. Until recently, my usage of LINQ was largely limited to returning IEnumerable instead of List<T> and writing simpler queries, but I have avoided the more “esoteric” features. I realize that now that F# is becoming familiar to my brain, whenever I see a statement in C# which contains a foreach:

foreach (var item in items)
{
   // do something with item.
}

… I ask myself if this could be re-written in a more functional way. Sometimes it works, sometimes not. Just like classic OO Design Patterns, functional programming has its own patterns, and I find that having a larger toolkit of patterns in the back of my mind helps criticizing my own code and think about alternatives and possible improvements.

I encountered one such case a few days ago, with the following snippet:

public bool IsValid()
{
    foreach (var rule in this.rules)
    {
        if (!rule.IsSatisfied())
        {
            return false;
        }
    }

    return true;
}

There is nothing really wrong with this code. However, seeing the foreach statement, and an if statement with a return and no else branch made me wonder how I would have done this in F# – and my immediate thought was “I’d use a Fold”.

More...

Comments

Comment RSS