hubFS: THE place for F#

"Hello World" is too simplistic, so whenever I learn a new language, I always implement a "Hello Mandelbrot" program.  I realize there are probably implementations already out there (who doesn't like making fractals? :P), but figured I'd give it a try without hunting around first.

I'd really appreciate comments from everyone here as to the implementation and style.  Do you see any room for improvements?  Did I do something wrong?  Or naive? Or good? :)  Any constructive criticism is greatly appreciated.


I'm particularly fond of the color picking algorithm using a list of (int,Color) tuples as a "color map".  This really illustrates the power of F# pattern matching.

Any comments? :)

---

http://thevalerios.net/matt/

Nice effort!

You can save yourself 20 odd lines of code by creating the form in a scripting style rather than an OO style. I think there maybe some other places in the algorithm itself were you can save quite a few lines but that's not as easy to spot. It maybe a good exercise to go thought the code and just make it as short as possible, this is something of an obession of functional programmers. Anyway here's my effort:

#light
// F# Mandelbrot Set Generator, 11.19.08, Matt Valerio
 
open System.Drawing
open System.Windows.Forms
open Microsoft.FSharp.Math
 
let ShowForm (f : Form) =
#if INTERACTIVE
    f.Show()
#endif
#if COMPILED
    Application.Run(f)
#endif

let BitmapForm bitmap =
    let picBox = new PictureBox(BorderStyle = BorderStyle.Fixed3D, Image = bitmap, Size = bitmap.Size,
                                Dock = DockStyle.Fill, SizeMode = PictureBoxSizeMode.StretchImage)
    let form = new Form(Text = "F# Mandelbrot", Size = bitmap.Size)
    form.Controls.Add(picBox)
    form

let MagnitudeSquared (c : complex) =  c.r * c.r + c.i * c.i
 
type Extents<'a> = { Xmin : 'a; Xmax : 'a; Ymin : 'a; Ymax : 'a }  with
    override t.ToString() = sprintf "(%A,%A)-(%A,%A)" t.Xmin t.Ymin t.Xmax t.Ymax
 
let inline interp y1 y2 x1 x2 x =
    let ymax = max y1 y2
    let ymin = min y1 y2
    let xmax = max x1 x2
    let xmin = min x1 x2
    ((ymax-ymin)/(xmax-xmin))*(x-xmin)+ymin
 
let MapX (size : Size) (extents : Extents<float>) x =
    interp extents.Xmax extents.Xmin 0.0 (float size.Width) x
 
let MapY (size : Size) (extents : Extents<float>) y =
    interp extents.Ymax extents.Ymin 0.0 (float size.Height) y
 
let Mandelbrot (maxIter : int) (c : complex) =
    let rec MandelbrotInner z iter =
        if (iter = maxIter) || (z |> MagnitudeSquared >= 4.0) then iter          
        else
            MandelbrotInner (z*z+c) (iter+1)      
    MandelbrotInner c 0
 
let colorMap = [(0, Color.Black); (3, Color.Red); (6, Color.Blue); (10, Color.Chartreuse);
                (20, Color.Magenta); (50, Color.DarkTurquoise); (100, Color.White)]
 
let PickColor (map : (int * Color) list) (n : int) =
    let InterpolateColor i1 (c1:Color) i2 (c2:Color) =      
        let r = interp (int c1.R) (int c2.R) i1 i2 n
        let g = interp (int c1.G) (int c2.G) i1 i2 n
        let b = interp (int c1.B) (int c2.B) i1 i2 n
        Color.FromArgb(r,g,b)
    let rec PickColorInternal map =
        match map with
        | [] -> Color.Black
        | [(_,c)] -> c
        | (i1,c1)::((i2,c2)::_ as t) -> if (i1 <= n) && (n <= i2) then
                                            InterpolateColor i1 c1 i2 c2
                                        else
                                            PickColorInternal t
    PickColorInternal map
 
let MakeMandelbrotBitmap (maxIter : int) (size : Size) (extents : Extents<float>) =
    let b = new Bitmap(size.Width, size.Height, Imaging.PixelFormat.Format24bppRgb)
    for w in [0 .. size.Width-1] do
        for h in [0 .. size.Height-1] do
            let x = MapX size extents (float w)
            let y = MapY size extents (float h)          
            let c = Complex.Create (x,y)
            b.SetPixel(w, h, c |> Mandelbrot maxIter |> PickColor colorMap)
    b

let maxIter = 100;
let size = new Size(700,600)  
let extents = {Xmin = -2.0; Xmax = 1.0; Ymin = -2.0; Ymax = 2.0}
 
do MakeMandelbrotBitmap maxIter size extents
   |> BitmapForm

Cheers,
Rob

---

Robert Pickering, MVP
http://strangelights.com

Oh ok, that makes sense.  That is a lot cleaner.
I was just copy/pasting the WinForms designer generated code into F# and changing all the "=" to "<-" (for the most part) :P

Thanks for taking the time to comment!

---

http://thevalerios.net/matt/

here's my rendition.  some things are shorter than i would have them in a normal app, for purposes of screwing around

#light

open System.Drawing
open System.Windows.Forms
open Microsoft.FSharp.Math

let max_iter = 100;
let width, height = 700,600
let xmin, xmax = -2.0, 1.0
let ymin, ymax = -2.0, 2.0

let color_map = seq [ (0, Color.Black); (3, Color.Red); (6, Color.Blue); (10, Color.Chartreuse);
                      (20, Color.Magenta); (50, Color.DarkTurquoise); (100, Color.White) ]
                |> Seq.pairwise |> Seq.cache

