For example, a linked list in Haskell has this definition, it's either empty or a node containing a single element and another listpic.twitter.com/BLveY6sGad
Show this thread
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.
-
-
-
Interpreting sum types as addition and product types as multiplication (that's why they have those names duh) you can write L(x) = 1 + xL(x) which you can solve to give the function L(x) = 1/(1-x)
Show this thread -
This has the series expansion L(x) = 1 + x + x^2 + x^3 + ... which tells you that a list is either empty (1) or has one element (x) or two elements (x^3) etc etcpic.twitter.com/YG70F7OfL7
Show this thread -
Binary trees are more fun. A binary tree is either empty, or a branch consisting of an element and a pair of binary treespic.twitter.com/AoBNXSOgWN
Show this thread -
Converting it to math gives T(x) = 1 + xT(x)^2 which you can solve with the quadratic formula (what) to give T(x) = (1 - sqrt(1 - 4x))/(2x)
Show this thread -
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.