CODEWITHSUNDEEP
haskell
fredoverflow
fredoverflow

Reputation: 263078

How would I write cycle as a lambda function?

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

Upvotes: 9

Views: 518

Answers (4)

Luis Casillas
Luis Casillas

Reputation: 30227

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:

  1. Add fix as a primitive to the calculus.
  2. Add recursive data types (which Haskell has; this is another way of defining fix in Haskell).
  3. 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)))

Upvotes: 11

hugomg
hugomg

Reputation: 69924

No one pointed out the "obvious" version of the fix solution yet. The idea is that you transform the named recursive call into a parameter.

let realMyCycle = fix (\myCycle xs -> xs ++ myCycle xs)

This "recursive name" introducing trick is pretty much what let in does in Haskell. The only difference is that using the built-in construct is more straightforward and probably nicer for the implementation.

Upvotes: 0

zurgl
zurgl

Reputation: 1930

For fun this is another stuff : 

let f = foldr (++) [] . repeat

or 

let f = foldr1 (++) . repeat

Upvotes: 5

Pubby
Pubby

Reputation: 53017

I think this works:

myCycle = \xs -> fix (xs ++)

http://en.wikipedia.org/wiki/Fixed-point_combinator

In programming languages that support anonymous functions, fixed-point combinators allow the definition and use of anonymous recursive functions, i.e. without having to bind such functions to identifiers. In this setting, the use of fixed-point combinators is sometimes called anonymous recursion.

Upvotes: 6

Related Questions