Skip to main content
Source Link
Flonk
  • 7.8k
  • 3
  • 23
  • 25

Haskell, denotational semantics

x = undefined

As most of you probably know, undefined :: a can be cast to any type - or in other words, every type contains a special value undefined, also called (pronounced "bottom"). We say that is less defined than any other inhabitant of that type, and while its a little too in-depth for this post, can also be seen as a computation that never finishes.

Let's import Data.Function.

In there, there is a function called fix, which according to the Haskell docs finds the least-defined fixpoint of f, by repeatedly applying the function to itself. Let's recap:

We need to find a value x, for which x = x + 2, or, equivalently x = (+2) x. Lets factor (+2) into a function called f. We get x = f x, which is precisely the definition of a fixed point for the function f. Since we don't know x yet, we need a function that knows how to calculate a fixpoint, like fix; x is our placeholder for said fixpoint (x = fix f), so our whole equation becomes fix f = f (fix f).

This is just the definition of fix, so fix indeed finds a fixed point for a given function!

What I'm trying to say is: To solve OP's problem, all we need to do is pipe fix (+2) through ghci. When we do that however, we see nothing, as ghci gets caught in an infinite loop. But since I said that infinite loops can be seen as ⊥, we arrive at the fact that x = ⊥, which by the way turns out to be the only solution to OP's question (who would have guessed).

Post Made Community Wiki by Flonk