Tag Archives : Functional Programming

Monadic Philosophy

(Since I accidentally published part one of this series a few minutes ago, I figured I might as well start publishing the series.)

If you start learning functional programming, eventually you’ll come across the idea of a monad. Coming from the object/imperative world of languages like C#, I’ve had a hard time wrapping my head around this concept. There’s no shortage of monad tutorials out there, but most use Haskell’s IO as the prototypical example of a monad. Given that I don’t know Haskell very well, I found it hard to separate the Haskell stuff from monad stuff. So I set monads on the back burner and decided not to worry about them.

However, all that changed when Stephan Tolksdorf alerted me to his very cool monadic parser combinator library FParsec. I found the FParsec parsers much easier to read my F# parser efforts, so I became very interested in monadic parser combinators. As you might guess, a “monadic parser combinator library” makes heavy use of monads. Time to switch burners.

The problem with learning monads with FParsec is that it’s really designed for production use. I needed to break monads down to first principles, so I rolled my own monadic parser library. Make no mistake, if I were looking to build a production parser in F# right now, I’d use with FParsec. My monadic parser library might “get there” eventually, but right now it’s a toy.

Over a series of posts, I’m going to describe what I know about monads. I didn’t set out to write a tutorial on monads – as I said, there are plenty of them out there. However, I found most of the the many monad tutorials I read lacking because the did a good job explaining the “how”, but not such a good job on the “why”. Coming from an imperative world, I wanted to understand the philosophy better. That being said, there’s a lot of tutorial in and around the philosophy. Hopefully, you’ll find both useful.

Morning Coffee 167

  • If you’re a gamer, you’re probably already well aware that E3 is this week. The Too Human demo has already been released. I have a friend who’s been working on “something” that will be announced today (I think).
  • Live Mesh folks pushed out an update Friday. Among the new features is the ability to sync folders among peers but NOT up to the cloud. This is cool because it means I can sync my many many GB of pictures and music on my home machine backed up with Carbonite. This means I can sync them without blowing thru my 5GB Mesh storage limit.
  • It looks like there’s a new F# drop – as usual there is no announcement or details as to what’s new. Release notes guys, look into it.  UPDATE – Don Syme blogged the release, and it’s pretty minor. a .NET FX 3.5 SP1 bug fix, a fix for Mono, and they removed WebRequest.GetResponseAsync to make F# work on Silverlight. And the release notes are in the readme. My bad.
  • Speaking of F#, it was “partially inspired” by OCaml, so when I see papers related to OCaml, I immediately wonder if I an apply the described techniques to F#. “Catch me if you can, Towards type-safe, hierarchical, lightweight, polymorphic and efficient error management in OCaml” is one such paper. (via LtU)
  • Speaking of functional programming, Matthew Podwysocki posted a bunch of FP links as well as a Code Gallery Sample on FP in C#. Good stuff.
  • As per Scott Guthrie, it looks like there’s a new ASP.NET MVC drop coming this week.
  • Based on posts by Ted Neward, Dare Obasanjo and Steve Vinoski, Google Protocol Buffers sounds like it’s going to be a dud. Note, I haven’t looked at it depth personally, I’m just passing on opinions of some folks I read and trust.
  • Speaking of Dare, both he and James Hamilton take a look at Cassandra and come away impressed. I wonder how easy it is to code against from Python and/or .NET?
  • Bart de Smet has a cool sample of calling out to PowerShell from IronRuby via the backtick command. Pretty cool, but it would even cooler to show how to call out to PS and return .NET objects to Ruby (though that would probably not be spec compliant for the backtick command).
  • Here’s a MS code name I had never heard before – Zermatt. It’s “a framework for implementing claims-based identity in your applications.” (via Steve Gilham)

