Rick Minerich's Development Wonderland : recursion

F# Discoveries This Week 05/02/2010

RickM — Sun, 02 May 2010 21:43:06 GMT

Back this week with another huge batch of F# links. While there’s way too much great stuff to mention, my favorite this week is by a mysterious blogger known only as James. His heat transfer model is short, sweet and very well explained.

If you’re around Boston tomorrow (Monday) be sure to check our F# panel for .NET Rocks! With over 100 people already signed up, it’s sure to be a great time.

The .NET Rocks! Visual Studio Road Trip – F# Edition in Boston (5/3/2010)

Carl and Richard are loading up the DotNetMobile (a 30 foot RV) and driving to your town again to show off the latest and greatest in Visual Studio 2010 and .NET 4.0! This stop will include an intro to F# and a special topic panel discussion on F# featuring New England F# User leaders.

Rob Knies’ F#: Putting the 'Fun' into 'Functional' (On Dr. Dobbs)

"In the F# team," says Syme, a principal researcher at Microsoft Research Cambridge, "We say, 'F is for Fun.' F# enables users to write simple code to solve complex problems. Programming with F# really does make many programming tasks simpler, and our users have consistently reported that they've found using the language enjoyable."

James’s Modelling heat transfer in F# using 100 lines of code

In this post I’m going to show how we can model the heat equation succinctly in F#. I’m going to consider the two-dimensional case and approximate the solution at discrete spatial mesh points and at discrete time periods.

Brian McNamara’s Game programming in F# (with Silverlight and WPF)

