Bayesian Football Picker: an implementation

Some time ago I wrote an article about applying Bayes to pick winners for the weekly football pool we had at our office. So, that pool went on for seventeen weeks, and I came out as one of the winners. Success!

So, how did that all work? 

I'll give you the business process of it and provide a high level overview of my Bayesian system. After that, I'll get down into the guts of the implementation.

I wrote this entire system in Haskell. It was something less than a day's effort.

Business Process/Big Picture

Each week, our boss, Dharni, provided the USA Today's predictions for the teams as a spreadsheet, which I saved in CSV format ('comma-separated values'). The weekly input spreadsheet (as CSV) looked like this:

,Wed Sep 5,

NYG GIANTS,3½ ,Dallas

,Sun Sep 9,

CHICAGO,10 ,Indianapolis

Philadelphia,7½ ,CLEVELAND

NYJ JETS,2½ ,Buffalo

NEW ORLEANS,7 ,Washington

New England,5 ,TENNESSEE

MINNESOTA,3½ ,Jacksonville

HOUSTON,11 ,Miami

DETROIT,6½ ,St. Louis Rams

Atlanta,2½ ,KANSAS CITY

GREEN BAY,5 ,San Francisco

Carolina,2½ ,TAMPA BAY

Seattle,2½ ,ARIZONA

DENVER,2½ ,Pittsburgh

,Mon Sep 10,,,,,,,

BALTIMORE,6 ,Cincinnati,TS,35-20,,,,

OAKLAND,2½ ,San Diego,,,,,,

where the number (e.g.: '2½') was the predicted point-spread, the team on the left was  the team predicted to win by the point-spread, and the capitalized team was the home team. The 'TS' indicator was if there were ties of people in the pool who guess the same number of picks correctly, then the TS was a tie-breaker: you had to guess the 'Total Score' for that game and the person who got the closest total score won the tie-breaker. I didn't worry my head over this particular aspect, so I just had my system predict the winner for that game and threw out a random total score.

I fed these data to my system which took each data point as a class-value for the Bayesian classifier, and my system spit out ('spit out' is a technical term, just like: 'run off') its own predictions which I turned right around back to Dharni: "I've highlighted the teams my system picked to win, Dharni."

The output result from the system was something like this:

Thursday,NYGGIANTS,Home,3.5,DALLAS,RIGHT

Saturday,CHICAGO,Home,10.5,INDIANAPOLIS,LEFT

Saturday,PHILADELPHIA,Away,7.5,CLEVELAND,LEFT

Saturday,NYJJETS,Home,2.5,BUFFALO,LEFT

Saturday,NEWORLEANS,Home,7.5,WASHINGTON,RIGHT

....

Just as before, right? Well, sort of. In this case my system output teams as (discriminated type) values, the spreads were floats, and the Home/Away indicator told me where the left team played. 'LEFT' or 'RIGHT' indicated which team the system predicted would win that game.

My coworkers were enchanted that I wrote myself a little football-picker. They'd exclaim in mock-dismay: "Something only geophf would come up with!"

Then my system won, and won, and won again. Not consistently, nor convincingly, but, to my satisfaction (that it even ever won at all): profitably. Pretty good. Pretty darn good enough!

Then, with what really happened that week (you know: that pesky ITRW result-set messing with my conceptual-frameworks!), I'd feed the results back into my system (the feedback look), training it with what were good and bad guesses on its part. Week after week my system accumulated the historical data and results into a data-set I named basis/training-set.csv. 

As the season progressed, my historical training data set grew, and I did, indeed, win pools more often later in the season rather than earlier. Which was nice: my predictive system was predicable.

The Guts/Little Picture

It's actually embarrassing how small my baby classifier is, and really, it'd be a lot smaller if Haskell natively read football spread predictions: it'd just be the Bayesian classifier.

But since Haskell doesn't natively read CSV files nor football spreads, I wrote those modules, too.

Here's the system.

The football picker is in the Football (parent) module and contains the module named Go:

> module Football.Go where

> import Football.Data.Week

> import Football.Analytics.Bayes

> import Football.Trainer

> go picks training = snarf training >>= \basis ->

>                     slurp picks >>= readWrite pick Thursday basis writeln

> choose picks = putStrLn "<table border='1'>" >>

>              slurp picks >>= readWrite justShow Thursday () writeRow >>

>              putStrLn "</table>"

> writeRow (match, _) = writeWeek HTML match >> putStrLn ""

What you do is load the Go module and say "go" to Haskell with the teams to be picked for this week with their data (the 'picks') and the training data set, both in CSV-format.

The system then 'snarfs' the training data, training the Bayesian classifier, yielding a training 'basis,' then 'slurps' in the teams for this week to give the picks.

As to the names of the functions: don't look at me. I don't know. The dude who wrote system had an oddball sense of humor.

