Geeky things and other research from a work in progress


"Upwards and downwards accumulations on trees" translated into Haskell

I was reading "Upwards and downwards accumulations on trees" by Jeremy Gibbons, and it's written in the Bird-Meertens formalism (a.k.a. Squiggol) of yesteryear. Not that I have anything against people who can write and understand this stuff (in fact, I have a lot of respect for them), but for me, the inconsistent and seemingly arbitrary notation leaves something to be desired. In an attempt to understand what was actually being done, I translated most of the equations to Haskell code. If you plan on reading this paper, here's hoping I could jump-start your comprehension with this contribution.

The only real issue that I ran into while performing this translation is in the function s_fork_sl2. The second component of the catamorphism, ((⊙ ↟ ≪) ∘ ≪²), does not have the expected type (b, b) -> a -> (b, b) -> (b, b). After attempting to puzzle through how to unify the two, I eventually gave up and just came up with a function that seemed to do what I thought it should do, pairs g (x, _) _ (y, _) = (g x y, x) where g :: b -> b -> b is ⊙. But I'm not sure whether there's a bug in the definition in the paper or the one in my code. The code seems to work for a few tests. If you've already read this paper or you're at all interested in debugging Squiggol, I would be happy to learn how this works.


  1. Sorry I'm such a late-comer, but no one's said anything, and I just found your blog - wonderful stuff, by the way.

    I guess the big issue is how do you interpret the equivalents of 'fst' and 'snd' on a triple.
    Because the trees used here are triples, it doesn't quite fit the form. Thank you for going through it and working on it beforehand.

  2. I'm not sure I understand you. Can you give some context?

  3. Well, the way in which the middle component of a triple gets "absorbed" by the operator is suggested, but is not specified very formally; it seems as if readerd (users?) are just supposed to "get it" by osmosis. It seems to me that it complicates how that "((⊙ ↟ ≪) ∘ ≪²)" part is supposed to obtain the subscript from the tree, and treat the other two parts as a pair. I am guessing that one is supposed to just ignore the middle part, and treat the two branch results as a pair. Since the examples in the paper only do this with operators and not with entire function expressions, it seems like the "crash course" in the notation is more like a "crash-and-burn" course.

  4. Ah yes. I think I see what you're saying. I had forgotten about the notation and the subscript approach to ┴.

  5. No to mention how (to my perspective, anyway) the operators tend to take currying as a matter of course, treating arguments as a pair, or as two separate values, with no warning, or notice. That makes it all the tougher to interpret.