I wanted to learn more about Silverlight, WPF, and Xaml (in the context of F#, of course), so I wrote a fun little game you can play in your browser (or on your desktop). It’s a knock-off of a dozen other similar games, as you can probably tell from this screenshot

Martin Doms’s Implementing the Mandelbrot set in F#

One of my favourite things to do when learning a new language (or graphics package for that matter) is to write an implementation of a Mandelbrot set viewer. So here’s my F# version, annotated to help out anyone who is trying to get to know this language.

Dmitry Lomov’s Finer Points of F# Value Restriction

Type inference algorithms are a fascinating topic – there is an interesting and beautiful theory behind them. Today we will consider one interesting aspect of type inference in F# - it might give you a glimpse of what kind of challenges coming up with a good algorithm in this space presents, and hopefully explain away a stumbling block that F# developers occasionally encounter.

Frank is a functional reactive request/response engine for .NET applications (written in F#)

Frank is inspired by the Ruby dynamic duo of Rack and Sinatra and aims to provide the simplicity of those frameworks but utilizing the powerful functional reactive paradigm for asynchronous processing.

Steve Gilham’s Launching an F# web application inside VS2010 as if it were C#

This is a follow-up to my comments on VS launcher for F# web apps, where I can put an example of the changed markup to the F# class library project to make it act like a web project and launch a browser with your Default.aspx page when you hit F5.

Phillip Trelford’s UML Sequence Diagram: F# Script

Yesterday I fancied moving some hand drawn diagrams to mouse drawn form; but instead found myself battling against a somewhat stubborn and forgetful modelling tool. It left me wondering if there might be an easier way to do this; perhaps by separating the concern of model description from layout.

Daniel Mohl’s A Distributed Hash Table (DHT) in F#: Recursion and Pattern Matching

The simplest implementation defined in the Chord Protocol requires that each node only know about its successor node. The circle of nodes, joined by each successor node association, makes up the node cluster. In order for a node to become part of the node cluster, it must execute a join request to any arbitrary node in the cluster.

Daniel Mohl’s Interacting with RabbitMQ via F# and Symbiote

Last week, I showed how easy it is to talk to CouchDB with F# and Symbiote. In this post, I'll show how you can start interacting with RabbitMQ by adding an additional dozen or so lines of code.

Steffen Forkmann’s Solving KataYahtzee with F# and NaturalSpec

Today I’m starting a new blog post series about solving code katas in F# and with the help of my NaturalSpec project. A code kata is a programming exercise which helps to improve your skills through practice and repetition.

Robert Pickering’s Strings and F# Immutable Lists

The aim of the article is to show that this is not the case, or at least it’s not as black and white as you may think. Specifically we’re going to compare how.NET strings differ considerable in performance characteristics to F#’s immutable lists.

Andre Burdette’s F# Screencast Series

This is the first of future screencasts that I am doing regarding F# programming. In this screencast I show how to use values and functions in the F# language. Enjoy!

Neil Carrier’s A Spell-Binding Tale of Three Recursions

Tail recursive functions often involve accumulators, continuations, and other values which are not really of concern to the ultimate users of those functions. These can often be curried away or otherwise hidden from the ultimate user. This post looks at three obvious techniques for doing so (there are some more that are less obvious), the differences between the three techniques, etc.

Neil Carrier’s Driving Range Pooled Allocator

Large numbers of small allocations can be brutal on a memory management system, especially in terms of CPU time (and in terms of fragmentation on non-GC systems). This post presents an F# implementation of a pooling algorithm I’ve used for many years, and in various languages from C onwards, to solve this problem.

Julien Ortin’s Technical analysis indicators in F# – Misc and Volatility

This is part of a series on technical analysis indicators in F#, based on the multi-language TA-Lib. Quick disclaimer: some of these indicators are not verified.

Vladimir Matveev’s Nature of value restriction

Value restriction is an error that firstly makes a direct hit in the brain of non-prepared developer. It has no straight analogues in the majority of mainstream languages and thus very confusing.

Vladimir Matveev’s MailboxProcessors: Practical Application

Last time we have examined the API of MailboxProcessors. Now it is time to see, how this concept can be applied to solve real-world problems.

Doug Finke’s How to add an F# type to a PowerShell session

The PowerShell Add-Type cmdlet lets you define a .NET Framework class in your Windows PowerShell session. It supports the following languages CSharp, CSharpVersion3, VisualBasic, JScript. It does not support FSharp directly.

Mark Pearl’s F# Objects Part 1, Part 2 and Part 3

In the next few blog posts I am going to explore objects in F#. Up to now, my dabbling in F# has really been a few liners and while I haven’t reached the point where F# is my language of preference – I am already seeing the benefits of the language when solving certain types of programming problems.

Mark Pearl’s International Radio Operators Alphabet in F# and Silverlight Part 1 and Part 2

My approach was really simple. I would need a function that would convert a single character to a string – i.e. ‘A’ –> “Alpha” and then I would need a function that would take a string of characters, convert them into a sequence of characters, and then apply my converter to return a sequence of words… make sense?

Mike Hadlow’s Currying vs Partial Function Application

There’s a lot of confusion over these two terms. By myself included. But I’m pretty happy now that I understand the difference and wanted to share my newfound knowledge with you, dear reader.

Bjorn Rochel’s Kata FizzBuzz in F#

Last F# book club meeting in Munich was awesome (as usual). 2 weeks ago we decided to do a Code Kata on each subsequent meeting. This week was our first, with Kata FizzBuzz. This is what we came up with.

Jim Lehmer’s Your language ain’t worth a pair o’ dimes

That's not to say the Real World Functional Programming book is a bad book. It has been an interesting read so far, for sure. I am just going to stop reading the C# parts, thereby allowing the new concepts and new language I am learning to be "pure" in my mind, which should actually help speed up my learning process. And my suggestion to you is if you pick up the book, do the same thing, too. Dump your baggage, start fresh!

Rick Minerich’s The Ted Neward F# Folding Challenge

Take a list of numbers and compress it in a particular simple way but without any mutable state. What makes this problem interesting is that a tech interviewer mentioned that that he hadn’t seen a functional solution to this problem. I also wanted to share this because I think it’s a great example of how to convert an imperative loop into a functional fold.

F# Discoveries This Week 02/08/2010

RickM — Mon, 08 Feb 2010 19:28:41 GMT

Back again with another F# community roundup. There’s been a ton of great content this week, almost too much. To try to combat this I’ve attempted to sort posts roughly in terms of how interesting I found them. All were worth the read though.

Also, I’ll be speaking this Wednesday on F# at the Boston .NET User Group. If you find yourself there, be sure to say hello!

Don Syme’s Introduction to F# (Video 1 of 3)

Dr. Don Syme is a principal researcher in MSR Cambridge. He has a rich history in programming language research, design, and implementation (C# generics being one of his most recognized implementations), and is the principle creator of F#.

Ashley Feniello’s FScheme Part 8: Language vs. Library

Perhaps this post should have gone along with the one about macros and how Lisp is a “programmable programming language.” The common tension in any language or runtime design is how much to build in as primitives and how much to implement as libraries within the language or atop the runtime.

Luke Hoban’s F# for Parallel and Asynchronous Programming

Last November at PDC 2009 in Los Angeles I gave a talk on F# for Parallel and Asynchronous Programming. The talk begins by covering basic F# concepts, and then focuses on four challenging issues related to concurrency and the tools F# brings for addressing these - immutability, async workflows, and agents.

Andrew Brehaut’s On Iteration (Could just as well be entitled “Why Programmers Leave Python/C#/Java")

There is an observable trend in Python programmers that results in a reasonable section of them moving to functional programming languages. This trend is encouraged by the Python language, and has a couple of temporal considerations.

Matthew Podwysocki’s Using and Abusing the F# Dynamic Lookup Operator

Much like C# 4.0 has the ability to do dynamic lookup, F# also has the same capability, although in a different capacity. The language has support for a dynamic lookup get operator ( ? ) and set operator ( ?<- ), but note that I said support and not actual implementation. The actual implementation is up to you and how you want to use it.

Matthew Podwysocki’s A Kick in the Monads – Writer Edition

In the past couple of Monads posts, we’ve talked briefly about the State and Reader Monads and their potential uses and misuses. Before this series completes, I have a few more to cover including the Writer, Continuation and eventually Observable monad. Today, we’ll get started looking at the Writer Monad and what it can do for us.

Ashley Feniello’s Recursion Is the New Iteration

Not all recursive expressions represent recursive behavior. In fact, iteration can be expressed recursively. One trick when considering the process that an expression represents is to think of functions as reducing to values rather than returning them. In a pure functional style (precisely because of referential transparency) you can do analysis by successive substitution.

Julien Ortin continues his series on Purely Functional Data Structures with a Real-time double-ended queue, a Skew binary random access list and a Binary random access list

This post describes the F# implementation of the <insert data structure here> from Chris Okasaki’s “Purely functional data structures”.

Flying Frog Consultancy Presents - John Conway’s Game of Life in 32 lines of F#

John Conway's Game of Life is a famous example of a simple cellular automaton that produces remarkably diverse results. The game can be implemented in only 32 lines of F# including real-time visualization using Windows Presentation Foundation as follows:

Brian McNamara’s An RSS Dashboard in F# (Part 3)

Last time I covered IObservables and we created a useful ObservableSource class. Today I’ll cover the next technology piece of the app: reading RSS feeds. I’ll discuss the design considerations regarding how to poll feed for updates and publish feed items as IObservables, and walk through one implementation.

Nick Gravelyn’s Pong in F# with XNA Game Studio

A few of my colleagues were discussing F# today and when/where/how it is/isn’t better than C#. I haven’t ever really used F# beyond a very, very brief look at the syntax, so tonight I decided to see what it was all about. As a little project, I decided to make Pong with XNA Game Studio using F# with Visual Studio 2010.

Jim Burger’s Maybe F# isn’t for you…

If you aren’t excited about new ways to tackle the concurrency problem, or new approaches to handling generic and mathematical problems, and if the thought of breaking out the shiny new lexer and parser don’t give you a tingle, then maybe F# isn’t actually marketed at you at all.

Alex Turner’s Calling F# from COBOL and Back Again (CodeProject)

Running languages on .NET is ultra-powerful. Using managed COBOL (from Micro Focus), it is possible to use F# code to work with COBOL code. Imagine a Cloud based F# map reduce system consuming legacy COBOL - yes, that really is on the horizon.

Steffen Forkmann’s New syntactic sugar for “FAKE – F# Make”

The new version 0.27 of “FAKE – F# Make” comes with new syntactic sugar for build targets and build dependencies. Don’t be afraid the old version is still supported – all scripts should still work with the new version.

Jared Parsons’s Having fun with events in F#

Recently I ran into a situation where I needed to handle some events in F# in a special way. In this particular case I wanted to be able to disable and re-enable my handler based on changes in the program. Essentially the C# equivalent of continually adding and removing the handlers.

Steve Gilham’s “Hello Glade#” from F#

Another bit of spiking, a rather tardy follow up from raw GTK#, starting from the C# example at the Mono Project site, but incorporating the earlier example, so as to build in a clean application exit, for one thing.

Luis Diego Fallas’s Using a Webcam with WIA and F#

In this post I'm going to show a small example of taking a picture using a Webcam with Windows Image Adquisition 1.0 . This API seems to have changed in Vista and above, the following code only applies to XP.

Flying Frog Consultancy’s WPF Tic-tac-toe demo

The article walks through the design and implementation of a multithreaded program that uses logic programming to create an unbeatable computer opponent and Windows Presentation Foundation to provide a graphical user interface in only 115 lines of elegant F# code!

A (Relatively Reasonable) Discussion of F# on Slashdot

OCatenac passes along an interview with Don Syme, chief designer of F#, which is Microsoft Research's offering for functional programming on the .Net platform. Like Scala, which we discussed last fall, F# aims at being an optimal blend of functional and object-oriented languages.

F# Discoveries This Week 11/09/2009

RickM — Mon, 09 Nov 2009 16:24:59 GMT

As momentum builds for the F# release with Visual Studio 2010, so too does the number of people blogging about the language. This week we have a spec update, clarified comparisons, decision trees, porting gotchas and in depth explorations of the debug IL generated by F#. Please do enjoy.

Speaking on F# at the Connecticut .NET Developer’s Group

Tomorrow (Tuesday November 10th, 2009) I’ll be speaking on F# at the Connecticut .NET Developer’s group. For more information check out the ClickToAttend event.

From Don Syme’s Blog - F# Spec Updated for the 1.9.7 Release

Many thanks to all those who sent so much helpful feedback on the specification during Beta1. And for those using 1.9.7 already, thanks for your patience in the last couple of weeks - it took us a little longer to get this out the door than we had planned, since a development deadline for Visual Studio 2010 intervened.

Don Syme’s Equality and Comparison Constraints in F#

F# 1.9.7 introduces two new constraints to the F# language to help uncover issues in your code when using equality and comparison operators. In this blog entry we'll take a look at these constraints in a bit more detail.

The F# team has inherited quite a mess in terms of the lack of any kind of concrete definition of equality in the .NET framework. It seems that they’ve been able to do much with it though.

Chris Smith’s Decision Trees Part 1 and Part 2

Now that we got all that painful math out of the way, let’s write some code! Here is an implementation of the algorithm in F#.

I’m just dying to see this extended to Bayesian network. Perhaps I’ll try and extend it myself.

Bart De Smet’s Stack-Friendly Recursion

Recursion is a widely known technique to decompose a problem in smaller “instances” of the same problem. For example, performing tree operations (e.g. in the context of data structures, user interfaces, hierarchical stores, XML, etc) can be expressed in terms of a navigation strategy over the tree where one performs the same operation to subtrees.

A detailed look at tail recursion optimization in F# and how to achieve something similar in C#.

On StackOverflow, is a program F# any more efficient (execution-wise) than C#?

I'm guessing that it is not because they both boil down to the same IL.

It turns out that F# is in fact much faster in some cases. For more on F# performance see this roundup post.

Steve Gilham’s F# under the covers parts 1, 2, 3, 4, 5, 6, and 8

I'm in the tidying up stages for the little project I've been working on lately, a set of FxCop rules, mainly aimed at providing some complementary features for nCover-style code coverage, including static analysis for trivial methods -- or compiler generated ones.

In this series Steve takes a very careful approach to exploring the IL generated by the F# compiler in debug mode.

Matt Moloney’s Lessons Learned in Porting [from] C# to F# (WPF)

I encountered a ton of difficulties while porting code from C# to F#. Fortunately / unfortunately, so have many other people. Thankfully they took the time to write about these problems so my solutions were often only a quick search away. Here is a collection of some of the finds that were able to help me in my endeavors.

An excellent post well worth reading for anyone getting ready to port to F#.

Discoveries This Week 08/02/2009

RickM — Mon, 03 Aug 2009 03:57:00 GMT

Tomorrow Matthew Podwysocki will be speaking at the New England F# User Group. I also have some great links today with Don Syme at QCon08, why we need the rec keyword, regular expression parsing and graphing with GLEE.

Tomorrow @ FSUG: Matthew Podwysocki on Parallelism in F#

With the increasing amount of data available to us, we need new ways of thinking around how to create scalable solutions in order to best exploit it.

I’m a long time fan of Matt’s blog and am looking forward to see him speak. We’ve gotten most of the bugs out of our video workflow and so I hope to have his talk up on the New England F# User Group site early this week.

Don Syme at QCon08, F# – Succinct, Expressive, Efficient Functional Programming for .NET

Don Syme presents F# basics, a typed functional language for .NET that combines the succinctness, expressivity, and compositionality of functional programming with the runtime support, libraries, interoperability, tools, and object model of .NET.

I’m always happy to find another instance of Don Syme speaking. In this talk he focuses on why functional programming is worth Microsoft’s investment in time.

Code Crafter, F#: Why the rec?

One of the first things that I noticed is that in order to declare a recursive function you have to be explicit about it in the function definition. You have to declare it with the rec keyword. […] But I don't know why they didn't do this by default.

Interestingly enough, it turns out that the reason for the rec keyword is required is due to the way Hindley-Milner type inference algorithm handles mutually recursive functions. Without the keyword the algorithm would be unable to generalize types appropriately.

Steve Horsfield, F#: Building a Regular Expression Pattern Parser

One of the habits of a good functional programmer is to use tail-recursion. This allows the compiler to convert recursion into iterative methods that can handle any length of input. I have attempted to use this. […] I have also structured the code into modules to demonstrate some of F#’s features in this regard.

Beautifully structured code for a first stab at F#.

Steve Horsfield, F#: A Data Structure For Modelling Directional Graphs and F#: Graphing with GLEE

In my previous post, I described how to parse a regular expression pattern into an abstract syntax representation. The next phase is to transform the parsed syntax into a finite state machine. I have chosen to model the FSM as a mathematical directional graph (digraph). This post describes the implementation of this module in preparation for the actual compilation step.

Another excellent couple of samples from Steve. I had not seen GLEE in the past and have had a number of projects in which it would have been quite useful.