Skip to main content
added 515 characters in body
Source Link
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)).


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" >>)

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)).

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" >>)
Source Link
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)).