Coding 2022-09-01

By Max Woerner Chase

I'm a little out of it again, so I'm going to focus on one particular thing that I want in NABTO, but I also, just, want in general.

Okay, so this is seemingly simple to describe in plain language, but it looks to me like it inevitably brings in a lot of complication when I try to formalize it.

So, it's a type, that takes three variables. Two of them are normal type variables. The other one is... A higher-kinded type that takes two arguments. In Python runtime terms, it's easiest to express the whole type as a tuple, so let's go with that. Call the higher-kinded variable HKT, and then there are two possible ways to inhabit this type:

MagicType[HKT, T, V] = tuple[HKT[T, V]] | MagicType[HKT, T, U] + tuple[HKT[U, V]]

Where + between types indicates "the type of the concatenation of tuples of these two types" which I'm pretty sure isn't ever going to be a thing. Functionally, it's something like variadic generics, so it's as if we could define a union of variadic generics...

MagicVariadic[HKT, T, V] = (HKT[T, V],) | (*MagicVariadic[HKT, T, U], HKT[U, V])

Which is still not a thing that the syntax is likely to permit. (This would be used like tuple[*MagicVariadic[HKT, T, V]])

I could imagine trying to write a plugin that would make that all sort of work, possibly in conjunction with existing plugins. But I don't think that's happening until Python 3.11 comes out.

:) (glitchy)

Not that it's not fun to imagine people trying to process that crazy syntax, but you should probably explain what this is for.

All right, so, I've got two motivating examples, and one of them kind of reduces to the other, so I'll do the other one first.

Suppose HKT[T, U] is Callable[[T], U]. Now if you have a T and a tuple[*MagicVariadic[OneArgCall, T, V]], then you can loop or functools.reduce() the tuple over the variable to obtain a V.

(In NABTO, the effect type would need to be tracked somehow.)


Someone's going to want to know whether looping or functools.reduce() is better.

"Better". Anyway, I was messing around earlier, and using functools.reduce() was always slower than an explicit loop, but I was able to get them pretty close by binding functools.reduce() as a default argument. I'm not going to give actual percentages, because if the functions are heavy enough, they'll swamp the difference. So, if you find yourself in this situation, go with whatever solution you're more comfortable with, and be ready to profile the code if it does seem slow.

Anyway, the other place I ended up wanting something like this was in the graph code I was messing with. I had the idea of a composed edge, an edge that follows an Edge[T, U] to an Edge[U, V]. And why stop at one composition, hmm? Or allow the compositions to form some kind of binary tree. Better to just lean on the associative property and collapse them all together. I can't prove I need this from a performance perspective, but it's just unaesthic to allow arbitrary binary structures that all "mean the same thing".

(Actually, from that perspective, there definitely needs to be a canonical form.)

Let's chase that thought for a sec.

MagicTuple[HKT, T, V] = tuple[HKT[T, V]] | tuple[HKT[T, U], MagicTuple[HKT[U, V]]]

I just realized that the U is kind of coming out of nowhere in literally all of these. Throw "existential types" on the pile...




I know, I know.

Anyway, however it's represented, we then want the conceptual ability to map as follows:

Edge[T, U] -> Callable[[T], frozenset[U]] -> Callable[[frozenset[T]], frozenset[U]]

Just a bunch of Haskell-inspired nonsense that I'm pretty sure Haskell wouldn't even let you do.

There are two wolves inside of me. One of them knows, intellectually, that trying to implement all of this type stuff is probably a bad idea. The other one really wants it, come ooon.

Meh, at least it's only my problem if I try to do this.

Thinking over this, I think the way forward is to consider a bunch of problems separately:

Anyway, I'm tired and I have other things I want to do, so I'm going to cap this off for now.

Good night.