Arnaud Spiwack

Typically text which narrates a source material without adding any context or value. And possibly adding some misunderstanding here and there.

Sometimes it takes a while to realise that some text has been AI generated. Sometimes one may not notice. Partly this is because people have been writing hand-crafted AI-generated text since long before AI was involved at all. 1/2

So maybe the Arrow implementation is significantly better than that of foldl. But I don't know that for even remotely sure. Anyway, this was a short experiment, we didn't carry it very far. You can find it here github.com/jameshaydon/janus… 11/11

Apparently, State is already slower than an hand-rolled scan, and Day doesn't really make things worse. On the other hand it seems to do (much!) better than a zipless Arrow-based implementation with foldl (which produces pairs original/computed on the first scan). 10/11

How does it fare? Well, it isn't as fast as the zip of two scans from base. Though it appears to be within 30% slowdown, which, considering how badly behaved Day is as an applicative, is rather surprising. In fact it's just as fast as the zip of two foldl Scan. 9/11

This doesn't use the Const applicative, since there is no `forall x. Const x -> x`. But this is otherwise a rather pleasing display of the most famous non-monad applicatives. 8/11

We can now reverse scans simply by applying the Backward applicative. We can still implement Arrow: composition is given by the Compose applicative, (***) is obtained by the Day applicative. Voilà! No more zips! 7/11

This suggest the solution: instead of existentially quantifying over some internal state, let's quantify over an entire applicative (we also have to replace the seed with a run function) data Scan a b = forall f. Applicative f => MkScan :: (a -> f b) (forall x. f x -> x) 6/11

Looking at the implementation of scanr in fold, we can see that it's the same as scanl, but mediated through a reverse State monad, very reminiscent of the Backward applicative hackage-content.haskell.org/… . 5/11

Problem solved? No: the trapped rain problem zips a scanr and a scanl. While Scan supports both scanr and scanl they can't be interleaved with the arrow combinators (once you call either you no longer have a Scan). We need a way to reverse a scan. 4/11

Let's turn to the foldl package and its implementation of Scan: data Scan a b = forall x. Scan (a -> State x b) x This type implement Arrow. So if we have two scans we can do them in parallel, without zipping! 3/11

This started with my friend James Haydon complaining about the fact that the classic trapped rain problem stackoverflow.com/questions/… involves the zip of two scans. But zip can drop data, so we have to prove that it doesn't. Can we enforce this? 2/11

The foldl hackage.haskell.org/package/… package is one of the most remarkable bit of the Haskell ecosystem. Turns out, we can make it better. I mean worse. I mean… maybe? 1/11

So here's my suggested definition: a pattern in a function f with a left adjoint g, and matching a against pattern f binds g(a) (multiple variables are obtained by using product posets). 8/8

Now our conditions become g∘f≤id and id≤f∘g (hint: id is minimal). That is f and g form a Galois connection (equivalently ∀a x, x≤f(a) ⟺ g(x)≤a). I think it generalises: in a subtyping situation, you don't typically have x=f(a) only x≤f(a). Exactly what shows up! 7/8

But not the other way around. So the error is a maximal element in some order. So let's imagine we have flat orders + a top element. Our functions are order preserving and top preserving. 6/8

I want to argue that it's because the error element is treated as an element like all the others. But it isn't like the other. An error is, somehow, worse than the other. We can think of this in term of an order: it's always possible to transition from a value to an error. 5/8

It's not too bad, but partial functions aren't the most well-behaved mathematical objects. Let's try and do better. To get rid of partial functions we can, of course, add an error point to our sets. But then we have to do some error monad shenanigans. 4/8

Second attempt. It's a function f, which is a (partial) retract. That is there's a partial function g such that g∘f=id. But that's a little too weak. We also want to know something about f∘g. Presumably that it's id on the domain of g. 3/8

One simple answer could be: it's some arbitrary function. It works, since we're defining a relation we could just say “forall a b, such that x = f(a,b)…”. There's no problem with this, but I don't think that's how we actually write inference rules. 2/8