The Fixed Point: Laziness, Recursion and Fixed Points in Haskell

Laziness in haskell is a weird issue. It makes compilation harder and it makes it much harder to predict a program’s performance, or the global performance impact of a local change (eg a change might be locally good but change to no longer evaluate so many things at once, deferring that evaluation to happen when it is more expensive—because eg the compiler can’t inline or there is no cache efficiency). Indeed Peyton Jones has said that the next haskell [family language] would be strict.

On the other hand, it allows for many programs to be written in nicer, more direct and declarative ways. As well as allowing for weirdness like in this article. But maybe a lot of that is more coming from code transformations enabled by purity and something like clojure-style lazy sequences (or strict if they are finite) plus aggressive inclining and stream fusion would be sufficient.

Fixpoints are one of the most important concepts in denotational semantics and domain theory (see [0] for a good introduction). Denotational semantics lets you precisely specify the meaning of a program as a mathematical object, and also nicely integrates partiality and nontermination. It's quite motivating to learn order theory this way as well.

[0] https://en.wikibooks.org/wiki/Haskell/Denotational_semantics

One practical use of "fix" is emulating Python-like decorators in Haskell: http://web.cecs.pdx.edu/~ntc2/haskell-decorator-paper.pdf

Fixed points are also an important part of the technique described in the paper "Abstracting Definitional Interpreters" https://arxiv.org/pdf/1707.04755.pdf

A well-written article, understandable even to people who are not familiar with Haskell. But, unfortunately, with some typos.

The factorial function can be useful for explaining the basics since it’s so simple, but it makes a poor example for showing when foldr is better than direct recursion.