Using F# fold function to implement recursion

In the last post, we talked about techniques to implement tail-recursion in F#. We also learned that to write pure functional code we can only use immutable data structures which means we have to implement loop using recursion.

Writing recursive function can be cumbersome (e.g., the function has to have one or more base cases) and hard to understand. It’s also harder to make sure that your recursive function is a tail-recursive one.

Fortunately, using higher-order function and data structure like list (which is a recursive data structure) can help easing the pain.

Let’s look at our non-tail-recursive factorial function from last post again.

let rec factorial x =
    if x <= 1 then
        1
    else 
        x * factorial (x - 1)

Since the function basically multiplies numbers (e.g., x, x-1, x-2, …) together, we can actually think of the input as a list of numbers like [5,4,3,2,1] instead.

With that in mind, we can now implement factorial function using List functions like List.fold.

Here is the List.fold signature:

(‘State -> ‘T -> ‘State) -> ‘State -> ‘T list –> ‘State

List.fold is a higher-order function that takes the following parameters:

(‘State –> ‘T –> ‘State)

A function that takes ‘State which we can think of it as an accumulator, ‘T which in this case is each value in the list, and returns new accumulator.

‘State

An initial state of an accumulator.

‘T list

The input list

The last ‘State is the final out put that we want.

Now, let’s see how we can implement our factorial function with only one line of code :-).

let foldFactorial x = [1..x] |> List.fold (fun acc i -> acc * i) 1

The most important part is the lambda expression, (fun acc i -> acc * i), that we pass to the fold function. The acc parameter in the lambda expression is the accumulated result like the acc parameter in accTailRecursiveFactorial recursive function from the last post.

let accFactorial x =
    let rec accTailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            accTailRecursiveFactorial (x - 1) (acc * x)

    accTailRecursiveFactorial x 1

Using fold also gives us tail recursive function. Here is the IL generated by foldFactorial function.

image

(NOTE: some lines have been cut to make the screenshot fit the page)

