Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How would I write cycle as a lambda function?

Tags:

haskell

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
like image 859
fredoverflow Avatar asked Feb 19 '13 22:02

fredoverflow


People also ask

What are the steps used to create a lambda function?

Step 1: Create a Lambda Function Your Lambda function receives event data and returns a greeting message. Ensure that your Lambda function is under the same AWS account and AWS Region as your state machine. Open the Lambda console and choose Create function. On the Create function page, choose Author from scratch.

How Lambda is executed?

First, Lambda shuts down the runtime. Then Lambda sends a Shutdown event to each registered external extension. The event includes the reason for the shutdown. If another Invoke event results in this execution environment being reused, Lambda initializes the runtime and extensions as part of the next invocation.

Can a Lambda call itself?

A recursive lambda expression is the process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily.


3 Answers

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)))
like image 125
Luis Casillas Avatar answered Oct 19 '22 03:10

Luis Casillas


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.

like image 44
Pubby Avatar answered Oct 19 '22 05:10

Pubby


For fun this is another stuff :

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

or

let f = foldr1 (++) . repeat
like image 5
zurgl Avatar answered Oct 19 '22 05:10

zurgl