macrocephalopod on Twitter: "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."

Country	Code	For customers of
United States	40404	(any)
Canada	21212	(any)
United Kingdom	86444	Vodafone, Orange, 3, O2
Brazil	40404	Nextel, TIM
Haiti	40404	Digicel, Voila
Ireland	51210	Vodafone, O2
India	53000	Bharti Airtel, Videocon, Reliance
Indonesia	89887	AXIS, 3, Telkomsel, Indosat, XL Axiata
Italy	4880804	Wind
3424486444	Vodafone
» See SMS short codes for other countries

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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

1 reply 0 retweets 11 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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)

1 reply 0 retweets 13 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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

1 reply 0 retweets 12 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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

1 reply 0 retweets 11 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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)

1 reply 0 retweets 11 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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

1 reply 0 retweets 12 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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

1 reply 0 retweets 15 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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)

1 reply 1 retweet 19 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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)

1 reply 1 retweet 22 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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 …

1 reply 1 retweet 21 likes

Show this thread

macrocephalopod‏ @macrocephalopod 2 Mar 2021

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.

3:42 AM - 2 Mar 2021

20 Likes

5 replies 0 retweets 20 likes

1. Show replies
1. SemiCynic ( , )‏ @SemiCynic 2 Mar 2021
  Replying to @macrocephalopod
  
  Very fun! Recursion has always had a special place in my heart. The “one hole” concept is a great tool for the problem solving generalist. Series approximations were also my favorite, as I was never strong with pure calculus but could usually get close with a bootleg Euler method
  
  1 like
  Thanks. Twitter will use this to make your timeline better. Undo
  
  Undo
1. AlexVlasev‏ @AlexVlasev 2 Mar 2021
  Replying to @macrocephalopod
  
  Mmm Analytic Combinatorics! Check out the work of Flajolet if you haven’t
  
  1 like
  Thanks. Twitter will use this to make your timeline better. Undo
  
  Undo
1. Show replies

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.

Tweets

macrocephalopod