I'm a huge fan of the
NBA and sports in general and for years I've been fascinated with the way the
NBA structures their playoff bracket. They take the top
8 teams from each conference and seed them based on which teams have to most wins. There are
2 conferences in all so that makes
16 playoff teams each year. The top seed plays the worst team, the second seed plays the seventh team and so on and so forth. So I thought it'd be cool to actually code this setup in
F#.
I started with a method that knows how to read in each team from a text file.
// Learn more about F# at http://fsharp.net
open System
open System.IO
open System.Reflection
type Conference =
| Eastern
| Western
type Team = {
Name : string;
Wins : int;
Losses : int;
Conference : Conference
}
let filename = (Assembly.GetExecutingAssembly().Location |> Path.GetDirectoryName) + "\Teams.txt"
let totalgames = 82
let max = totalgames + 1
let r = new Random()
let conferencesize = 15
let playoffteamsperconference = 8
let half = playoffteamsperconference / 2
let getteams() =
seq {
let mapteam conference (l : string) =
let wins = r.Next(0, max)
{ Name = l.Trim(); Wins = wins; Losses = totalgames - wins; Conference = conference;}
let teams = filename |> File.ReadAllLines
// first 15 teams are the eastern conference
let eastern = teams
|> Seq.take conferencesize
|> Seq.map (mapteam Eastern)
yield! eastern
// last 15 are the western conference
let western = teams
|> Seq.skip conferencesize
|> Seq.take conferencesize
|> Seq.map (mapteam Western)
yield! western
}
The chunk of code within the seq{...} scope is known as a
computation expression. This particular type of
computation expression is called a
sequence expression. It's a
language integrated feature of
F# that allows you to use certain operators based on a set of methods you implement. In this case, the compiler will translate my call of
yield! to a method call that knows how to accept a
sequence and return it's values. Computations in F# are
monads; a fundamental feature of all functional languages. Believe it or not, the infamous
LINQ as you know it is
based on monads.
Amusingly enough, you've been using
monads in
.NET for quite a while even if you aren't a normal user of
LINQ. Ever used
Nullable<T>? It's a
maybe monad. Even the infamous
jQuery is a monad. It either has a value or it doesn't. In
F# we represent this type of
construct using the generic
option type.
Options are a
discriminated unions. They're represented by
Some 'T or
None; where
'T is a generic type argument.
An example is
let o = Some 5
let p = Some "string"
Now
o is an
int option and
p is a
string option.
This is cool because
we never have to worry about a value being null.
Null isn't even a
valid value in
F#, but it is however a valid
.NET value.
How do we find out if
o or
p has a value? We have to use
pattern matching.
let printifhasvalue optionvalue =
match optionvalue with
| Some v -> printfn "%A" v
| _ -> ()
You can think of
patterns as
switch statements. And that's exactly how the compiler translates them. When using
pattern matching, you have to handle all cases or the compiler will yell at you. In my case I only have to worry about
Some and
None. I accounted for
Some with the first check, and I used the
wildcard value, _, to handle all other cases. If there were a third option, we'd have a problem because there would be 2 more possibilities. The compiler knows that
None is the only other option so we're ok.
So when inter operating with other
.NET libraries we do have to account for it.
F# libraries
never return
null though. As for
discriminated unions, I'll talk more about those later. As a heads up, my
Conference type is one.
The
map function accepts a function that can take a value and transform it into another type of value. It's just like
Select in
LINQ. When I called
Seq.map (mapteam Western), I used a concept called
partial application.
The expression
(mapteam Western) isn't actually invoking the
mapteam function. It actually returns a function that accepts the remaining arguments for
mapteam. In our case it's the actual team. This is also known as
currying. If
mapteam took 3 arguments, I'd get a compile time error because I'd get a function back that accepts 2 arguments as opposed to 1. In that case I'd have to do
(mapteam Western arg2), to get a function that accepts only 1 argument. Pretty cool.
Most everything is a function in F#. Event the + and - operators. Don't believe me? You can use the operators as functions by wrapping them in
parenthesis like so:
(+). The output of that expression is a function that accepts
2 ints and returns another. Or
(int -> int -> int).
I also needed a datastructure to store each team and its properties. Specifically I used what's known as a
record in
F#. It's completely separate from a
class and the two are not synonymous.
There are
82 games in an
NBA season so I wanted to
randomly generate the record for each team. I generate a number between
0 and
82 inclusively for the
wins and subtract that from the remaining games in the season to compute the
losses. Pretty simple.
As far as which team each conference belongs to, I got the names of each team from the
NBA.com website and typed them in order into my
Teams.txt text file. I tried to keep things simple on that regard.
Teams.txt
Chicago
Miami
Boston
Orlando
Atlanta
New York
Philadelphia
Indiana
Milwaukee
Charlotte
Detroit
New Jersey
Washington
Toronto
Cleveland
San Antonio
L.A. Lakers
Dallas
Oklahoma City
Denver
Portland
New Orleans
Memphis
Houston
Phoenix
Utah
Golden State
L.A. Clippers
Sacramento
Minnesota
The cool thing about
F# is that it's
functional. That means we should implement
light weight composable functions. That's exactly the approach I've taken here. Each function builds atop the other. A simple
f(g(x)) relationship if you will.
And by the way, all values in
F# are
immutable by default. That means we can't
change the
state of something once we've created it. This greatly simplifies
multithreaded programming, because you don't have to worry about
multiple threads changing the
state of your data. You can rest assured that once you give a function a reference to a value, it'll be in that very state once the operation is completed.
F# isn't a purely functional language so we do have
mutable properties and values that we can pass around. Just not by default.
So now that we have a function that knows how to fetch each team and generate their record, we'll make something that can consume the output of that function and print each team.
let printteams (teams : seq<Team>) =
teams
|> List.ofSeq
|> printfn "%A"
The
printfn function is a cool utility because it knows how to print a
generic object. It can be a
sequence, a base type, etc. It's just like
printf in
C. You can pass a
format like
%s for
strings and
%d for
integers.
I used
List.ofSeq from the
List module to convert my
sequence to a
List. I did that because
sequences can be
infinite in
F# so the
printfn function wouldn't print out all the values. A
List on the other has is
finite. So
printfn will
iterate the entire
sequence and print out each element as opposed to the first few.
The type
seq<'a> in F# is equivalent to
IEnumerable<T> in
C#. It represents a possibly
infinite list of elements. I work solely with
sequences throughout my implementation. All instances of
Seq.x represent a set of functions known as the
Sequence Module in
F#. You can think of it as a
class with a bunch of
static methods. The funny looking |> syntax is just an
operator. It takes a
function and its argument and invokes that
function passing in the given
argument as a
value.
F(x) once again. I don't have to use this operator, the
forward pipe operator as it's known, but I really like it's logical syntax so I kind of abused it here. It's no different than piping output from one command to another when using bash on Linux or any other command shell. Piping input to grep is really nice by the way.
There is also a backward operator that knows how go go in the opposite direction. It accepts
x first then pushes it into
f. That one reads from right to left like
List.ofSeq <| x
In order to pull of the same syntax without the
pipe operator, I'd have to nest all of my return values. It'd look like
f(g(x)) or
printfn "%A" (List.ofSeq teams)
In this case,
g if my
List.ofSeq function which accepts the teams. The
teams are of course
x. The output of that function is then passed to
printfn. That makes
printfn g in this equation. It doesn't look so helpful in simple scenarios, but later on you'll witness me using the
pipe operator quite aggressively; and I think you'll start to appreciate the elegant syntax it allows you to exercise.
And since
F# is
functional,
functions are
first class citizens. They don't have to belong to any particular
object in general just like in
JavaScript. You can pass them as normal
values just like
ints,
GUIDS, and any other base types. That makes
F# a really powerful language.
You're probably wondering how I got away without specifying types. Don't you expect to see
int and
string? Well the
F# compiler implements what's known as t
ype inference. It's able to
infer types based on the way they're used. We rarely have to specify types in
F#, but I had to do it a few times with my implementaton using
type annotations. These appear in the
signature of my
method. Method signature syntax goes
functionname arg1[type] arg2[type] arg3[type]...argn[type]
F# interprets this as
(arg1 -> arg2 -> arg3 -> argn -> returntype)
The
last value is the
return type. Just like
Func<T> in
C#.
So anytime you see
(blah -> blah), that means a function. If you ever see this from intellisense when hovering over a method, you can believe that method accepts a function as an argument; so be prepared to pass one.
Arguments are
delimited by
spaces. The
type of the argument is
optional and is required based on whether the compiler can use its
type inference algorithm to
infer the type of the argument. We don't need
curly braces also, because
F# detects
scope based on
spaces.
Four spaces to be exact.
Now that I can get all the teams in the league, I need to group them by their conference. There are
2 conferences in the
NBA. The
eastern and
western conferences. You'd normally represent something like this an an
enum in
C#, but we have a more
functional construct known as
discriminated unions in
F#. My
discriminated union is called
Conference. You're probably starting to notice that the functions I'm using look a lot like
LINQ. That's because
LINQ's roots are tied deeply to functional programming.
let getteamsbyconference() =
getteams()
|> Seq.groupBy (fun t -> t.Conference)
I again made a function that knows how to print the teams out. Since I
grouped the conferences, they came back as a
pair or
tuple as we call it. So I have to drill down into the conference to get the teams. Then from their it's business as usual. I can simply reuse the initial function I created that knows how to print a
sequence of teams.
let printteamsbyconference (conferences : seq<(Conference * seq<Team>)>) =
conferences
|> Seq.iter (fun (_, teams) -> teams |> printteams)
You probably noticed the weird syntax I used in my function to iterate the conferences. It another form of
pattern matching. As I mentioned before, the _ represents the
wildcard character. That means I don't care about the result of the first value; which in this case is the conference. The syntax I used is a pattern for
tuples because its wrapped in
parenthesis and
delimited by a comma. That means I working with a
pair, but I could have easily been working with a
triple,
quadruple, and so on and so forth. I could have called my teams parameter whatever I like. The
name you give to your
parameters is
completely arbitrary.
I can get each conference and its respective teams now. It's time to make something that knows how to get the best
8 teams from each conference.
let getplayoffteams() =
getteamsbyconference()
|> Seq.map (fun (c, teams) -> (c, teams |>
Seq.sortBy (fun t -> t.Losses)
|> Seq.take playoffteamsperconference))
For each conference, I
sort the teams in the conference by the number of losses they have. Logically you'd think I've order by wins, but the
sortBy function orders in
ascending order. That means the teams with the least number of losses will be at the front of the pack. Logically the teams with the lest number of losses are the best right? That means they have the most number of wins. After sorting the teams, I take the
top 8 teams from each conference and return them as a tuple to pair them with their conference.
Anytime you see the
(fun x -> ...) syntax, that represents a
lambda.
Lambdas are pretty big in functional languages. It's with the
lambda symbol that we mathematically denote a function. That's some old school history related stuff and it's admittedly pretty boring. It is kind of nice to know though.
The last step is to order the teams and make the final bracket.
let printplayoffbracket() =
getplayoffteams()
|> Seq.iter (fun (c, teams) ->
Console.ForegroundColor <- ConsoleColor.Red
printfn "%A conference matchups\n" c
let topfour = teams |> Seq.take half
let bottomfour = teams |> Seq.skip half |> Seq.take half |> Seq.sortBy (fun t -> t.Wins)
Console.ForegroundColor <- ConsoleColor.Yellow
bottomfour
|> Seq.zip topfour
|> Seq.iter (fun (topseed, bottomseed) ->
printfn "%s (%d-%d) vs %s (%d-%d) \n" topseed.Name topseed.Wins topseed.Losses bottomseed.Name bottomseed.Wins bottomseed.Losses)
Console.ResetColor())
We consume the playoff teams and match the best teams against the worst teams. I used
closures in this case. I know the top for teams are at the front of the pack, so I simply took the first
4 teams out of the
8 available in each conference. After that, I took the last
4 teams and sorted them by the number of wins they had. Again, you'd logically then I'd sort them by the number of losses they had. But again I know the worse teams are the teams with the least number of wins. The
zip function knows how to
pair up each member of one
sequence with a
member of another
sequence. It will do this for each
pair it can find. If one
sequence is bigger than the other, it'll stop pairing elements from each
sequence once it's paired the number of elements equivalent to the smallest
sequence.
Now it's time to watch our little composable puppies in action
do getteams() |> printteams
do getteamsbyconference() |> printteamsbyconference
do getplayoffteams() |> printteamsbyconference
do printplayoffbracket()
We use the do keyword in
F# to execute imperative code. That's code that
doesn't return a value and just executes an action. It'll have the return type
unit, or
void in
C#. In
F# we always have to return a value. It'll either be an actual value like a
record or
tuple, or
unit.
Unit is denoted by
(). So to return
unit from a function you just write
let f() =
()
The function I definte above not only returns
unit, but accepts it as an argument. So event when you think you're calling a parameterless method in
F#, you're really not. And when you think you're not returning anything, you actually are.
And that's it. We started out by making a function that could read in each team and generate wins and losses for it. Then we
grouped each one of those teams into the right conference. Next we were able to take the top 8 teams from each conference, which were our playoff teams. And lastly, we pair up the best teams with the worse teams in each conference just as the
NBA does it.
If you want to try out my code, you can download
F# and fsharp.net. It's deployed as its own toolset, independent of
Visual Studio. I'd recommend
Visual Studio so you can have
intellisense though. If you want to get down and dirty, you use the
F# interactive command shell. It's an
interpretor so you're allowed to execute raw code without compiling it.
