# F# – Monty Hall problem

Do you remem­ber that scene from the movie 21 where Kevin Spacey gave our pro­tag­o­nist Ben the game show host problem?

What Kevin Spacey described is known as the Monty Hall prob­lem. It became famous as a ques­tion from a reader’s let­ter to Mar­i­lyn vos Savant’s “Ask Mar­i­lyn” col­umn in Parade mag­a­zine in 1990.

Marilyn’s answer caused quite a bit of con­tro­versy at the time and whilst I don’t under­stand the for­mal math­e­mat­i­cal proof, it’s a prob­lem that can be eas­ily proved through simulations.

## Sim­u­la­tion with F#

First, let’s set up a few types to rep­re­sent the prob­lem domain:

Pretty self-explanatory here:

• behind every Door is a Prize;
• the Prize is either a Car or a Goat;
• you Win if you get the Car in the end, oth­er­wise you Lose

When you start a new game you always have three doors, arranged in some ran­dom order.

After you had given your ini­tial choice, the game show host will reveal one of the doors that has a Goat?.

Here we have a func­tion that takes in the doors and the player’s ini­tial choice; and return the index of a door that:

1. the player didn’t choose; and
2. has a goat

Putting it together, we have a func­tion that takes in the doors as well as the player’s strat­egy and return whether the player Win or Lose at the end of the game.

From the code above you can guess the type sig­na­ture of the strat­egy func­tion to be int –> int –> int. That is, it takes two inte­gers – the player’s ini­tial choice and the index of the door the host has revealed – and return the player’s final choice.

Now, given the two choices we have – to stay or to change, we can rep­re­sent it with two strategies:

• strat­e­gyA would stay with the player’s orig­i­nal choice;
• strat­e­gyB would change

We can now use these two func­tions to call play with.

p.s. notice we have essen­tially imple­mented the Strat­egy pat­tern, but with­out all the boil­er­plates and inter­faces and classes? With just func­tions! Isn’t that sweet?

To be kinder to our­selves, let’s add another helper func­tion that will take in our cho­sen strat­egy and run a sim­u­la­tion of 1000 games, and return the num­ber of games that we have won with this strategy:

Finally, let’s run our sim­u­la­tions and see how the two strate­gies perform.

Run­ning this sim­u­la­tion over and over, strat­e­gyB con­sis­tently out­per­forms strat­e­gyA by roughly 2-to-1, which is exactly what we expected.

You can also just run the sim­u­la­tion your­self on .Net Fid­dle here, just click the Run but­ton at the top.

## Improv­ing our code

Whilst the above is suf­fi­cient for its pur­pose and it’s a pretty short solu­tion, there’re cou­ple of things that can be improved in hindsight:

• player’s choice – to Stay, or Change – is not explic­itly rep­re­sented in the domain;
• whilst a Change can only lead to one out­come – chang­ing to the door that isn’t revealed nor ini­tially cho­sen – it is expressed implic­itly by the logic in strat­e­gyB;
• if we were to intro­duce another strat­egy (e.g. decide to stay or change ran­domly) then we’d have to dupli­cate the logic for change.

To make these improve­ments is really easy. We can start by adding a type to present the two choices avail­able to the player:

Then we can update the play func­tion to work with it:

So now, our strat­egy imple­men­ta­tions become much simpler:

Again, you can try out this updated ver­sion on .Net Fid­dle here. It also includes a ‘ran­dom’ strat­egy which chooses to Stay or Change using the rand func­tion we cre­ated earlier.

There are other things we can improve still. For instance, how do we encap­su­late the con­straint of hav­ing only 3 doors as part of our model?

This way, we can elim­i­nate another invalid state using the type sys­tem. I’ll leave that as a teaser to you  and feel free to share your solu­tion in the comments!

# Exercises in Programming Style–Style 1

NOTE : read the rest of the series, or check out the source code.

## Pro­logue

I was at Joy of Cod­ing ear­lier this year and one of the high­light for me was Crista Lopes’ keynote  Exer­cises in Pro­gram­ming Style.

Crista demon­strated how a sim­ple prob­lem of cal­cu­lat­ing term fre­quency can be writ­ten in a plethora of ways, including:

