How would I write cycle as a lambda function?

Question

Just for fun, here is my own version of `cycle`: ``` myCycle :: [a] -> [a] myCycle xs = xs ++ myCycle xs ``` The right-hand side refers to both the function name `myCycle` and the parameter `xs`. Is it possible to implement `myCycle` without mentioning `myCycle` or `xs` on the right-hand side? ``` myCycle = magicLambdaFunction ```

Accepted Answer

Is it possible to implement `myCycle` without mentioning `myCycle` or `xs` on the right-hand side?

The answer is yes and no (not necessarily in that order).

Other people have mentioned the fixed point combinator. If you have a fixed-point combinator `fix :: (a -> a) -> a`, then as you mention in a comment to Pubby's answer, you can write `myCycle = fix . (++)`.

But the standard definition of `fix` is this:

```
fix :: (a -> a) -> a
fix f = let r = f r in r

-- or alternatively, but less efficient:
fix' f = f (fix' f)
```

Note that the definition of `fix` involves mentioning a left-hand-side variable on the right hand side of its definition (`r` in the first definition, `fix'` in the second one). So what we've really done so far is push the problem down to just `fix`.

The interesting thing to note is that Haskell is based on a typed lambda calculus, and for good technical reason most typed lambda calculi are designed so that they cannot "natively" express the fixed point combinator. These languages only become Turing-complete if you add some extra feature "on top" of the base calculus that allows for computing fixed points. For example, any of these will do:

- Add `fix` as a primitive to the calculus.

- Add recursive data types (which Haskell has; this is another way of defining `fix` in Haskell).

- Allow the definitions to refer to the left-hand side identifier being defined (which Haskell also has).

This is a useful type of modularity for many reasons—one being that a lambda calculus without fixed points is also a consistent proof system for logic, another that `fix`-less programs in many such systems can be proven to terminate.

EDIT: Here's `fix` written with recursive types. Now the definition of `fix` itself is not recursive, but the definition of the `Rec` type is:

```
-- | The 'Rec' type is an isomorphism between @Rec a@ and @Rec a -> a@:
--
-- > In  :: (Rec a -> a) -> Rec a
-- > out :: Rec a        -> (Rec a -> a)
--
-- In simpler words:
--
-- 1. Haskell's type system doesn't allow a function to be applied to itself.
--
-- 2. @Rec a@ is the type of things that can be turned into a function that
--    takes @Rec a@ arguments.
--
-- 3. If you have @foo :: Rec a@, you can apply @foo@ to itself by doing
--    @out foo foo :: a@.  And if you have @bar :: Rec a -> a@, you can do 
--    @bar (In bar)@.
--
newtype Rec a = In { out :: Rec a -> a }

-- | This version of 'fix' is just the Y combinator, but using the 'Rec'
-- type to get around Haskell's prohibition on self-application (see the
-- expression @out x x@, which is @x@ applied to itself):
fix :: (a -> a) -> a
fix f = (\x -> f (out x x)) (In (\x -> f (out x x)))
```

How would I write cycle as a lambda function?

Solution

Problem