One of my favorite math/programming mashups is that you can take an algebraic data type (like in OCaml, Haskell, F# etc) and convert it into a function, and the series expansion of the function counts the number of instantiations of the data type.
-
-
The coefficients in the series expansion are telling you that there is one empty binary tree, one binary tree with one element, two binary trees with two elements (the second element could either be on the left or the right branch)pic.twitter.com/dYJaI8Y2Ye
Show this thread -
It's not immediately obvious that there are five binary trees with three elements, or fourteen binary trees with four elements, but there arepic.twitter.com/y3ksysrXxo
Show this thread -
The functions you derive from the algebraic data type are called "generating functions" and they are useful for all kinds of counting problems with unlabeled data (ordinary gf) or labeled data (exponential gf) or probability problems (probability generating function)
Show this thread -
The mind-blowingly cool thing is that you can differentiate the generating function to get a new function, and if you turn that back into an ADT, it is the zipper type associated with the original ADT (that is, the full data structure plus a 'focus' that you can move around)
Show this thread -
I first saw this in a Conor McBride paper from about 2000 but I'm not sure if that's the first time it was noticed, as once you have the ADT <--> generating function correspondence, differentiating it seems like quite a natural thing to do
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.176.2720&rep=rep1&type=pdf …Show this thread -
Anyway I will probably go back to regularly scheduled finance content after this, feel free to ignore and pretend nothing weird has happened if you like.
Show this thread
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.