The point of these exer­cises is to allow you to see that there are many solu­tions to the same prob­lem, and that each comes with a set of con­straints that needs to be com­mu­ni­cated.

I really enjoyed the talk and bought Crista’s book so I can go through all 33 approaches in my own time!

It’s taken me a lit­tle while to find the time to do this, but I was finally able to make a start last week­end. Over the next cou­ple of weeks I hope to share with you my ports of Crista’s Python solu­tions in F# and my takeaways.

If you like what you see then please buy the book and sup­port Crista’s work!

## Style 1 – Good Old Times

This style was com­mon­place in early 50s when hard­ware lim­i­ta­tions had some hard constraints.

### Con­straints

• Very small amount of pri­mary mem­ory, typ­i­cally orders of mag­ni­tude smaller than the data that needs to be processed/generated.
• No iden­ti­fiers – i.e. no vari­able names or tagged mem­ory addresses. All we have is mem­ory that is address­able with numbers.

Get the source code here.

As you can expect, not being able to use iden­ti­fiers really stops you in your tracks and made an oth­er­wise sim­ple task so much more com­plex (also makes you appre­ci­ate the work of lan­guage and hard­ware design­ers that came before us).

The imple­men­ta­tion feels deeply unnat­ural due to the con­straints we have imposed on our­selves, and that’s kinda the point of these exercises.

The absence of iden­ti­fiers for instance, forces us to lump a bunch of global vari­ables into an array that acts as our ‘pri­mary mem­ory’ for the pro­gram and forces you to remem­ber which index cor­re­sponds to what.

This style is really at odds with how one would code in F# (prob­a­bly even more so than Python!), as by design F# nudges you towards code in a func­tional style — using immutable val­ues, recur­sion, using types to drive your pro­gram, etc.

# Warning, Conferences ahead!

Update 24/08/2015 : some help­ful peo­ple pointed out that I’ve missed a cou­ple of other notable con­fer­ences here, including:

It’s almost that time of the year again, that last stretch of the year when we have so many good con­fer­ences in UK and Europe.

## Sep­tem­ber

First we have quite a treat in Kats Conf, on the 12th Sep in Dublin. An unbe­liev­able list of speak­ers include Joe Arm­strong, Francesco Cesarinni, Edwin Brady, Amanda Laucher and Phil Trelford!

Ses­sions span across a num­ber of FP lan­guages – Erlang, Scala, F#, Idris to name a few.

What’s more, it’s great value for money. Ticket is only 25 euro, and if you fancy going to Erlang Fac­tory Lite the day before you can even get a combo ticket for 50 euro.

Shortly after Kats Conf, there’s Dev­Day in Krakow on 17th and 18th Sep, with some well known speak­ers in the .Net space includ­ing our very own F# machine learn­ing expert Math­ias Bran­dewinder!

Then on the 26th Sep, there’s DDD East Anglia over in Cam­bridge, a one-day free event that’s organ­ised by devel­op­ers for developers.

The pro­gramme is not out yet but looks like I’ll be giv­ing my “F# in the Real World” talk there.

Round­ing off a rather busy Sep­tem­ber, there’s code.talks in Ham­burg on the 29th and 30th Sep. I’ll be giv­ing my “Tour of Pro­gram­ming Lan­guages” talk there and I’m really look­ing for­ward to vis­it­ing Ham­burg for the first time.

## Octo­ber

Hot on the heels of OSCON in Port­land, it’s com­ing to Europe for the first time, in Ams­ter­dam on 26th and 27th of Oct.

Some pretty cool tech com­pa­nies will be there – GitHub, DataS­tax, Google, Thought­Works, Pay­Pal, Heroku and Spo­tify to name a few! I will be talk­ing about “Mod­el­ling Game Econ­omy with Neo4j” there.

Rachel Reese from Jet.com is also com­ing over from the US to talk about build­ing reac­tive ser­vices with F#!

## Novem­ber

CodeMesh has been my favourite con­fer­ence the last cou­ple of years and it’s the place to be to learn about emerg­ing tech­nolo­gies and lan­guages from some of the best peo­ple in the industry.

This year, you can learn from the likes of:

