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:

image

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.

image

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

image

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.

image

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

image

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:

image

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

image

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:

image

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

image

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

image

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.

image

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

exercises-prog-styles-cover

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

image

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.

 

image

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!

 

image

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.

 

image

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

image

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!

 

image

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.

 

image

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:

p2

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.

swardley_13

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.

swardley_14

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.

swardley_15

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.

swardley_16

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.

swardley_17

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?

swardley_18

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

swardley_20

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).swardley_21

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.

swardley_22

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#!

 

Links