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))
.
Update: As suggested, I'm posting a variant that is closer to the definition of Y in the untyped lambda calculus:
data Strange a = C (Strange a -> a)
-- | Apply one term to another, removing the constructor.
(#) :: Strange a -> Strange a -> a
(C f) # x = f x
infixl 3 #
-- The Y combinator, which allows to express arbitrary recursion
yc :: (a -> a) -> a
yc f = C (\x -> f (x # x)) # C (\x -> f (x # x))
main = yc (putStrLn "Hello world" >>)