And the 'choose' and 'writeRow' functions. Eh. I had made my system both CSV and HTML (output) friendly. I had this grandiose plan to have everything printed out all prettily in HTML and have an HTML input interface, setting this up as a web service with micro-transactions and everything so I could eventually sell the system off to Microsoft for 1.21 gigabucks, but in practice I just 'go'ed with the console-output results and highlighted the winning teams on the spreadsheet Dharni provided, and never really used the HTML functionality beyond some initial prototyping. Idle hands, lesson learned, simplicity, ... you know: all that.

So, the 'Go' module is just an entry-point to the 'readWrite' function which reads the input UTF-8 data, converts it to Haskell types and then writes the results out as CSV. Let's look at that function, then, and keep digging down until we're all dig-dugged out.

readWrite

The 'readWrite' function is in module Football.Trainer, its definition is as follows:

> readWrite _ _ _ _ [] = return ()

> readWrite fn day basis w (row:rows) = if   length (csv row) == 1

>                                       then readWrite fn (succ day) basis w rows 

>                                       else w (fn day row basis) >>

>                                            readWrite fn day basis w rows

... the whole if-clause is to handle whether this row is a football match row or a row declaring the day of the week.

If we query the type of readWrite from the Haskell system we get this 'interesting' type-value:

readWrite

  :: (Monad m, Enum a) =>

     (a -> String -> t -> t1)

     -> a

     -> t

     -> (t1 -> m a1)

     -> [String]

     -> m ()

which is my lovely way of making this generalized function that reads an enumerable type and puts it out to some monadic domain.

Bleh!

But, since I'm not working with HTML any more, readWrite is always called with the higher-order function arguments of

readWrite pick day basis writeln

where the functions pick and writeln are declared as:

> pick :: DayOfWeek -> String -> ([Match], [Match]) -> (Match, Call)

and

> writeln :: (Show t) => (Match, t) -> IO ()

> writeln (match, winner) = writeWeek CS match >> putStrLn (show winner)

which reduces readWrite, once the higher-order function arguments are applied, to a more compact type of:

> justDoIt :: DayOfWeek -> ([Match], [Match]) -> [String] -> IO ()

> justDoIt day basis rows = readWrite pick day basis writeln rows

which, of course, means we need to explain the function pick now, with its calls, but let's first clarify the types used, now that the function readWrite has been reduced to its used form.

Types

DayOfWeek is an example right out of the book for a disjoint type:

> data DayOfWeek = Thursday | Sunday | Monday

>      deriving (Show, Read, Eq, Ord, Enum)

(apparently there are only three days of the week ... in football, anyway, and that's all that matters, right?)

And the Match-type is the representation of a row of data (a football match):

> data Match = Match DayOfWeek Team Field Float Team deriving Show

Team is just simply the teams as disjoint enumerated values (e.g.: GREENBAY, STLOUISRAMS, etc.), The Field-type is Home or Away, and there you go!

There is a bit of a hex reading in the floating point value from, e.g.  '2½' and for that particular hack I created a separate type in a separate module:

> module Football.Data.Spread where

eh.

So, the spread is a number but represented in unicode ... do we wish to

capture the original datum as it was represented in the picks sheet for any

reason? Mucking with data always leads to sorrow, but ... well, this module

provides a Num interface to Spread, so you can swing either way with it.

> import Data.Char

> data Spread = Spread String

>      deriving Show

> toNum :: Spread -> Float

> toNum (Spread x) = toNum' x 0.0

> toNum' [] x = x

> toNum' (c:rest) x | c == ' ' = x

>                   | c > '9' = x + 0.5

>                   | otherwise = toNum' rest (10 * x

>                                              + fromIntegral (ord c - ord '0'))

> instance Read Spread where

>    readsPrec _ datum = [(Spread datum, "")]

> instance Eq Spread where

>    x == y = toNum x == toNum y

You'll note that the Spread-type isn't actually a Num instance, as the spread is a typed class value, I don't care, in my Bayesian system, whether the spread is lesser or greater; I just care if it's different from another spread.

Algorithm

Okay, back to the program!

So readWrite slurps in training data and the matches for this week and sends it to the 'pick' function which we've declared above, and we now define as:

> pick day row basis = let (match, _) = mkWeek day row

>                          winner = classify match basis

>                      in (match, winner)

The mkWeek function just slurps in the row as a string and converts it to a Match-type and with that reified typed value we ask the Bayesian system to classify this n-tuple as a Left or Right (predicted-to-)win.

So, let's look at the classify-function.

> classify :: Match -> ([Match], [Match]) -> Call

> classify query basis@(l, r) = let ll  = fromIntegral $ length l

>                             lr  = fromIntegral $ length r

>                             tot = ll + lr

>                         in  if (bayes query l + log (ll / tot)) >

>                                (bayes query r + log (lr / tot))

>                             then LEFT

>                             else RIGHT

The classify-function is your classic Bayes algorithm: classify the n-tuple as the type with the greatest probabilistic outcome. In our case we have two possible results, LEFT and RIGHT, so if the probablistic (logarithmic) sum for LEFT is greater, then it's LEFT, otherwise it's RIGHT.