Morning Coffee 162

  • Another nice thing about the new job: I’m working in the vicinity of some good friends. I was over in building 42 yesterday and made it a point to stop by Pat Helland‘s office yesterday and spend an hour or so chatting about the new gig. Pat is down the hall from David Hill, whom I worked with on Architecture Strategy. Back in my building, we’re down the hall from the VSX folks including my friends Ken Levy and Gareth Jones. I’m sure there are more folks I know around, but hey it’s only my second week!
  • I’m a big fan of Carbonite, which I use to back up all the digital media on my home computer. With two little kids, we have lots of digital photos as you might imagine . However, one thing that bugs me about Carbonite is that it doesn’t back up video files by default, you have to go in on a folder by folder basis and select “‘Back up Video files in this folder” from the context menu. Given how much trouble this “feature” has given me, I imagine less techie folks don’t even realize their video files aren’t getting backed up. However, I will say the latest version of the Carbonite Software at least makes it easy to find files that aren’t backed up. A quick sweep revealed around a dozen folders that had un-backed-up video files in them, which I promptly fixed.
  • The big news yesterday was the new Google App Engine, which looks to give you access to virtualized infrastructure that sounds similar to what GOOG is rumored to use internally. I like Dave Winer’s comment that this enables “shrinkwrap net apps that scale that can be deployed by civillians.” Given Google’s history w/ Python – Python’s BDFLGuido van Rossum works there – it’s no surprise that Google App Engine (GAE?) runs on Python, though apparently they “look forward to supporting more languages in the future”. I’m guessing “more languages” == Ruby, maybe Erlang too.
  • I wonder if/how Google App Engine will affect Ruby on Rails momentum? If there’s a significant lag before App Engine supports Ruby, will that drive developers to Python web stacks like Django? (Django is included in “the box” with App Engine)?@ PyCon, I was surprised at the intra-language animosity I observed. I wonder how many Python developers are secretly hoping Google never ships Ruby support. I highly doubt Google would do that – they want to tap the exploding RoR market like everyone else – but I’d bet it would really take the wind out of Rails’ sails if they did.
  • Today’s Michael Foord Link: Embedding IronPython 2, Examples of the DLR Hosting API. You can read the DLR Hosting spec, but it’s pretty out of date so Michael’s article helps fill in some of the gaps.
  • Looks like PowerShell has gotten the open source community treatment in a project called Pash. While I’m sure others are excited about PS on Linux or Mac, I’m excited to see PS running on Compact Framework. I wonder if it would work with XNA?
  • Speaking of XNA, XNA Console is a new CodePlex project that provides an IPy console to manipulate your XNA based game on the fly. Python is no stranger to game development – Civ IV for example provided mod capabilities via python. Alas, the compact framework can’t run IPy today, so neither can XNA on Xbox. But wouldn’t it be cool to hack your game in IPy running on a 360 using the messenger kit? (via IPy URLs)
  • Bart De Smet gets functional, writing type switch and pattern matching in C# 3.0. I guess it works, but it sure is ugly. Why not just use F# and be done with it?
  • Soma announces that the VC++ Feature Pack has shipped. Somewhere, I assume, there is much (some?) rejoicing.

Morning Coffee 157

  • My Xbox 360 started flashing the dreaded Red Ring of Death on Friday. <sigh> I’m not going to have much time to play in the next week, so it’s not the end of the universe, but I did have to dig an old DVD player out of the garage for interim duty.
  • My Caps really stepped in it over the weekend dropping two games they had to have and by most reports (aka according to my dad) that they dominated most of the way. Caps Playoff Math isn’t as dire as say Clinton’s Nomination Math, but they are three games back of the Hurricanes with twelve to play.
  • Ted Neward has a pretty good F# overview article in the most recent MSDN Magazine. I say pretty good because I wonder if someone with no functional programming experience will “get it”. As much as I like F# and functional programming, I think some of the basic concepts don’t pass Don Box’s two beer test.
  • Speaking of Ted, somehow his feed fell off my radar (bad DevHawk!) and I missed several great posts like Modular Toolchains (note to Ted, check out A Research C# Compiler), Why we need both static and dynamic in the same language (note to self, check out Cobra) and The Fallacies Remain…. (recently, I’m the guy shouting about risks).
  • Speaking of MSDN Magazine, have you seen their new site redesign? I can’t find any announcement of it, but man the site looks great.
  • If you missed MIX, the sessions are all online already. That was fast.
  • John Lam blogs about the availability of the Dynamic Silverlight bits. Apparently, Dynamic Silverlight includes more recent bits than the Silverlight 2 SDK, which does includes binaries and tools for IronPython, IronRuby and Managed JScript (quickstart). So you can get started with dynamic languages on Silverlight using the SL SDK alone, but I expect that the Dynamic Silverlight bits will be updated more regularly than the SDK.

Play Ball Script in F#

Scott Hanselman wanted an F# version of this Play Ball! round-robin scheduling PowerShell script. Here’s what I came up with:

let randomize list = 
    let random = new System.Random()
    let list'=  
        |> List.map (fun i -> (random.Next(), i))
        |> List.sort (fun (i1,_) (i2,_) -> Int32.compare i1 i2)  
    let (_,list'') = List.unzip list' 

let rec makeGames teams = 
    match teams with
    | first :: rest ->
        [for team in rest -> (first, team)] @ (makeGames rest)
    | [] ->  []

let teams = ['a'..'f']
let games = teams |> makeGames |> randomize

MakeGames uses pattern matching to see if the list of teams is empty or not. If the list is empty, we simply return an empty list of games. If not, we use F#’s list comprehension syntax to generate a list of games between the first team in the list and each of the remaining teams. This list is combined (via the ‘@’ operator) with the results of calling makeGames recursively. This generates the un-randomized list of games.

Once we have the list of games, we need to randomize it. I ported the randomize function above over from a version I found in Erlang. Basically, it attaches a random number to each element in the list to be randomized, sorts by those randomly generated numbers, then throws the numbers away and returns the just the randomized list. Note, the Erlang version I referenced runs randomize log(length of list) times to ensure a fair shuffle, but I thought once would be enough for this simple script.

(Note to F# team: perhaps List.randomize should be a part of the standard F# library?)