If you are curious, below is what List.fold looks like (NOTE: The code below is from list.fs in F# compiler and code library on GitHub). You probably notice that it has the nested recursive function that is tail-recursive!

[<CompiledName("Fold")>]
let fold<'T,'State> f (s:'State) (list: 'T list) = 
	match list with 
    | [] -> s
    | _ -> 
		let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
        let rec loop s xs = 
			match xs with 
            | [] -> s
            | h::t -> loop (f.Invoke(s,h)) t
		loop s list

And as a bonus, you can even make the factorial code shorter by using operator (*) which is actually a normal function in F#.

let foldFactorial2 x =  [1..x] |> List.fold (*) 1

Better yet, the code can be made shorter by using List.reduce which is a specialized version of fold that treat the first input on the list as accumulator.

let reduceFactorial x = [1..x] |> List.reduce (*)

This post shows how tail-recursive code could be implemented using List.fold and List.reduce. Since implementing recursive algorithm is important in functional programming, using built-in F# function like fold and reduce really reduces (no pun-intended :-) ) our work.

Recursion and Tail-recursion in F#

While imperative programming language paradigm depends on updating mutable variables (or introducing side effect) to change state of the program, pure functional programming only uses immutable data structures to represent their state. Side effect is required if you need your program to do any work (i.e., I/O), but undesirable side-effects are the root of many bugs. Immutability makes you write safer code as the code is more predictable.

When people (most of us!) with imperative programming languages background start looking at functional programming, we probably think that if we aren’t allowed to change anything, how we can even do anything useful at all. The answer is that instead of writing program as a sequence of statements that change the state like we do in imperative style programming, we write functional programs differently.

Today, we are going to look at recursion which is a technique that allows functional programs to implement loop-like algorithm without using mutable variables. Basically, a recursive function is a function that calls itself.

Let’s see implementations of factorial function using loop and recursion in C#:

// using recursion
int Factorial(int n)
{
    return n<=1?1:n*Factorial(n - 1);
}

// using loop
int FactorialLoop(int n)
{
    var ret = 1;
    while (n >= 1)
    {
        ret *= n--;
    }

    return ret;
}

Now let’s see our F# implemetations:

let rec factorial x =
    if x <= 1 then
        1
    else 
        x * factorial (x - 1)

let factorialLoop x = 
    let mutable n = x
    let mutable ret = 1
    while n >= 1 do
        ret <- ret * n
        n <- (n - 1)
    ret

In C#, the recursive and non-recursive function signature are the same. However, in F#, the rec keyword is needed by the F# type inference system. (I show F# implementation in loop just to show that we can also write F# code in imperative style by using mutable keyword as well although it’s not preferable.)

NOTE: Writing the recursive functions like this every time we need loop-like algorithm can be cumbersome, so most functional languages provide an easier way for doing recursion with higher-order function technique (i.e., Map or Reduce functions). I will write about it in the later post.

Stack Overflow

Ok. Now we can use recursion to implement loop-like algorithm even we aren’t allowed to use mutable variable. However, there is one problem. As you might already know, internally, when a function is called, the caller state will be put into the stack. So if we have a recursive function that call itself deeper and deeper, the program might experience Stack overflow.

Let’s set a break point at the base case and look at our call stack when we call F# factorial 10:

CallStackFactorial10

Although we should not have any stack overflow issue here, stack is not infinite resource, the naive recursive function can cause stack overflow with large number of iterations eventually.

Intermediate Language

Before we talk about tail recursion, let’s talk about IL or Intermediate Language.

What is IL or Intermediate Language? When you compile CLI languages like C#, VB, or F#, the .NET compiler generates IL. You can think about it as the native or assembly language of .NET which runs on CLR. When the .NET application is run, each IL method is translated into native machine code Just-In-Time before it’s first executed.

Although it looks just like normal assembly language, IL is a stack-based language and has no concept of registers. As we walk through each samples, we will talk about some of those instructions and learn what it does.

Tail Recursion

Now we understand recursion, stack overflow, and IL, let me introduce tail call and tail recursion. Tail recursion is a special form of recursion, where the compiler can optimize the recursive call in tail position to not allocate stack space to keep caller state. The idea is that if a compiler can guarantee that the call to the recursive function is the tail call or last action that happens before the function returns, there is no need to keep the caller state in the stack at all!

F# is a functional-first language and its compiler is designed to provide tail-call optimization if possible. The most efficient way is to turn the recursive function into a function with a loop. If the compiler can’t do that because the recursive function is more complex, then the compiler generate call IL with a tail. prefix to let the JIT compiler uses the tail call.

Let’s look at the recursive version of the factorial function in F# again:

let rec factorial x =
    if x <= 1 then
        1
    else 
        x * factorial (x - 1)

At the first glance, we might think that factorial (x-1) is the last action of the function. However, the last action is actually a multiply operation. If you don’t believe me, you can just look at the IL generated from this function.

image

Don’t worry if you don’t understand most of the IL, what I want you to see is mul, which is a multiply operation, is executed before ret, which return from the function, and after call that is the IL that call the function. In this case, it calls its own function recursively.

If F# code above is not tail-recursive function, then how we can create tail-recursive function. In functional programming we have patterns that we can use to make sure that our recursive function is tail-recursive.

Accumulator Pattern

The first pattern is called Accumulator Pattern. In this pattern, we introduce another parameter, accumulator, that keeps the current state of the recursion, so that information doesn’t need to be kept in the call stack and used later. Let’s see how we can apply the pattern to our factorial function above.

let accFactorial x =
    let rec accTailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            accTailRecursiveFactorial (x - 1) (acc * x)

    accTailRecursiveFactorial x 1

So we basically create a non-recursive function that will get called by the consumer. The non-recursive function has the nested recursive function that accepts two parameters, one is the same recursive parameter, and another one, acc, is a parameter that accumulates multiplied result together. Let’s see the call stack when we execute accFactorial 10.

image

As you can see, our call stack is pretty clean now!

When F# compiler sees that the last action is a call to a recursive function, it knows that it can generates IL with tail. prefix. When JIT sees the tail. prefix, it knows that it must use a tail call.

image

(NOTE: some lines have been cut to make the screenshot fit the page)

Continuations

In this pattern (aka continuation passing style), we will see the power of F# and functional programming language! When we treat a function as a value, we can pass it around, make a copy, or create a new one on the fly. So instead of pass another parameter with the accumulated value like in Accumulator Pattern case, why don’t we just build expressions on the fly and pass them via function instead!

Let’s implement the same factorial function with this pattern:

let contFactorial x =
    let rec contTailRecursiveFactorial x f =
        if x <= 1 then 
            f()
        else 
            contTailRecursiveFactorial (x - 1) (fun () -> x * f())

    contTailRecursiveFactorial x (fun () -> 1)

The implementation looks just like the Accumulator Pattern. In this pattern, we also have an outer function which is non-recursive and the nested recursive function. However, instead of passing an accumulator, we pass a function!

Let’s see the call stack and we should see the clean call stack:

image

Now let’s see the generated IL and we should see tail. prefix again:

image

The advantage of using Continuations is that you are not limited to passing a single computed value which might not be possible to do in more complicated recursive function which I can post about it later.

Happy Coding!

Learning F# with F# Succinctly by Robert Pickering

Learn at least one new language every year.

Above is one of the best recommendations in my developer career. It is from the book, “The Pragmatic Programmer” by Andrew Hunt and David Thomas. The obvious advantage of learning a new language is to expand your problem solving skills as different programming languages usually have different styles and approaches to solve problems. To get the most benefit, I think we should not learn the new language that is too similar to the languages we already know (e.g., C# programmer learning Java).

Last summer I was having fun with the “Coding Dojo: a gentle introduction to Machine Learning with F#” by Mathias Brandewinder, so I decided to learn more about F#.

WinRT-DigitRecognizer.PNG (954×588)

I also chose F# for the following reasons:

  1. F# is a “Functional-First” programming language unlike C# which is “Object-Oriented” first. You probably heard a lot of buzz around functional programming paradigm and why it matters especially since the free lunch is over.
  2. F# is one of .NET CLR languages, so interoperability with C# is easy. I can still use C# for many tasks that it is good at such as GUI programming (i.e., XAML for WinRT, Silverlight and WPF) while utilizing F# for other tasks that functional programming will shine.
  3. I can use my favorite IDE, Visual Studio. I also post about Visual Studio Extensions that make your F# development experience better.
  4. F# is also a scripting language, so you can use REPL such as fsi (that comes with Visual Studio) or use web interface on tryfsharp.org or even using .NET fiddle which now supports F#. REPL makes it easier to try and test your code interactively.

However, learning and mastering a new programming language can be daunting task as you already have to keep up with new technology for your day-time job.

There are many F# books on the market, some can be good for overview and quick reference, academic, or written for developers who has C# background, or even for specific tasks.

Today, I will review the free F# e-book from Syncfusion, F# Succinctly by Robert Pickering. F# Succinctly has about 100 pages, so you should be able to finish it within a week easily. It starts with a good and concise introduction into functional and F# programming with a little bit of history. It also gives some idea about why F# is good for .NET developer and how it is different from other functional programming languages.

image

The book has been released for a while, so it’s based F# 2.0 and Visual Studio 2012. However, most samples in the books should still work besides FSharp Charting which you should follow the instructions how to set it up here instead

Like most F# programming books, the book introduces you to F# programming via REPL (fsi). It covers most of the F# programming basic that you should know include the followings:

  • Pattern matching
  • Type and Type inference
  • Records
  • Discriminated Unions
  • Function composition
  • Pipe operation (|>)
  • Partial function

In the later chapters, you will also learn about Object-Oriented aspect in F# and learn why multiple programming paradigm support makes F# suitable to solve different kinds of problems. At the end, you will learn how you can use F# to create user interfaces or graphics and creating real-world web and non-web application using F#.

image

However, as the e-book is written while F# 3.0 was still being implemented, the book doesn’t cover great F# 3.0 features like Type-Providers or LINQ support. Also, the book talks about important functional programming concept like recursion and pattern matching, but it doesn’t cover advance concept like tail-recursion, higher-order function, computation expressions, or active patterns.

In conclusion, the book is a good introduction to F# for anyone (especially .NET developers) who is interested in functional programming and F#. It should be an easy read and ignite your interest into learning F# and functional programming.

By the way, If you are interested in learning more about F#, there are many books, wikis, resources, news, and so on. Although, F# is originated in Microsoft, it’s open source edition and can run on other platforms like iOS, android. The best of all, F# has great and passionate people and community behind it. It also helps that I live in Nashville, TN which has three F# MVPs together with strong functional programming and .NET communities.

NOTE: Although I have been playing with F# for a while now, I still learn a lot of things from the book like how F# supports Unicode. Can you guess what Thai value names below mean in English? :-)

let หนึ่ง = 1
let สอง = 2
let สาม = หนึ่ง + สอง

Create a super-duper-happy SPA web app using Durandal, Nancy, and Bootstrap

I start looking at Durandal after attending Jason Clark’s DurandalJS and Twitter Bootstrap at Nashville .NET User Group. Durandal is a SPA framework that incorporated several popular JavaScript libraries like JQuery, Knockout, and RequireJs. It’s also created by Rob Eisenberg who is also behind Caliburn.Micro.

For Nancy, I have heard about it in .NET Rocks and Hanselminutes podcasts for a while, but I haven’t had a chance to look at it until recently. Basically, Nancy (or NancyFX) is a lightweight web framework allowing you to build HTTP based web applications or services using .NET. Nancy is very easy to learn and set up.However, It doesn’t depend on System.Web and doesn’t need to be run on IIS at all. Most importantly, Nancy is very easy to learn and set up as you will see.

The last one is Bootstrap which is a very popular front-end framework that comes with HTML/CSS/JavaScript templates and controls. It allows us to create better-looking responsive web UI with small effort.

Using them together makes our job to create a web app much easier.

 

Ok. Enough with the background. Let’s get start by building a web app using Durandal and Nancy (I will touch on Bootstrap once we have a web app running).

First, we start with just an empty ASP.NET web site.

 

001-Empty-Web-Project

002-Empty-Web-Project 

 

Once we have the web site project, we install Durandal and Nancy via NuGet. Since I want our web app to run on IIS, I also have another package, Nancy.Hosting.Aspnet installed.

image

 

If everything went smoothly, you should see these packages installed in your project. As Durandal is using JQuery, Knockout, and RequreJS, those packages will be installed as well.

004-NuGet-Packages

 

Now, let’s start coding. We start in the client-side by creating modules (viewmodels) and views. If you have played with the Durandal StarterKit, you should be familiar with the files (index.html, main.js, shell.js, etc.). I won’t explain what those files do here, but you can find more information about them here.

Next, we look at the server-side with Nancy. To set up a Nancy site, what I need to do is to create a C# class derived from NancyModule, and define route handler in the constructor. We don’t need to worry about the name. As long as it is derive from NancyModule, Nancy will find it. Here is how I want Nancy to return back index.html for the root URL.

 

 

By default, Nancy will look at static content like JavaScript files, css, images, and so on in /Content folder only. But we already have those static files that Durandal needs in App folder. So to make Durandal works, we need to tell Nancy to look at those folders as well by adding those folders to StaticContentsConventions which can be done in Nancy Bootstrap process. We can do that by creating a class derived from DefaultNancyBootstrapper and add some code.

 

 

Here is how our project looks right now.

005-EDT-Minimum-Final

 

Now, let’s run the web app. And you should see our very simple web app

image 

To make our web app a bit less trivia, I will add another Durandal view and module which will do some AJAX call to get JSON data from the server. Here is the code in the new module.

 

 

The page is expecting the server to send JSON when it hits /api/list. With Nancy, we can do that easily by adding just couple lines of code.

 

 

Now. let’s run our web app again and click the new link!

image

Wow! super easy, right?

 

So far, we just have our client-side and server-side code taken care. However, you probably notice that our web app doesn’t look good at all. This is how Bootstrap can help. By using its reusable CSS templates, we can make our web app looks much better with ease.

Before we can do that we have to install Bootstrap package.

image

 

Next, we bootstrapify our pages by adding Bootstrap CSS class to HTML elements in our Durandal views. Besides reusable JavaScript/CSS components, there are many things that Bootstrap can help, most notably, the grid layout system.

image

 

Let’s run our web app again.

image

 

That’s it. Using Durandal, Nancy, and Bootstrap, we have a super-duper-happy SPA web app done right! :-)

 

For the full source code, please see my github repo. I have each step in git branches as well. If you want to see the site in action, I also set up the Windows Azure web site here,

Happy coding!

Add Code Syntax Highlighting to your Ghost blogging site

If you have followed my posts about setting up Ghost blogging site on Windows Azure and adding Disqus comment and changing your Ghost site theme, you probably notice that code block that comes with Ghost is very plain and has no syntax highlighting.

019-Code-Block

Don’t worry, you can easily add syntax highlighting to your ghost site. There are many ways to do that, but in this post, I will use google-code-prettify.

In this sample, I use the default casper theme, so what I need to do is to add

<script src="https://google-code-prettify.googlecode.com/svn/loader/run_prettify.js"></script>

to content/themes/casper/default.hbs (NOTE: put where the main script tags are. Other themes might require you to put the script tag above in different line). As usual, I will just use Visual Studio Online to update the code.

image

However, instead of using 4 spaces of indentation to create a code block, you will need to put something that is similar to GitHub Flavored Markdown. Here are samples for C# and F# code respectively (NOTE: Highlighting also works with other popular languages like JavaScript, XML, C++, and so on).

image

And here is out post with nice code syntax highlighting for both C# and F# code.

image

Happy Blogging!

Changing Ghost theme and add Disqus comment

Last post, we have set up the Ghost blogging site on Windows Azure. In this post, we will continue customizing our Ghost site by changing the theme as well as add Disqus comment.

By changing the theme, you can either fork the default casper theme and modify it or you can look for a new theme at the Ghost’s market place.

008-Marketplace

Basically, what we have to do is to download the theme and copy the whole folder to content/themes folder.

To copy files to our Windows Azure web site, the easiest way is to set up your deployment credentials if you haven’t done it already and use FTP client (like SmartFTP or Filezilla) to copy the theme folder.

Once you copy the theme folder (you might need to refresh the setting page), and you should see those new themes.

012-Select-N-Coded-Theme

Here is the N-Coded theme.

013-After-Theme-Change

 

Ghost doesn’t come with commenting capability. However, we could easily add Disqus comment to our blogging site. With Disqus, you can moderate commenting on any of your sites.

First, let’s go to disqus site and add your blogging site information.

014-Add-Disqus

 

For Ghost, select the Universal Code.

015-Disqus-Universal

Then, Disqus should give you the HTML and JavaScript that you can copy and paste to your web site.

image

 

For Ghost, what we need to do is to copy the code block to the post.hbs in the theme folder. In this example, we will copy the code block into between {{/post}} and </article> in the file content/themes/N-Coded/post.hbs. If you change the theme later, don’t forget to copy the code block to file in the new theme.

017-Add-Disqus-N-Coded

 

In the above screenshot, I use the Visual Studio Online or “Monaco” which can be integrated with your Windows Azure web site. However, you can still modify the theme file on your machine and upload it via FTP.

Now you should see the Disqus comment section under your post!

018-Post-with-Disqus

I think I like Ghost more and more. Hopefully, I have more cool stuff about it to share in the future posts.

Happy New Year!

Set up Ghost blogging site on Windows Azure Websites

Only one desktop application that I miss on Windows RT is the Windows Live Writer. WLW works well with blogging sites like WordPress and making writing blog post a breeze.

While monitoring my twitter feed talking about WLW, Scott Hanselman has mentioned Ghost and MiniBlog which is a dedicated blogging platforms. Both Ghost and MiniBlog looks great to me, but I am interested in markdown and node.js, so I am trying Ghost first.

(By the way, there is nothing wrong with WordPress in my opinion and I am posting this blog post to WordPress using WLW.)

Ghost is an open source blogging platform built on node.js. You can install it locally on Windows, Linux or Mac to try it out. If you have Windows Azure account (or plan to create one), I will show you how to create a Ghost site the easy way. If you are up to challenges, you can also do it the hard ways.

Let’s start

1. First, we create an Azure Web site and select “From Gallery” option.

001-CreateAzureWebsite

2. You should be able to select Ghost on the list. It’s currently version 0.3.3, but version 0.4 should be released anytime soon. (UPDATE: As of 1/29/2014, Ghost 0.4 is available on Azure’s Gallery now!)

002-Ghost

After you select Ghost, you will need to specify Azure web site and Ghost configuration. As of now, email is required so Ghost can send reset password email only.

003-ConfigureGhost

3. You should have the ghost site ready now (so easy :-)).

004-Ghost-Welcome

4. Great! But your job is not done yet. You need to go to [your site]/ghost and set up an admin account.

005-Ghost-Admin

Once you have an account, you can look around the admin pages.

006-Ghost-Admin-002

5. And here is my favorite part about Ghost, the side-by-side Markdown editor. Let’s write and publish something.

007-ghost-edit-publish

That’s it. Creating a Ghost site on Windows Azure is pretty easy. You could have the Ghost site up in less than 10 minutes. And the best part, you can have 10 web sites on Windows Azure free :-)

Next time, I will show you how you can change the site theme and allow comments on your ghost site. Happy New Year!

UPDATE: I have add more posts about Ghost if you are interested to see more:

Changing Ghost theme and add Disqus comment

Add Code Syntax Highlighting to your Ghost blogging site