Very 'Either'escque ... without the packaged data. So, actually, not very 'Either'escque at all but more 'Boolean'escque. Kinda. Sorta.

Our bayes-function is just summing the logarithms of the probabilities:

> bayes :: Match -> [Match] -> Float

> bayes (Match dow fav field spred dis) side = 

>       let pdow =   logp (\(Match d _ _ _ _) -> d == dow) side

>           pfav =   logp (\(Match _ f _ _ _) -> f == fav) side

>           pfield = logp (\(Match _ _ f _ _) -> f == field) side

>           psprd =  logp (\(Match _ _ _ s _) -> s == spred) side

>           pdis   = logp (\(Match _ _ _ _ d) -> d == dis) side

>       in sum [pdow, pfav, pfield, psprd, pdis]

We need a fix here for 0% match ... the log return -infinite, skewing the results, so let's just return 0 for 0, okay?[1]

> logp :: (Match -> Bool) -> [Match] -> Float

> logp fn matches = let num = fromIntegral (length $ filter fn matches)

>                       dem = fromIntegral (length matches)

>                   in  if (num == 0.0 || dem == 0.0)

>                       then 0.0

>                       else log (num / dem) 

That's basically everything, just some window-dressing functions of reading in the training set, which requires us to read in CSV files, so I present these functions here for completeness.

To read a CSV file, we simply rewrite the words-function from the Prelude to allow separators other than spaces:

> module CSV where

> import Char

-- I modified Prelude.words to accept a set of alternative delimiters to space

> wordsBy :: String -> String -> [String]

> wordsBy delims line

>        = let isDelim = flip elem delims

>          in  case dropWhile isDelim line of

>                           "" -> []

>                           s' -> w : wordsBy delims s''

>                                 where (w, s'') =

>                                        break isDelim s'

> csv = wordsBy ","

The CSV module is useful not only here for picking football teams, but also for anywhere you need to parse in CSV data as linearized Haskell-types.

and then readResults (the results of the training data, that is) is as follows:

> readResults :: ([Match], [Match]) -> [String] -> ([Match], [Match])

> readResults map [] = map

> readResults map (row:rows) = let [dow, fav, field, spred, dis, call] = csv row

>                                  day = read dow

>                                  match = Match day (read fav) (read field)

>                                                (read spred) (read dis)

>                                  winner = read call

>                                  res = Result match winner

>                              in  readResults (addmap winner map match) rows

where addmap is the obvious add-to-left-or-right-branch-of-the-training-data-function:

> addmap :: Call -> ([a], [a]) -> a -> ([a], [a])

> addmap LEFT (l, r) m = (m:l, r)

> addmap RIGHT (l, r) m = (l, m:r)

The 'a'-type here is invariably a Match-(Row)-type that I use as my training-set basis, but the addmap-function works with any set of paired-lists.

The readResults-function is used by the snarf-function:

> snarf :: FilePath -> IO ([Match], [Match])

> snarf file = readFile file >>=

>              return . lines >>=

>              return . readResults ([], [])

So that just leaves the slurp-function for reading in this week's matches:

> slurp :: FilePath -> IO [String]

> slurp file = readFile file >>= return . tail . lines

