Readit News logoReadit News
IngoBlechschmid commented on Monoid-Augmented FIFOs, Deamortised   pvk.ca/Blog/2025/08/19/mo... · Posted by u/todsacerdoti
seanhunter · 14 days ago
For people who haven’t done abstract algebra, don’t be put off by the word “monoid”. A monoid in algebra is just a set with some associative binary operation and an identity element. Mathematicians in the 19th and 20th centuries realised you can study these types of structures and prove things which are true for all of them rather than having to do each one separately, and that led to “abstract algebra”.

So for example, if I have the integers and multiplication, this is a monoid[1]. The identity element is zero, which is an integer, and multiplication is an associative binary operation. It takes two integers and returns an integer.

Once you realise you have a monoid, if you do maths that only relies on the monoid properties then it applies to all monoids, so you could drop a different monoid in there and everything would still work. This ends up being very much like how typeclasses work in Haskell or traits in Rust.

[1] For the curious, it’s not a “group” because the integers don’t have multiplicative inverses. If I have x=2, there is no integer that I can multiply that by to get 1. Integers with addition on the other hand is a group, which is a monoid with the additional property that inverses are present.

IngoBlechschmid · 14 days ago
Somebody asked in a now-deleted comment: 'Right, and what does it mean in the context of "A monad is just a monoid in the category of endofunctors"?'

Here is an answer to this question:

What the parent poster referred to are "monoids in the category of sets". You can recognize this as they have introduced the carrier as (just a) set.

But the notion can be generalized. For instance, a "monoid in the category of datatypes" would not be given by a mathematical set and a mathematical binary operation, but by a datatype and a computable binary operation. (To make this precise, I would need to fix which "category of datatypes" I have in mind. It could be the category of Haskell types and Haskell functions, for instance; but C types and functions would work just as well. I could also go all the way to the effective topos, which contains lots of types which most mainstream programming languages are missing such as true quotient types.)

Finally, a "monoid in the category of endofunctors" is given by an endofunctor and a natural transformation. Endofunctors can be pictured as container kinds (e.g. ordered lists, unordered lists, Maybe/Optional, trees, vectors of length n, pairs, ...) and the additional datum of the natural transformation is what singles out those container kinds which support a "flattening operation" from those which don't. For instance, we can flatten a list of lists into one (long) list, but we cannot flatten a pair of pairs into one pair (we would need to drop two of the four elements).

Just as it is quite convenient that many results about integers or lists also hold for all monoids in the category of sets, it is quite nice that many results about monoids in the category of sets also hold for all monoids in all categories and hence in particular to monads.

IngoBlechschmid commented on Can Large Language Models Play Text Games Well? (2023)   arxiv.org/abs/2304.02868... · Posted by u/willvarfar
willvarfar · 2 months ago
It's been a background thought of mine for a while:

* create a basic text adventure (or MUD) with a very spartan api-like representation

* use an LLM to embellish the description served to the user etc. With recent history in context the LLM might even kinda reference things the user asked previously etc.

* have NPCs implemented as own LLMs that are trying to 'play the game'. These might be using the spartan API directly like they are agents.

Its a fun thought experiment!

(An aside: I found that the graphical text adventure that I made for Ludum Dare 23 is still online! Although it doesn't render quite right in modern browsers.. things shouldn't have broken! But anyway https://williame.github.io/ludum_dare_23_tiny_world/)

IngoBlechschmid · 2 months ago
Gwern has an interesting take on this: https://gwern.net/cyoa By pivoting to "choose your own adventure"-style games, multiple issues (quality, costs) might be resolved.
IngoBlechschmid commented on Can Large Language Models Play Text Games Well? (2023)   arxiv.org/abs/2304.02868... · Posted by u/willvarfar
Workaccount2 · 2 months ago
How are you going to release an LLM eval paper in mid-2025 using

ChatGPT 3.5

Yes, if you are wondering why they don't clarify the model, it because all this was done back in early 2023 (the chat logs are dated). Back then it was only 3.5 and 4 was just freshly released.

Advancement in this space has been so rapid that this is almost like releasing a paper today titled "Video streaming on Mobile Devices" and only using a 3G connection in 2013.

The authors should have held back a few more months and turned the paper into a 3.5 to O3 or any other 2025 SOTA improvement analysis.

IngoBlechschmid · 2 months ago
The paper was originally released in April 2023, it just got version-bumped a couple months ago :-)
IngoBlechschmid commented on 100 years of Zermelo's axiom of choice: What was the problem with it? (2006)   research.mietek.io/mi.Mar... · Posted by u/Bogdanp
skissane · 3 months ago
> So to conclude that there are more reals than naturals, the classical mathematical argument is:

> a) There are more functions N to Bool than naturals.

> b) There are as many reals as functions from N to Bool.

> Now, we of course agree the mistake is in b) not in a).

Given certain foundations, (a) is false. For example, in the Russian constructivist school (as in Andrey Markov Jr), functions only exist if they are computable, and there are only countably many computable functions from N to Bool. More generally, viewing functions as sets, if you sufficiently restrict the axiom schema of separation/specification, then only countably many sets encoding functions N-to-Bool exist, rendering (a) false

IngoBlechschmid · 3 months ago
Indeed, what you write is true from an external point of view; just note that within this flavor of constructive mathematics, the set of functions from N to Bool is uncountable again.

There is no paradox: Externally, there is an enumeration of all computable functions N -> Bool, but no such enumeration is computable.

