News for hackers. Stuff that matters.
Re:Abusing the algebra of algebraic data types – why does th... by svat on Monday October 10, 2022 @12:34PM (#33153453)
A very nice fact that I coincidentally learned just yesterday, which is not in the linked answer but is touched on in one of the comments and in an edit on the accepted answer: there is an explicit bijection that maps a binary tree to seven binary trees (and vice-versa, by the inverse function).

Consider the definition of a binary tree: "a binary tree is either empty, or is a root with a left tree and a right tree". This we can write as

    T = 1 + T²
Solving the analogous equation z = 1 + z² in the complex numbers gives z to be a primitive sixth-root of unity, i.e. z⁶ = 1, and so z⁷ = z. It turns out that T⁷ = T, which we can show with some algebra (without subtractions) by repeatedly applying the transformations T→1+T² or 1+T²→T:

    T⁷ 
    = T⁶ + T⁸
    = T⁵ + T⁷ + T⁸
    = T⁴ + T⁶ + T⁷ + T⁸
    = T⁴ + 2T⁷
    = T³ + T⁵ + 2T⁷
    = T³ + T⁶ + T⁷
    = T² + T⁴ + T⁶ + T⁷
    = T² + T⁵ + T⁷
    = T² + T⁶
    = T + T³ + T⁶
    = T + T² + T⁴ + T⁶
    = T + T² + T⁵
    = 2T + T³ + T⁵
    = 2T + T⁴
    = 1 + T + T² + T⁴
    = 1 + T + T³
    = 1 + T²
    = T
This can be used to give an explicit bijection: see Andreas Blass's paper "Seven trees in one": https://arxiv.org/pdf/math/9405205 (see also https://twitter.com/CihanPostsThms/status/157901771352705024... and a "game" version at http://lebarde.alwaysdata.net/seventrees/)
Re:Abusing the algebra of algebraic data types – why does th... by travisgriggs on Monday October 10, 2022 @01:55PM (#33154421)
"Bijection" -> https://en.wikipedia.org/wiki/Bijection

Monday was looking boring. I'm excited now about the new adventure I've set for myself to somehow inject this (new for me) term into a discussion appropriately.

Re:Abusing the algebra of algebraic data types – why does th... by harveywi on Monday October 10, 2022 @05:12PM (#33156436)
As long as you surject it whenever you inject it you'll be fine.
Re:Abusing the algebra of algebraic data types – why does th... by krastanov on Monday October 10, 2022 @02:48PM (#33155073)
This is fascinating, but I am still curious: would I ever have a good reason to repackage seven binary trees as one (or other way around)?
Re:Abusing the algebra of algebraic data types – why does th... by hither_shores on Monday October 10, 2022 @03:37PM (#33155559)
The particular example is not the point. The question you should be asking is

> would I ever have a need to understand what happens when you perform algebraic manipulations on data structures

and the answer is as usual that it depends on what you're working on. Parsers? Absolutely. CRUD apps? Yes, but only if you look for them. Numerical linear algebra? Probably not.

Re:Abusing the algebra of algebraic data types – why does th... by feoren on Monday October 10, 2022 @04:27PM (#33156042)
> CRUD apps? Yes, but only if you look for them.

I upvoted just for this breath of fresh air right here. CRUD apps are boring and crappy because people make them boring and crappy. I find uses for this type of thing all the time in "boring" CRUD apps, because I look for them.

Re:Abusing the algebra of algebraic data types – why does th... by svat on Monday October 10, 2022 @03:56PM (#33155758)
I can't imagine any application. :-)

The fascination is more that of explanation: if you treat T = 1 + T^2 as an algebraic equation in the complex numbers, you can get a lot of expressions that are meaningless: it's hard to make sense of T = 1/2 ± i√3/2 or T^3 = -1 or even T^6 = 1 (there is certainly no bijection sending six trees to the empty tree). But then, T^7 = T is suddenly very much meaningful and we can turn it into an explicit description. What's going on? Which equations are "meaningful" and which are not?

Blass's paper gives an explanation: an equation is meaningful if you can derive it by working in (something like) N[T]/(T = 1 + T^2) (with some more conditions). Baez's discussion (linked above) puts it in terms of "categorification", and is also interesting.

Re:Abusing the algebra of algebraic data types – why does th... by jerf on Monday October 10, 2022 @04:09PM (#33155881)
This is like giving an artist a new shade of color they've never had before, like a new rich blue or something. It isn't that everything is improved by using that new color as much as possible everywhere. It's that it opens up new possibilities you may never have considered before. This insight may be useless, but there are other useful ones that can emerge that you wouldn't have thought of on your own in a long time.
Re:Abusing the algebra of algebraic data types – why does th... by feoren on Monday October 10, 2022 @04:25PM (#33156021)
Sharding a huge database index (or other binary tree structure) onto 7 different servers or hard drives? Or 49 (recursively apply it)? I don't know if that's actually useful here but it's the first thing that came to mind.
Re:Abusing the algebra of algebraic data types – why does th... by mjcohen on Monday October 10, 2022 @03:33PM (#33155515)
Wouldn't t be a cube root of -1? t=t^2+1 => 0=t^2-t+1 => 0=(t+1)(t^2-t+1)=t^3+1
Re:Abusing the algebra of algebraic data types – why does th... by 6gvONxR4sf7o on Monday October 10, 2022 @03:44PM (#33155632)
Same thing. A cube root of -1 is a sixth root of 1.