(we skip, or 'tail', by the first line, because that's the day of the first football games, which we invariably call Thursday)

Conclusion, or: please send your 1.21 gigabuck checks to geophf

And there you have it, folks: a little Bayesian system that picks (we hope) winning football teams from a set of accumulating historical data. The 'we hope'-caveat is the usual standard disclaimer when using Bayesian systems: as one of my colleagues pointed out, using such a system for classification is like driving your car with the only guidance being the view in the rear-mirror, but, for me, such guidance paid off. I walked away from this experience building yet another (naïve) Bayesian classifier, and my little pet project helped me walk away from this pool with a few dollars more than I invested into it. Yay!

('Yay!' is a technical term, c.f. Despicable Me 2)

-----

Endnotes:

[1] There was a comment on my original blog entry about normalizing the absent probability instead of what I do here, which is to zero it out. My system worked okay without linearization, so it would be an area of further research to see how the results are improved from linearization.

'Arrow' is spelt 'fizz-buzz'

A little literate Haskell program:

> module Fizzbuzz where

So, fizz-buzz through a functional lens

> import Control.Arrow

Our predicate is for some number, x, we print 'fizz' if it's modulo 3,
or we print 'buzz' if it's modulo 5. N.b.: these predicates are not
exclusive.

So our fizz-buzz predicate follows ('pred'icate 'f'izz-'b'uzz)

> predfb :: String -> Int -> Int -> Either String Int
> predfb str modulo x | x `mod` modulo == 0 = Left str
>                     | otherwise = Right x

so:

> fizz = predfb "fizz" 3
> buzz = predfb "buzz" 5

... that's really all there is so we just split the input number
into the two predicates and then remerge the results following
this rule:

Left str1 (+) Left str2 = str1 ++ str2
Left str (+) _ = str
_ (+) Left str = str
Right x (+) _ = show x

which transliterates quite nicely (it's nice programming requirement specification as implementation-code when your programming language is declarative)

> fbprinter :: (Either String Int, Either String Int) -> String
> fbprinter (Left x, Left y) = x ++ y
> fbprinter (Left x, _) = x
> fbprinter (_, Left y) = y
> fbprinter (Right num, _) = show num

Now the fizz-buzz game: count from 1 to 100 replacing '3's with fizz and '5's
with 'buzz' ... off you go:

> fizzbuzz = [1..100] >>= return . (fizz &&& buzz >>> fbprinter)

There it is. fizzbuzz in, lessee, 8 lines of implementation code. Any questions?

Nope? Q.E.D.

Afterthought:

Well, there is one improvement. If we look at the Either type as a cartesian
product type (which it is), then the print rule looks rather redundant to the
monoidal append operation, for, after all

m0 (+) (anything) = (anything) (order of arguments superfluous); and,
m+ (+) m+ = defined by the semigroupoid-implementation

so, the monoidal addition of lists is

[] (+) lst = lst; and,  (... even if lst == [])
lst1 (+) lst2 = lst1 ++ lst2

Can't we just convert our Either String Int type to be a monoid and have
the special base case of 'show num' for the (Right num (+) Right num) case?

Hm. Yes. I leave this now as an exercise for the reader...

... which is another way of saying that I see a simple solution of

mzero == Right num

and

mplus == Left str

in my head, but how to implement that in Haskell is currently puzzling me.

Intrepid readers, show me the light!

... at any rate, 'running' fizzbuzz gets you all fizzy-buzzy and you can feel good that you've used a little predicate logic, functional programming, programming with arrows, no less, and you didn't have any redundant boolean logic that you see in other implementation for fizz-buzz: Either took care guarding our conditioned results.

Sweet!

p.s. The payoff! The payoff! How could I forget the payoff for those of you who don't have Haskell running natively on your 'iron'?

(Now, why you don't have haskell running on your platform, I don't want to even think about. Not having haskell on hand to feed yourself your functional-programming (daily/hourly/secondly) fix? geophf shudders)

*Fizzbuzz> :l Fizzbuzz.lhs 

[1 of 1] Compiling Fizzbuzz         ( Fizzbuzz.lhs, interpreted )

Ok, modules loaded: Fizzbuzz.

*Fizzbuzz> fizzbuzz 

["1","2","fizz","4","buzz","fizz","7","8","fizz","buzz","11","fizz","13","14","fizzbuzz","16","17","fizz","19","buzz","fizz","22","23","fizz","buzz","26","fizz","28","29","fizzbuzz","31","32","fizz","34","buzz","fizz","37","38","fizz","buzz","41","fizz","43","44","fizzbuzz","46","47","fizz","49","buzz","fizz","52","53","fizz","buzz","56","fizz","58","59","fizzbuzz","61","62","fizz","64","buzz","fizz","67","68","fizz","buzz","71","fizz","73","74","fizzbuzz","76","77","fizz","79","buzz","fizz","82","83","fizz","buzz","86","fizz","88","89","fizzbuzz","91","92","fizz","94","buzz","fizz","97","98","fizz","buzz"]

There ya go!

(this program contains its own solution ... meta-quine, anyone?)

Quotes-map-reduce-close-quotes

"So, geophf," I was asked during a recent interview for a software quality-assurance tester job, "have you heard of the product map-reduce?"

"Well," sez I, "no, but I'm familiar with the concept from functional programming."

That was a good enough answer for me.

The test manager had heard of functional programming and (from me) category theory. I was talking with Ph.D.s who were test managers.

A refreshing conversation, actually.

"Yes," he said, "but what is all this stuff good for?"

I gave him a "you've got to be kidding me" look.

What is category theory good for? Coming on the heels of have I heard of map-reduce?

Like where did the concept of map-reduce come from?

So, here's what it's good for.

The Joke

An infinite number of mathematicians walk into a bar. The first math dude sez, "Bartender, I'll have half-a-beer." The next one sez, "I'll have half what he's having." Then next: "I'll have half of hers." And the next one goes to speak.

And they want to get in this specification, because that's how mathematicians roll, but the bartender holds up his hands.

"Ladies and gentlemen," he says, "know your limits, please!"

And pours out one beer which the infinite number of mathematicians enjoy.

The proof in the pudding

let nat = [1..]
let halflings = map (\x → 1 / 2 ** x) nat
let onebeer = sum halflings

onebeer

Now, that may take some time to return (geophf cackles evilly at his phrasing of 'some time'), but we've just used map-reduce. How? map we used directly above in halflings, as you see, and reduce (a.k.a. the fold function) is embedded in the definition of sum:

let sum :: Num a ↠ [a] → a = foldl (+) 0

So, if we look at the the above we just used map-reduce to solve the beering-mathematicians problem (as opposed to solving the dining philosophers problem, because, anyway, those philosophers really should go on a diet. Just sayin').

Piece of cake, right?

Well, not really. Our solution, to use a technical term, sucks.

Let's look at it. What does our set of equations reduce to? The reduce to this one formula:

let onebeer = sum (map (\x → 1 / 2 ** x) [1..])

What's wrong with this?

Well, for any n, where n is the length of the set of natural numbers, we have a least a double-linear complexity to solve this problem.

But let's look at the sequence we create by unwinding the problem.

First we have [1,2,3,4, ...]
Then we have [1/2, 1/4, 1/8, 1/16, ...]
Then we have [1/2 (+ 0), 1/4 + 1/2, 1/8 + 3/4, 1/16 + 7/8, ...]

Huh. What's interesting about this pattern?

Story time

Once upon a time, there was a bad little boy in maths class, named Gauss, and he was held after school. The teacher told him he could go home after he summed the first 100 'numbers' (positive integers, I believe the teacher meant).

Gauss left for home after writing the solution down in less than one second.

The teacher was furious, believing that Gauss had cheated.

He didn't. He just noticed a pattern.

1 = 1
1 + 2 = 3
1 + 2 + 3 = 6
1 + 2 + 3 + 4 = 10
sum [1..n] = ... what?

Well, what does it equal?

When n = 1, sum [1..1] = n
when n = 2, sum [1..2] = n + 1
when n = 3, sum [1..3] = n * 2
when n = 4, sum [1..4] = ... hm, well, it equals ... what?

It equals n (n + 1) / 2, doesn't it.

n = 100, sum [1..100] = 100 * 101 / 2 = 5,050

... and Gauss was done. He went home, serving the shortest detention ever, and put egg on his prof's face, too.

Good times. Good times.

Well, what about this problem?

We can map and sum all we want, but can't we do what Gauss did and reduce the double-linear (at least) problem complexity down to some constant on the number n?

Yes, we can.

The pattern is this, after we've done our reduction to the simplest forms:

[1/2, 3/4, 7/8, 15/16, ... blah-blah-blah, boring-boring-boring]

Who needs map-reduce when we just simply return

lim_n (1 - 1 / 2ⁿ) 

for any n even as n approaches infinity?

Who, indeed.

The take-away? Yes, I could have used map and reduce and exponentiation and all that to get to the answer, but sometimes we just have to take a step back from trying to solve a problem and just observe what we're solving.

"Hey," algorist exclaims, "I'm just solving to get this simple fraction! I don't have to map-sum anything!"

It's amazing what meta-problem-solving saves us as we go about solving problems, isn't it?

Epilogue

Oh, map is reduce, did you know that?

Specifically, for every function f, there is a reduce function that is isomorphic to map f.

What is it?

A little κ-calculus conversation

So, "wan plas wan is doo" in the κ-calculus. Because why? Because if you can prove addition in some calculus, you can prove anything.

Well, prove any primitively-recursive thing in that calculus, and that's good enough for most anything (except Ackermann and some others), which is close enough to a latte at Caribou café for me.

SO! without further ado: 1 + 1 = 2, κ-style.

First of all, some basics. What is the κ-calculus?

κ-calc: application is composition: 

f: A → B is κ x . f : (C x A) → B

and the lifting ('identity') function

C : 1 → C is lift : A → (C x A)

Then, for addition we need the category Nat and the following arrows:

0 : 1 → Nat; and,       (so, 0 ~> 0)

succ : Nat → Nat         (so, succ o succ o 0 ~> "2")

but we also need the iterator function for natural numbers:

(a) it(a, f) o 0 ~> a; and

(b) it(a, f) o succ o n ~> f o it(a, f) o n

from this we can declare the function add in the κ-calculus:

add : Nat x Nat → Nat ≡ (κ x . it(x, succ))

Note how we don't care what the second (snd) argument of the tuple is, we just iterate succ over it, so with add defined above we can now prove 1 + 1 = 2

add o (succ o 0, succ o 0) = (κ x . it(x, succ)) o lift (succ o 0) o succ o 0 (lift distribution)

= it(x, succ)[succ o 0] o succ o 0 (composition)

= it(x [succ o 0/x], succ [succ o 0/x]) o succ o 0 (substitution)

= it(succ o 0, succ) o succ o 0 (substitution)

= succ o (it(succ o 0, succ) o 0) (iteration (b))

= succ o (succ o 0) = 2 (iteration (a))

Q.E.D.

Piece of cake, right? Using categories (for types), we reduce 200 pages of the Principia Mathematica down to a couple of axioms, a couple of types and one function (it), then a few lines of proof and we're done.

Awesomesauce!

But then, my daughters became curious about what the Papa was doing, so this conversation ensued with my 10-year-old.

"But, Papa," Li'l Iz asked with big-big eyes, "what does snd have to do with 2?"

So, I explained.

A tuple is of the form: (a, b)

So for example we have: (3, 4)

So the tupling functions are:

fst (3, 4) ~> 3

snd (3, 4) ~> 4

And therefore for the tuple (1,1)

fst (1, 1) ~> 1

snd (1, 1) ~> 1

So, to prove 1 + 1 = 2 we thence have:

add o (1, 1)

Therefore:

fst (1, 1) o add o snd (1, 1) = 2 

and that's why snd (1, 1) has everything to do with 2. :p

wa, wa, waaaaaaaa (this my daughter wrote)

Abstract Nonsense, chapter 3: the Tuple

We consider the tuple.

Really, after Unit and Id, the tuple is one of the simplest data structures around. In its base for the tuple is of type

data Tuple a b = (a, b)

Tuple has two fundamental functions:

fst :: (a, b) -> a

snd :: (a, b) -> b

and that's all there is to it, and that's all there is to the tuple.

(really, the above declaration should be:

data (a, b) = (a, b)

but the typeful LHS ('left hand side') declaration being the same syntax (and I say 'the same syntax,' not 'the same semantics') as the instance definition on the RHS ('right hand side') may make some people's head hurt. That's also why I gave the list declaration as:

data list a = nil | (a, list a)

and not the standard syntax of:

data [a] = [] | (a:[a])

There is the question of programs are written to be read as well as to be executed by a machine).

So: simple.

Or.

Is.

It?

(I believe this has become my trademark.)

Of course if you have the Cartesian cross-product of two typed values, then why not three? why not one? why not ... 'n'?

So, of course, the tuple is any number of typed values associated through their cross products, but I like to keep things simple here (and in my code), so I'll just be working with the above given definition of tuple and where I need a 'triple' (heh: 'triple') ('triple' was the term used for monads up until recently) I'll define one, or I'll simply compose tuples, for, after all, any n-relation can be reduced to a set of 2-relations, e.g.:

data Triple a b c = (a, (b, c))

data Quad a b c d = (a, (b, (c, d)))

data Quinz a b c d e = ... etc

So from tuple you have triple, or quad, or quinz, or whatever.

So: tuple.

What can we do with it?

Well, everything, actually. You see most programming languages take the tuple for granted, and call it the parameter-set of functions. Haskell does not do this. Haskell be smart. Haskell be curry(ing) the arguments to functions.

Haskell B. Curry. Geddit? No? Look it up.

So, in programming language X, where X is most likely the language of your choice you invoke a function in the 'standard' way:

foo(bar, baz, ...)

Not so with Haskell ... I mean, not necessarily so (and not even ordinarily so).

Nor even with other Lisp-like languages. When everything's a list, you get a tremendous amount of conceptual freedom and from that freedom comes power.

But ... power? Later.

So, with Haskell, you can force the tupling of arguments to a function:

foo :: (bar, baz) -> quux

But why would you want to do that, requiring all the arguments to a function to be present when you can curry them:

foo :: bar -> baz -> quux

And then apply the arguments individually as needed, building a partial function (the partial function itself being a (functional) value) until you finally apply to get the solution (in this example, the quux-typed value).

So, currying: the 'anti-tuple.'

So we showed a simple, elegant use contra the tuple, but what are the uses of the tuple.

Well, like I said: plentiful, many-ful, many-fold. Manifold.

(I love writing words.) (Bear with me.)

(which means something totally different than 'bare with me.')

One of the primary uses that come to mind for the tuple, besides freely-relating two disconnected values (which, in and of itself is a big, huge win ... ever see a list of parameters to a function where there are obviously-paired values, except they aren't paired, so the code gets all mucked up treating something that isn't as if it were because it should be?), is to 'pretend' that two values are one and then to fool everybody else with this conceit.

Where does this work?

Have you ever needed to return two values from a function?

But of course you can't because a function returns 'a,' 'one,' 'single' value. A function doesn't return two values, and you don't want to have to write a class to package those values together (because why? That's something you may have to look into yourself to answer: if two values are related, why aren't you making that relation explicit in the type system? Types makes things easier, but only when you use them), so what do you do?

Return the tupled pair.

You now have functions that return two values, well-typed, at that, and if they can return two, then can return three, or four, or ... 'n.'

That's one place where tuples shine: 'Oh, I need the value from the list, but I also need the list-index where that value was.' You tuple the index with the value, and your function now returns the data you need to proceed with your work.

But then, once you start using tuples one place, you find yourself starting to see uses for tuples in many other places you never considered before, because you just coded around two disparate values.

'Coding around' things is the algorithmic approach, tuple provides a data-centric solution. You ever notice how greatly algorithm simplifies when the right data types are used?

Tuple.

Examples

Arrows

Of course, the fundamental data type of category theory, the map can be viewed as a list (which is a linked set of tuples (or 'pairs')) of tuples, where each tuple is composed of the key for the first value and the value for the second.

So that gives us another example: one is 'Map.Entry<K, V>' so obviously 'Tuple' I'm wondering why the Java folks just didn't name it 'Duck' since it was quacking like one.

But then ... Arrow.

Arrow captures the entirety of the function f :: a -> b, so if you look at it slightly differently, an arrow, or morphism, or function, is the mapping of all values applicable to the function f from Category A to Category B.

So, one way to look at an arrow f is simple the set of all tuples (a, b) where the 'a's are all possible inputs to f with the 'b's being the corresponding outcomes.

But there are more to arrows than that (and, fear not, this article will not be side-track to an arrow-exclusive): the primary arrow operation is 'first' (arrows are fundamentally, or minimally, defined on 'arr' (which is the 'arrow-maker' function) and 'first').

What does first do?

First supposes that the input has been split from some value a into two (tupled) values (a, a). And first takes an unit function and applies it to the the tuple's first value, leaving the second value unchanged.

So, if you have some value a, and a function f :: a -> b then

first f

does the following

first f (a, a) -> (b, a)

Or, actually, and more generally, this works for any tupled input value so:

first f (a, d) -> (b, d)

works as well.

Exercise: Given than f :: a -> b and first f :: (a, d) -> (b, d), write an implementation of first.

Ordering

We mentioned before that Map.Entry<K, V> is just another name for 'Tuple<K, V>', so then, looking at it this way, either List<Tuple<K, V>> or Set<Tuple<K, V>> is another name for Map<K, V> depending on which search strategy we wish to use.

... with a significant difference: as both the K and V in the tuple are used to compute the tupled instance's identity, then both those data structures permit 'duplicate' entries: a key may be associated with zero, one or more values.

And, here is where the search strategy becomes significant: List has an explicit positional ordering: first comes the first value, next come the second value, etc. This positioning may be exploited for the inherent positional index to a tuple ... or I exploited this inherent indexing, at any rate.

Problem statement: so, have a list of values, rows from a data table that we wish to display in order.

Simple enough: we make the data table entity a comparable type, sort the section, and we're done.

Or.

Are.

We?

The problem here is that ...

Well, there's always a 'the problem here is' when a model encounters the real world and when developed code hits production data.

This particular problem is that there are scenarios where an entity is represented by compound data, and so you need two rows to indicate one entity.  In these cases, you have the same entity id, so what do we do? We can complicate the sort-criterium for the comparison for the entire entity because of this special case, or we can sort simply and handle sorting these two-row entities on a case-by-case basis.

But then we sort the list twice. Once naturally and automatically, and we don't need to think about that sort.

But how do we juxtapose two rows with the same entity id in a list? We can't change the indices on a list pel-mel, can we?

Or.

Can.

We?

Using tuples, we can indeed do just that. If we have the mostly-well-sorted list

[Ent {13, ... Nov 20, asdf},

 Ent {27, ... Aug 3, aega},

 Ent {27, ... null, hjg},

 Ent {34, ... null, asjkl},

 Ent {34, ... Apr 26, aehe},

...]

And we wish to have the 'null' date higher up on the list, as per customer requirements. One way to do that is to add this to the search criteria. But what if the search criteria is already based off of three values of the primary key (and this date is not part of the primary key, because it is nullable)? Do we wish to add this new criterium for these specialized cases?

Yes, we can do that.

Or, as we did in the project, we did another sort, manually. You see, the question comes up, how do we recognized that two rows represent one value, and, when recognized, how do we swap the row order for that one case where we wish to?

You can't say, 'oh, this list index is now less one and the other list is now index plus one'

Not with a straight-up list, anyway, you can't¹ change the indices there. But if we make the indices explicit by tupling them with their listed data:

int index = 0;

for(Ent entity : entities) {

    newList.add(OrderedTuple.pair(index++, entity);

}

And then, when we encounter our special case, we verify the order or correct it:

OrderedTuple<Integer, Ent> oldPair =

    OrderedTuple.pair(-1, Ent.prototype());

for(OrderedTuple<Integer, Ent> pair: newList) {

    Ent newEnt = pair.snd();

    Ent oldEnt = oldPair.snd();

    if(newEnt.id == oldEnt.id) {

        if(newEnt.date == null) {

            int pairKey = pair.fst();

            pair.changeKey(pairKey - 1);

            oldPair.changeKey(pairKey);

         }

     }

     oldPair = pair;

}

// now we sort on the revised indices:

Collections.sort(newList);

// and return that sorted entity list (sans the explicit indicies):

List<Ent> revisedList = new ArrayList<Ent>();

for(OrderedTuple<Integer, Ent> pair : newList) {

  revisedList.add(pair.snd());

}

return revisedList;

And that's one way to skin that cat.

So, what's OrderedTuple? It's simply a mutable tuple with an ordering imposed on the keyed value:

@Effectual 

public class OrderedTuple<K extends Comparable<K>, V> 

    extends MutableTuple<K, V>

    implements Comparable<OrderedTuple<K, V>> {

  protected OrderedTuple(K key, V val) { super(key, val); }

  public static <KEY extends Comparable<KEY> VALUE>

    OrderedTuple<KEY, VALUE> pair(KEY k, VALUE v) {

return new OrderedTuple<KEY, VALUE>(k, v);

  }

  // Comparable implementation --------------

  @Override public int compareTo(OrderedTuple<K, V> tup) {

    return fst().compareTo(tup.fst());

  }

}

Where mutable tuple simply decorates the tuple protocol with setters:

@Effectual public class MutableTuple<K, V> extends Tuple<K, V> {

  protected MutableTuple(K k, V v) {

    super(k, v);

    key = new State<K>(k);

    value = new State<V>(v);

  }

  @Override public K fst() { return key.arg(); }

  @Override public V snd() { return value.arg(); }

  @Effectual public void changeKey(k newKey) { key.put(newKey); }

  @Effectual public void changeValue(v newValue) { value.put(newValue); }

  private final State<K> key;

  private final State<V> value;

}

Entanglement

Tuples are a way of pairing or associating things that are not explicitly already paired. As we saw above, normally the indices of a list are implied, but they are there and are associated with the elements of the list. A tuple makes that implied associate explicit. Once something is explicated then it can also be exploited in ways unimagined heretofore.

Another, novel, way I've used tupling is entanglement. Something over here, an event or an object, changes, and that change is supposed to reflect throughout the system. How do we do that?

One way is to hardcode it:

if(x changed) then change y

But this is at the algorithmic level, and things happening procedurally are notoriously hard to track.

We could, instead, make this a structure and realize entanglement as a data type.

This is what I do. I associate an observed object with an action, and that action is to change a value entangled (implicitly) with the observed object.

@Effectual public class Entanglement<T> extends Tuple<T, Effect<T>> {

  private Entanglement(T source, Effect<T> setterF) {

    super(source, setterF);

  }

  // the point of it all: we entangle two objects

  public static <T1> Entanglement<T1> entangle(T1 src, Effect<T1> destF) {

    return new Entanglement<T1>(src, destF);

  }

  // when we observe an object, that act of observation, itself, 

  // changes the destination object via entanglement:

  public Maybe<T> observe() throws Failure {

    return (Maybe<T>) Maybe.nullOr(fst()).liftThenBind(snd());

  }

}

A very, very simple class for a very simple concept.

Where is such a concept used?

Well, as in the above scenario with Ent types, I was collecting a set of three of the most current dates from Ent rows where 'most current' is defined as the the last update date auditing column is greatest on a particular set of entity types.

The thing is that any of these three dates could be null, so if I wholesale replaced dates with the most recent Ent row, then I found I would be nulling out already established dates.

I had to update dates on the most recent non-null dates, and this occurred on a case-by-case basis.

A further complication: one of the dates has an associated duration type-code, so every time I replaced that date, I had to update the duration code, too.

Algorithmically this turned into a nightmarish mess. Three development teams were called in to code the solution, and three teams each, eventually, threw up their hands, declaring this to be an intractable problem.

I used entanglement to solve this problem.

For the associated date-duration-code, I had one entanglement:

Entanglement.entangle(incomingRow.getDateA(), new Effect<Date>() {

  @Override protected void execute(Date newA) throws Failure {

    stored.setDateA(newA);

    int dur = incomingRow.getDurCd();

    if(dur > 0) {

      stored.setDurCd(dur);

    }

  }

}).observe();

For the stand-alone date, I used a simple entanglement:

Entanglement.entangle(incomingRow.getDateB(), new Effect<Date>() {

  @Override protected void execute(Date newDateB) throws Failure {

    stored.setDateB(newDateB);

  }

}).observe();

Then I simply iterated up the result set of the set of entities of concern and I was able to get the correct dates for each entity row that were required.

Easy, peasy!

Using the entanglement type (which, itself, is simply a tuple of observed value and an effect) I overhauled a patchwork system, that actually wasn't working at all, of over one-thousand lines of code with a fifty line replacement that satisfied customer requirements.

My take-away here is that solving problems algorithmically leads to code bloat and complication, but when the problem is reconceptualized into data structures, the problem is simplified and modularized.

Tuple is a data type that does just that: often, in code, two values are implied to be associated, but there is no direct correlation. A tuple makes that association explicit.

κCalc: the Kappa calculus

One more point to cover on tuples.

The λ calculus can be considered to be the marriage of two dual calculi: the κ calculus, which is the calculus of composition,² and allows functors of the first order only, and the ζ calculus, which is the calculus of application. So, in the κ calculus, values are lifted into tupled types, or dropped to the unit type. An entire calculus exists around the manipulation of tuples, and it has its own arithmetic and everything.

You can do anything with tuples! Tuples are like Tiger Balm that way.

-----

(1) Ever hear a British-English person say the word 'can't' ...? It is to die for! But I digress, and also, in digression, have embarrassed Mr. Sh, my boss.

(2) When I read this paper on the κ calculus, I was so pleased! I had defined my morphism type to be a type that contained only the identity and the composition functions, but not application! And I had wondered if I were doing the right thing. Isn't the whole point of it all to apply a function? Isn't that what a morphism ... 'is'? And, actually, no, that's not the case at all. There do exist morphisms free of the concept of function application, and the κ calculus has arrows where elimination occurs from (de)composition, not from function application.

There exist a whole class of arrows that do no application at all. And I got that correct!

But this topic can be discussed in the article where we consider the morphism.

I suppose I'll start that article with the words: "We consider the morphism."

Hm, I wonder if the map article and the morphism article are one and the same?