let bitmap = new Bitmap( width, height, Imaging.PixelFormat.Format24bppRgb )

let form = new Form(
    Text = "F# Mandelbrot",
    Size = bitmap.Size)

let pic_box = new PictureBox(
    BorderStyle = BorderStyle.Fixed3D,
    Image = bitmap,
    Size = bitmap.Size,
    Dock = DockStyle.Fill,
    SizeMode = PictureBoxSizeMode.StretchImage)

form.Controls.Add( pic_box )

let mandelbrot c =
    let rec curse iter (z: complex) =
        if (iter = max_iter) || (z.Magnitude > 2.0) then
            iter
        else
            curse (iter + 1) (z*z + c)

    curse 0 c

let inline map (x1min, x1max) (x2min, x2max) =
    let ratio = (x2max - x2min) / (x1max - x1min)

    fun value ->
        (value - x1min) * ratio + x2min

let pick_color n =
        color_map
        |> Seq.find (fun ((a, _), (b, _)) -> (a <= n) && (n <= b))
        |> (fun ((a, c1), (b, c2)) ->
                let f (c, d) = map (a, b) (int c, int d) n
               
                Color.FromArgb( f (c1.R, c2.R),
                                f (c1.G, c2.G),
                                f (c1.B, c2.B) ))

let mapx = float >> map (0.0, float width) (xmin, xmax)
let mapy = float >> map (0.0, float height) (ymin, ymax)

for x = 0 to width - 1 do
    for y = 0 to height - 1 do
        bitmap.SetPixel( x, y, Complex.Create(mapx x, mapy y) |> mandelbrot |> pick_color )

#if INTERACTIVE
form.Show()
#else
Application.Run(form)
#endif

one of the things i noticed is that by using the inline keyword on a function it becomes less polymorphically challenged

i was trying to do let i = Complex.Create(0,1) for a more natural notation, but except for scalars the Complex class lacks operations with floats.  quite pathetic

Hi amr,

Thanks for that!  Very clean and concise (and short).

I really like what you did with the map function, making it return a function that can be easily composed (e.g. applying the "float" function and then the map function using "float >> map").  That makes a lot of sense.  It also makes sense to group things together into tuples that must (should?) be applied together (like x-y coordinates for point pairs).

I'd forgotten about Seq.pairwise.  Nice.  Why did you Seq.cache?

Thanks again.

---

http://thevalerios.net/matt/

since F# has currying/partial application, that explicit returning of a function isn't really necessary.  the map function could have been written

let inline map (x1min, x1max) (x2min, x2max) value =
    (x2max - x2min) / (x1max - x1min) * (value - x1min) + x2min

and it would work the same.  in this case the compiler might even be smart enough to memoize the function up to before 'value' is reached.  i explicitly returned a function because i'm not sure about how it might be optimized.  for simple arithmetic like this though it's probably not something to worry about either way

i use tuples because it helps me get a grasp of what the parameters are when i'm using the function, so it's really a readability thing for me.  in the case of the map function, i see it as a mapping from one range to another, and so the tuples let me "visualize" that a little bit

from what i understand, sequences are evaluated only when necessary, which is useful for very large sequences.  For example, if you do this:

let my_seq = seq [ 1; 2; 3; 4; 5 ]

my_seq |> Seq.map ((+) 1) // increment each value by 1

nothing will actually happen.  the original my_seq might not even be "actualized."  nothing happens until you request a value from the sequence, like if you print it out.  the issue is that the sequence isn't memoized (again, for purposes of large sequences,) and so every time you iterate over it, the sequence will be recalculated.  in this example case, the incrementation will be applied over and over.  in the case of the color map, the Seq.pairwise would be repeatedly recalculated

that's my understanding at least, but the cached version is indeed faster than the uncached, by 2x on my computer.  i would have liked to use a plain list but i couldn't find a pairwise for lists.  the non-uniform API's for the different data structures is annoying

Cool, thanks.

Makes sense about the tuples.  Functions taking tuples, in general, are more restrictive than those that allow currying of every parameter, but in this case it definitely makes sense.  Not very often do you deal with x,y pairs independently, and even then, how do you decide whether x or y goes first? Tuples just make sense here as a generalization of a Point struct/class like in C#.

Yeah, Seq is just the F# version of IEnumerable in C#, so it makes sense to cache it.

By the way, Seq is just an IEnumerable and the F# List (not to be confused with the C# List = ResizeArray, though this also holds true for that) implements IEnumerable under the covers, it's perfectly legal to use Seq.pairwise on an F# list:


Or you could define your own List.pairwise -- it's pretty easy:

---

http://thevalerios.net/matt/

(playing my usual role of tail-recursion police)

Careful, that 'pairwise' is not tail-recursive.

#light

let rec pairwise l =
    match l with
    | [] | [_] -> []
    | h1::(h2::_ as t) -> (h1,h2) :: pairwise t

let pairwiseTR l =
    let rec pairwise l acc =
        match l with
        | [] | [_] -> acc
        | h1::(h2::_ as t) -> pairwise t ((h1,h2)::acc)
    pairwise l [] |> List.rev

pairwise [1..5] |> printfn "%A"
pairwiseTR [1..5] |> printfn "%A"

let r = pairwiseTR [1..100000] // ok
let r2 = pairwise [1..100000]  // kaboom

 

Oh SNAP :)

Thanks for catching that, Brian.  I meant to double-check that before I posted but forgot.

That's a very tricky point that would make a good blog post -- tips about how to make absolutely sure that your recursive function can be optimized by the compiler to be tail recursive so there are no "kabooms" at runtime.

---

http://thevalerios.net/matt/