IngoBlechschmid commented on 100 years of Zermelo's axiom of choice: What was the problem with it? (2006)   research.mietek.io/mi.Mar... · Posted by u/Bogdanp
impostervt · 3 months ago
I've never quite gotten the axiom of choice. Can anyone ELI5?
IngoBlechschmid · 3 months ago
This set of slides, originally devised for the Chaos Communication Congress, might be helpful: https://www.speicherleck.de/iblech/stuff/ac-38c3.pdf

- Precise statement of the axiom

- Overview of its consequences

- A counterexample (in an alternative universe)

- Consistency of the axiom

- Gödel's sandbox for containing the axiom

IngoBlechschmid commented on Mathpad: A mathematical keypad for students and professionals   github.com/Summa-Cogni/Ma... · Posted by u/todsacerdoti
challenger-derp · 3 months ago
Am eagerly anticipating the commercial availability of Mathpad.

At the moment I'm using Espanso, an open source software that lets users map typed character sequences to unicode. So it's possible to set things up in such a way that typing the character sequence ";" "a" ";" makes Espanso replace the entire ;a; string with the greek symbol alpha α.

Symbols like ⇒ that can kind of be "drawn" with common keyboard characters "=" ">" is possibly nice to be mapped to the character sequence ;=>; This is a personal preference inspired by Typst's math notation design choice.

IngoBlechschmid · 3 months ago
I like Vim's digraphs, which go in a similar direction. For instance, Ctrl-K = > gives ⇒, Ctrl-K a * gives α. An overview of available digraphs is available at :digraphs.

Otherwise I like the Agda input method of Emacs, where \to gives ⇒ and \alpha (or \Ga) gives α.

IngoBlechschmid commented on How to (actually) prove it – New Frontiers of Mathematics and Computing in Lean   kirancodes.me/posts/log-h... · Posted by u/gopiandcode
gnulinux · 4 months ago
I personally prefer Agda to Lean or Coq [1] to prove my theorems but this frontier is imho among the most exciting research in theoretical CS in many many decades. I really wish more programmers and mathematicians knew about automated theorem proving and automated reasoning. It's nothing short of revolutionary and I think next generation of pure mathematicians will use these as a crucial tool in their research.

[1] It's a personal preference but Agda is simply a much better language with almost limitless metaprogramming which allows me to write proofs close to as they'd appear in prose math papers. It has a smaller ecosystem though. I've never seen a proof in any other language I personally didn't think would be much more readable/simpler in Agda.

IngoBlechschmid · 4 months ago
I'm currently creating an interactive tutorial on Agda, with lots of embedded exercises (running purely in the browser/on a server, no installation required), perhaps it is useful to some:

https://lets-play-agda.quasicoherent.io/

IngoBlechschmid commented on Tracking types of non-parents in the United States   onlinelibrary.wiley.com/d... · Posted by u/PaulHoule
dijksterhuis · 5 months ago
> Always remember that the world was fine with 2bn people just 100 years ago.

we’ve gone from ~2 billion to ~8 billion in 100 years.

compared to the (highly estimated) figures from before 100 years ago — that’s a massive increase.

the graph is basically a line going straight up compared to the rest of (highly estimated) population data for the last 10k years. and growth is continuing.

https://ourworldindata.org/grapher/population

> Maybe the world in 2050 will be so different that the issue has resolved itself

“maybe a miracle might happen” — is just kicking the can down the road in my book.

we are out of balance with our surrounding environment. there will be a readjustment — whether we choose to make that readjustment ourselves (take responsibility for the problem), or let the readjustment happen (the problem really becomes a problem), is up to us as a species.

> Some problems need tackling at the right time.

some problems take a really long time and a lot of effort to work on so maybe starting to work on them early and proactively might be a good idea. like climate change.

> We don't need to get too crazy about declining populations when we are facing more urgent issues.

speaking of climate change, global overpopulation kinda has an impact on it! more people -> use more resources -> screwing up the planet faster

IngoBlechschmid · 4 months ago
> speaking of climate change, global overpopulation kinda has an impact on it!

You are right, of course; but just to put some perspective to it:

If Thanos-style the population and the CO2 emissions would be cut in half, this would not be enough at all -- we need to get back to 350 ppm (or similar).

I'm writing this to counter the meme that "climate change is Africa's fault, because of their population count".

IngoBlechschmid commented on James Webb Space Telescope reveals that most galaxies rotate clockwise   smithsonianmag.com/smart-... · Posted by u/instagraham
idiotsecant · 5 months ago
How much mass is required to form a black hole in a new universe with perhaps different physical constants? It could be that 'ability to make black holes' is a prerequisite for successful universes in the way way that good genes are a prerequisite for successful organisms. The universes that fail to spawn black holes are 'dead ends' so any life is statistically likely to find itself in a black hole spawning universe.

Maybe there is an 'incentive' for universes to form with physical constants tuned to produce black holes with the available energy in that universe.

IngoBlechschmid · 5 months ago
This circle of ideals seems to be known as: https://en.wikipedia.org/wiki/Cosmological_natural_selection
IngoBlechschmid commented on Automating Interactive Fiction Logic Generation with LLMs in Emacs   blog.tendollaradventure.c... · Posted by u/dskhatri
IngoBlechschmid · 5 months ago
Gwern shared an idea how to exploit the strength of current-generation LLMs, despite their weaknesses, for "create your own adventure"-style fiction. https://gwern.net/cyoa Having people vote on AI-generated potential continuations should yield better results and cut costs at the same time.

From the title I thought this was an implementation of Gwern's idea, but it's not.

u/IngoBlechschmid

KarmaCake day855July 11, 2015View Original