Skip to main content
1 of 2
Petr
  • 4.4k
  • 22
  • 31

Haskell

The following code contains no recursive function (even indirectly), no looping primitive and doesn't call any built-in recursive function (uses only IO's output and binding), yet it repeats a given action idenfinitely:

data Strange a = C (Strange a -> a)

-- Extract a value out of 'Strange'
extract :: Strange a -> a
extract (x@(C x')) = x' x

-- The Y combinator, which allows to express arbitrary recursion
yc :: (a -> a) -> a
yc f =  let fxx = C (\x -> f (extract x))
        in extract fxx

main = yc (putStrLn "Hello world" >>)

Function extract doesn't call anything, yc calls just extract and main calls just yc and putStrLn and >>, which aren't recursive.

Explanation: The trick is in the recursive data type Strange. It is a recursive data type that consumes itself, which, as shown in the example, allows arbitrary repetition. First, we can construct extract x, which essentially expresses self-application x x in the untyped lambda calculus. And this allows to construct the Y combinator defined as λf.(λx.f(xx))(λx.f(xx)).

Petr
  • 4.4k
  • 22
  • 31