QUESTION: What is a fixed-point of a function?

ANSWER: See this video) at least, and the Fixed-point (mathematics)) wikipedia article:

In mathematics, a fixed point (sometimes shortened to fixpoint, also known as an invariant point) of a function is an element of the function's domain that is mapped to itself by the function. That is to say, c is a fixed point of the function f if f(c) = c. This means

f(f(...f(c)...)) = f n(c) = c

an important terminating consideration when recursively computing f. A set of fixed points is sometimes called a fixed set.

For example, if f is defined on the real numbers by f(x)=x^{2}-3x+4,}, then 2 is a fixed point of f, because f(2) = 2.

There is also the wiki article fixed-point combinator that actually plays a role here, but read through the articles in this order.

Then dissect the Stackoverflow thread What is a Y combinator?, and pay attention to the comments! For example:

According to Mike Vanier's description, your definition for Y is actually not a combinator because it's recursive. Under "Eliminating (most) explicit recursion (lazy version)" he has the lazy scheme equivalent of your C# code but explains in point 2: "It is not a combinator, because the Y in the body of the definition is a free variable which is only bound once the definition is complete..." I think the cool thing about Y-combinators is that they produce recursion by evaluating the fixed-point of a function. In this way, they don't need explicit recursion. – GrantJ Jul 18 '11 at 0:02

(wut?)

Other resources in no particular order:

• google search for "fixpoint evaluation fixed point combinator explained"
• Cornell's CS 6110 S17 Lecture 5
• google search for "fixed-point of a function"
• Fixed-point theorem (wikipedia)
• How can I find the fixed points of a function? (math stackexchange)
• The Y Combinator (Slight Return) (see the "Fixpoint of functions" section)
• Clear, intuitive derivation of the fixed-point combinator (Y combinator)? (computer science stackexchange)
• Fixed-Point Combinators (stackoverflow)
• Fixed-point combinator (HandWiki)

QUESTION: How the hell did they come up with the idea of using this with Nix and package management? (..and who? I remember a video saved somewhere, but maybe that was about overlays)

QUESTION: ... and how does it work in this context?

ANSWER: Well, not an answer yet, but this may be something in the right direction:

http://blog.tpleyer.de/posts/2020-01-29-Nix-overlay-evaluation-example.html

"fixed-point", "fix point" seems to be most important concept in Nix, because overrides, overridePackages, overlays are built using it.

• Nix Pill - Chapter 17. Nixpkgs Overriding Packages (the first place I saw this concept properly described)
• Nixpkgs issue - Add pkgs.overrideWithScope#44196 (best high level summary of Nixpkgs ever read)
• How to Fake Dynamic Binding in Nix
• Comment by zimbatm on NixOS Discourse
• nixpkgs/lib/fixed-points.nix