Introduction I want to return to something I've mentioned a couple of times in the past - the fact that applying certain type constructors performs a tensor product. First some admin stuff: > {-# LANGUAGE DeriveFunctor #-} > {-# LANGUAGE FlexibleInstances #-} > {-# LANGUAGE MultiParamTypeClasses #-} > {-# LANGUAGE UndecidableInstances #-} > {-# LANGUAGE TypeApplications #-} > {-# LANGUAGE…
Introduction One game I like to play is decomposing code and algorithms as compositions of simpler pieces even when they already seem as simple as they could be. One example is the observation that adjoint mode automatic differentiation isn't a separate algorithm to forward mode automatic differentiation but a composition of forward mode and transposition. I talked about this in an old paper of…
Biased posteriors the hard way I was previously interested to see how die rolls in an RPG appear when conditioned on you having survived an unlikely situation. As might have been predicted, if the die rolls contribute to that survival in a largely additive way, for example by being damage scored against a large opponent, then the posterior distribution of the rolls looks exponentially tilted.…
1 We only hear about the survivors In the classic Star Trek episode Errand of Mercy, Spock computes the chance of success: CAPTAIN JAMES T. KIRK : What would you say the odds are on our getting out of here? MR. SPOCK : Difficult to be precise, Captain. I should say, approximately 7,824.7 to 1. And yet they get out of there. Are Spock’s probability computations unreliable? Think of it another way.…
A more stable version of this article can be found on github . The Problem Since the early days of role-playing games there has been debate over which rolls the GM should make and which are the responsibility of the players. But I think that for “perception” checks it doesn’t really make sense for a player to roll. If, as a player, you roll to hear behind a door and succeed, but you’re told there…
This is something I put on github years ago but I probably should have put it here. Here's an elementary example of the use of the list monad: > test1 = do > x <- [1, 2] > y <- [x, 10*x] > [x*y] We can desugar this to: > test2 = [1, 2] >>= \x -> [x, 10*x] >>= \y -> [x*y] It looks like we start with a list and then apply a sequence (of length 2) of functions to it using bind (>>=). This is probably…
Google have stopped supporting the Chart API so all of the mathematics notation below is missing. There is a PDF version of this article at GitHub . Some literate Haskell but little about this code is specific to Haskell... > {-# LANGUAGE DataKinds #-} > {-# LANGUAGE TypeFamilies #-} > {-# LANGUAGE TypeOperators #-} > {-# LANGUAGE UndecidableInstances #-} > > import GHC.TypeLits Introduction This…
Some pointers to things not in this blog One reason I haven't blogged much recently is that my tolerance for blogger.com has reached its limit and I've been too lazy to build my own platform supporting mathematics and code. (For example, I can't get previewing on blogger to work today so I'm just publishing this and hope the reformatting is acceptable.) But that doesn't mean I haven't posted stuff…
Why does water fall out of an inverted cup? Before considering nuclear fusion, let's consider something much more familiar. If you turn a cup full of water upside down, the water falls out. Why is this? It seems obvious: with nothing supporting the water from below, gravity pulls the water out of the cup. But let's look a little closely at the left side of Figure 1. We have water in an inverted…
Important Note Google have stopped supporting the Chart API so all of the mathematics notation below is missing. There is a PDF version of this article at GitHub . Preface Functional programming encourages us to program without mutable state. Instead we compose functions that can be viewed as state transformers. It's a change of perspective that can have a big impact on how we reason about our…
Introduction I've been reading a little about concentration inequalities recently. I thought it would be nice to see if you can use the key idea, if not the actual theorems, to reduce the complexity of computing the probability distribution of the outcome of stochastic simulations. Examples might include random walks , or queues . The key idea behind concentration inequalities is that very often…
Introduction Popular science writing about quantum mechanics leaves many people full of questions about the status of photons. I want to answer some of these without using any tricky mathematics. One of the challenges is that photons are very different to ordinary everyday objects like billiard balls. This is partly because photons are described by quantum mechanics whereas billiard balls are…
Introduction TL;DR The behaviour of a certain kind of delay component has a formal similarity to Löb's theorem which gives a way to embed part of provability logic into electronic circuits. Here's a famous paradoxical sentence: This sentence is false If it's false then it's true and if it's true then it's false. Here's a paradoxical electronic circuit: The component in the middle is an inverter.…
Introduction Sometimes you want to differentiate the expected value of something. I've written about some tools that can help with this. For example you can use Automatic Differentiation for the derivative part and probability monads for the expectation. But the probability monad I described in that article computes the complete probability distribution for your problem. Frequently this is…
Introduction A popular question in mathematics is this: given a function \(f\) , what is its "square root" \(g\) in the sense that \(g(g(x)) = f(x)\) . There are many questions about this on mathoverflow but it's also a popular subject in mathematics forums for non-experts. This question seems to have a certain amount of notoriety because it's easy to ask but hard to answer fully. I want to look…
Introduction Gabriel Gonzalez has written quite a bit about the practical applications of free monads . And "haoformayor" wrote a great stackoverflow post on how arrows are related to strong profunctors. So I thought I'd combine these and apply them to arrows built from profunctors: free arrows. What you get is a way to use arrow notation to build programs, but defer the interpretation of those…
Attempted segue Since I first wrote about profunctors there has been quite a bit of activity in the area so I think it's about time I revisited them. I could just carry on from where I left off 5 years ago but there have been so many tutorials on the subject that I think I'll have to assume you've looked at them. My favourite is probably Phil Freeman's Fun with Profunctors . What I intend to do…
Introduction Google have stopped supporting the Chart API so all of the mathematics notation below is missing. There is a PDF version of this article at GitHub . There are many introductions to the Expectation-Maximisation algorithm. Unfortunately every one I could find uses arbitrary seeming tricks that seem to be plucked out of a hat by magic. They can all be justified in retrospect, but I find…
Introduction Programming languages and libraries for numerical work tend not to place a lot of emphasis on the types of their data. For example Matlab, R, Octave, Fortran, and Numpy (but not the now defunct Fortress ) all tend to treat their data as plain numbers meaning that any time you have a temperature and a mass, say, there is nothing to prevent you adding them. I've been wondering how much…
> {-# LANGUAGE RankNTypes, MultiParamTypeClasses, TypeOperators #-} Introduction After I spoke at BayHac 2014 about free monads I was asked about cofree comonads. So this is intended as a sequel to that talk. Not only am I going to try to explain what cofree comonads are. I'm also going to point out a very close relationship between cofree comonads and free monads. At the beginning of the talk the…
Introduction There are two broad approaches to problem solving that I see frequently in mathematics and computing. One is attacking a problem via subproblems, and another is attacking a problem via quotient problems. The former is well known though I’ll give some examples to make things clear. The latter can be harder to recognise but there is one example that just about everyone has known since…
Introduction As Dan Doel points out here , the gadget Free that turns a functor into a monad is itself a kind of monad, though not the usual kind of monad we find in Haskell. I'll call it a higher order monad and you can find a type class corresponding to this in various places including an old version of Ed Kmett's category-extras . I'll borrow some code from there. I hunted around and couldn't…
Introduction A while back I talked about the idea of reinversion of control using the continuation monad to wrest control back from an interface that only wants to call you, but doesn't want you to call them back. I want to return to that problem with a slightly different solution. The idea is that we build an interpreter for an imperative language that's an embedded Haskell DSL. You arrange that…
Introduction Suppose we are given a function of boolean arguments that returns a boolean result. Alice has bits, and Bob has another bits . Alice and Bob are widely separated and don't know each other's bits. What is the total number of bits that Alice has to send to Bob and that Bob has to send to Alice so that between them they can compute ? Think about how complex might get. The and might each…
Introduction Recall the standard cartoon sketch of the proof of Gödel's first incompleteness theorem . We start by defining a predicate, , that is true if and only if its argument is provable. (Or more accurately, is true if is the Gödel number of a provable proposition.) With some quining we can use this to construct the proposition which says . The proposition asserts its own unprovability.…