• Sir Tony Hoare (Tur­ing Award Winner)
• John Hughes (QuickCheck)
• Robert Vird­ing (co-creator of Erlang)
• Don Syme (cre­ator of F#)
• Joe Arm­strong (co-creator of Erlang)
• Evan Czaplicki (cre­ator of Elm)
• Ste­fan Karpin­ski (co-creator of Julia)
• William Byrd (co-creator of miniKanren)
• Bruce Tate (author of the 7 lan­guages in 7 weeks books)
• and F# super­stars Phil Trelford and Tomas Petricek!

Seri­ously, if you’re look­ing for a con­fer­ence that’ll chal­lenge you intel­lec­tu­ally (and hon­estly, hurt your brain a lit­tle!) then CodeMesh is the place to be on Novem­ber 3rd and 4th in London!

Over in Malmo, there’s also Ore­dev from Novem­ber 4th to 6th, which is a very well attended con­fer­ence with thou­sands of atten­dees each year.

I have heard plenty of good things about Malmo and Ore­dev, and it was per­son­ally rec­om­mended by Phil Trelford so you just know it’s gonna be good!

And this year there’ll be a good F# pres­ence, with Rachel Reese, Paul­michael Bla­succi, Evelina Gabasova and myself all talk­ing about F#

Oh, and Adam Torn­hill (who you might know as the author of Code as Crime Scene) will be there too.

Finally, Build­Stuff is hap­pen­ing again from Novem­ber 18th to 20th. It’s still early days and only a cou­ple of speak­ers have been con­firmed but already you can count the likes of Uncle Bob, Michael Feath­ers, Trisha Gee, Randy Shoup, Pieter Hin­t­jens and Kevlin Hen­ney amongst them.

Based on my expe­ri­ence from last year, I’m sure Build­Stuff is going to be great again this year.

With so many great con­fer­ences com­ing up, I’m really excited to be able to learn from some of the best peo­ple in the indus­try and hope to catch you at some of these events!

# More fun with APL

Note: see the rest of the series so far.

I stum­bled across this post the other day and prob­lem 2 seems like some­thing I can eas­ily do in APL since it essen­tially requires you to inter­leave two arrays.

The prob­lem is:

Write a func­tion that com­bines two lists by alter­nat­ingly tak­ing ele­ments. For exam­ple: given the two lists [a, b, c] and [1, 2, 3], the func­tion should return [a, 1, b, 2, c, 3].

Here’s the solu­tion I have come up with:

since it uses both $\omega$ (right argu­ment) and $\alpha$ (left argu­ment) so it’s a dyadic func­tion, let’s test it out:

$'a' \ 'b' \ 'c' \ p2 \ 1 \ 2 \ 3$

=> a 1 b 2 c 3

Here’s how it works:

• con­cate­nate the two argu­ments together, with the left argu­ment first $(\alpha, \omega)$
• reshape $\rho$ the con­cate­nated vec­tor into 2 rows, so that you have effec­tively placed $\alpha$ and $\omega$ into a matrix, i.e.

$a \ b \ c\\* 1 \ 2 \ 3$

• trans­pose that matrix

$a \ 1\\* b \ 2\\* c \ 3$

• reshape $\rho$ the trans­posed matrix into a vec­tor, and that’s it!

# My picks from OSCON keynotes

So OSCON came and went, and whilst I haven’t seen the record­ing for any of the ses­sions, the keynotes (and a bunch of inter­views) are avail­able on YouTube.

Unlike most con­fer­ences, the OSCON keynotes are really short (aver­age 10–15 mins each) and hav­ing watched all the pub­lished keynote ses­sions here are my top picks.

### Simon Ward­ley — Sit­u­a­tion Nor­mal, Every­thing Must Change

I’m a big fan of Simon’s work on value chain map­ping, and his OSCON 2014 keynote was one of the most mem­o­rable talks for me last year.

Simon started by point­ing out the lack of sit­u­a­tional aware­ness on the part of enter­prise IT. Enter­prise IT lives in a low sit­u­a­tional aware­ness envi­ron­ment that relies on back­ward causal­ity and ver­bal rea­son­ing (or story telling), and has no posi­tion or movement.

Whereas high-level sit­u­a­tional aware­ness envi­ron­ments (e.g. mil­i­tary com­bat) are con­text spe­cific, you have posi­tions and move­ments and usu­ally employ some form of visual reasoning.

Mil­i­tary actions are dri­ven by your sit­u­a­tional aware­ness of the where and why, but in Busi­ness we have a tyranny of actions.

and this is where Simon’s value chain map­ping comes in. With maps, you can add posi­tions to your com­po­nents based on the val­ues they pro­vide, as well as move­ment as they evolve from the unchar­tered world (chaotic, uncer­tain, unpre­dictable, etc.) to become industrialized.

In terms of method­ol­ogy, there’s no one size that fits all.

Agil, XP and Scrum are very good on the left side (the unchar­tered world), par­tic­u­larly when you want to reduce the cost of change.

On the right side, as things become indus­tri­al­ized, you want to reduce the cost of devi­a­tion and Six Sigma is good.

In the mid­dle where you want to build a prod­uct, lean is par­tic­u­larly strong.

If you take a large scale project, rather than hav­ing a one-size-fits-all method­ol­ogy, you can employ dif­fer­ent method­olo­gies based on where that com­po­nent is in its evo­lu­tion. For devel­op­ers, this is no dif­fer­ent to the argu­ments for poly­glot pro­gram­ming, or poly­glot per­sis­tence, because no sin­gle lan­guage or data­base is good for all the prob­lems we have to solve.

Why should the way we work be any different?

By over­lap­ping the value chain maps for dif­fer­ent areas of the busi­ness you can start to iden­tify over­laps within the orga­ni­za­tion, and a snip­pet from his most recent post shed some hor­ri­fy­ing light on the amount of dupli­ca­tion that exists:

…To date, the worst exam­ple I know of dupli­ca­tion is one large global com­pany that has 380 cus­tomised ver­sions of the same ERP sys­tem doing exactly the same process…

The US air force dis­cov­ered that, as peo­ple came up with new ideas they tend to add fea­tures to that idea and made it bet­ter (and more com­plex); they then added even more fea­tures and made the idea so com­plex it’s com­pletely use­less to any­one, and that’s approx­i­mately where they shipped it. (for reg­u­lar read­ers of this blog, you would prob­a­bly have read about this obses­sion of fea­tures many times before)

So Lt. Col. Dan Ward came up with FIST (Fast, Inex­pen­sive, Sim­ple and Tiny), which in his own words:

FIST stands for Fast, Inex­pen­sive, Sim­ple and Tiny. It’s a term I use to describe a par­tic­u­lar approach to acqui­si­tions and sys­tem devel­op­ment. As you might guess, it involves using a small team of tal­ented peo­ple, a tight bud­get, a short sched­ule and adher­ing to a par­tic­u­lar set of prin­ci­ples and practices…

in other words, small is beau­ti­ful, and it’s a theme that we have seen repeat­edly — be it microser­vices, or Amazon’s two-pizza teams, etc.

And as you impose con­straints on the teams — tight bud­get, short sched­ule — you encour­age cre­ativ­ity and inno­va­tion from the teams (some­thing that Kevlin Hen­ney also talked about at length dur­ing his Joy of Cod­ing clos­ing keynote).

How­ever, even with small teams, you still have this prob­lem that things need to evolve. For­tu­nately we have a solu­tion to that too, in what is known as the three party sys­tem where you have:

• pio­neers — who are good at explor­ing the unchar­tered world
• set­tlers — who are good at tak­ing half-baked ideas and make use­ful prod­ucts for others
• town plan­ners — who are good at tak­ing a prod­uct and indus­tri­al­is­ing it into com­mod­ity and utility

Once you have a map, you can also start to play games and antic­i­pate change. Or bet­ter yet, you can manip­u­late the map.

You can accel­er­ate the pace of evo­lu­tion by using open prac­tices — open source, open API, etc. Or you can slow the process down by using patents, or FUD.

The key thing is that, once you have a map, you can see where things are mov­ing and visu­ally rea­son about why you should attack one com­po­nent over another. And that’s how you can turn busi­ness into sit­u­a­tional aware­ness first, and actions after.

As things move from prod­uct to com­mod­ity, they enable a new gen­er­a­tion of ser­vices to spawn up (won­der), but they also cause death to orga­ni­za­tions stuck behind the iner­tia bar­rier (death).

This is a pat­tern that Simon calls War, Peace and Won­der, and is iden­ti­fi­able through weak sig­nal detec­tion and see roughly when these changes will likely happen.

Simon fin­ished this bril­liant ses­sion with three lessons:

1. if you’re a start up, have no fear for large cor­po­rates because they suck at sit­u­a­tional awareness;
2. the future is awe­some, and pio­neers have already moved into the space of open hard­ware and open biology;
3. open source itself is chang­ing, we have new peo­ple com­ing in as new settlers

I hope you enjoyed Simon’s talk, his blog has much more infor­ma­tion and goes into each of these top­ics in a greater deal of detail. If you fol­low him on Twit­ter (@swardley) he also post reg­u­lar tit­bits of wis­dom, which I have started to col­lect.

### James Pearce — How Face­book Open Sources at Scale

…We use in pro­duc­tion what we open source, and we open source only what we use in production…

- James Pearce

Nuff said

### Mar­tin Fowler — Mak­ing Archi­tec­ture Matter

I don’t like the term “soft­ware archi­tec­ture” as it sum­mons up these images of some senior per­son in an orga­ni­za­tion who’s set­ting rules and stan­dards on how soft­ware should be writ­ten but hav­ing actu­ally writ­ten any soft­ware for maybe 10 or 20 years. These archi­tects, Joel Spol­sky use the term “archi­tec­ture astro­nauts”, often cause a lot of prob­lems in soft­ware projects. So the whole term “archi­tect” and “archi­tec­ture” has a kinda nasty taste to it.

- Mar­tin Fowler

For me, the key points from this talk are:

• the notion that archi­tects shouldn’t code is wrong (or, don’t be an ivory tower architect!)
• archi­tec­ture is really the shared under­stand­ing of the system’s design amongst its expert developers
• archi­tec­ture dia­grams are just (often imper­fect) rep­re­sen­ta­tions of this shared understanding
• as soft­ware projects grow, what mat­ters the most is for you to ensure a good shared under­stand­ing between peo­ple lead­ing the project
• archi­tec­ture is also the deci­sions that you wish you could get right early
• your con­cern is there­fore the deci­sions that are hard to change, e.g. the pro­gram­ming language
• com­bin­ing the two def­i­n­i­tions above, and you can think of archi­tec­ture as the “impor­tant things that I need to always keep in my head whilst I’m work­ing on the system”
• when con­fronted with requests for more fea­tures over qual­ity, don’t make the moral argu­ment of craftsmanship
• when it comes to a bat­tle between crafts­man­ship and eco­nom­ics, eco­nom­ics always wins
• a com­mon fal­lacy is to think that soft­ware qual­ity is some­thing that can be traded off for cost (like you do with cars or cellphones)
• soft­ware has both exter­nal (vis­i­ble to users) as well as inter­nal (good mod­u­lar­ity, etc.) and archi­tec­ture is about inter­nal quality
• what mat­ters with inter­nal qual­ity is the long term picture
• well main­tained code base gives you a plat­form to build upon and can make future devel­op­ment eas­ier and faster
• poorly main­tained code base makes it harder and harder for you to make changes to
• this is why archi­tec­ture matters!

### Raffi Kriko­rian — Hack­ing Conway’s Law

Conway’s law has been a trendy topic at con­fer­ences this past 12 months, and every­one is basi­cally singing the same tune — apply Conway’s law in reverse and orga­nize your com­mu­ni­ca­tion struc­ture to fit the soft­ware you want to build.

## OSCON is com­ing to Europe!

At long last, we’ll see a ver­sion of OSCON in Europe this year, on 26th-28th Octo­ber in Ams­ter­dam. Some pretty cool tech com­pa­nies will be rep­re­sented there — GitHub, DataS­tax, Google, Thought­Works, Pay­Pal, Heroku and Spo­tify to name a few, and of course, our very own Gamesys

I will giv­ing a talk on the work I did with Neo4j a while back, which you can read all about in this post.

p.s. Rachel Reese (of Jet) is com­ing over from the US and talk­ing about build­ing reac­tive ser­vice with F#!