 Feb 2021

toraritte.github.io toraritte.github.io

17.3. Fixed point
QUESTION: What is a fixedpoint of a function?
ANSWER: See this video) at least, and the Fixedpoint (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
iff(c) = c
. This meansf(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 off
, becausef(2) = 2
.There is also the wiki article fixedpoint 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 Ycombinators is that they produce recursion by evaluating the fixedpoint 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 "fixedpoint of a function"
 Fixedpoint 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 fixedpoint combinator (Y combinator)? (computer science stackexchange)
 FixedPoint Combinators (stackoverflow)
 Fixedpoint 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/20200129Nixoverlayevaluationexample.html
