Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What is the name of λx.λf.fx in lambda calculus?

Does the corresponding function have a standard name in functional programming languages, like Haskell?

In object oriented programming, is there a usual name for a method foo which takes a function as an argument, such that x.foo(f) returns f(x)?

share|improve this question
3  
You need to buy a dictionary. –  Robert Harvey May 17 '13 at 23:19
8  
Which one? Where? How much? –  Alexey May 17 '13 at 23:21
1  
I do not understand the downvotes. It seems a perfectly reasonable question to me. –  Giorgio May 18 '13 at 8:15
    
I have posted an answer below but I realised that the OP was asking what is the name of this lambda expression so I deleted =D –  TemporaryNickName May 18 '13 at 8:52
    
The concept you refer to is known as a combinator, have a read here if you're not familiar en.wikipedia.org/wiki/SKI_combinator_calculus though I'm not familiar with a known combinator of the nature you refer to though, C from BCKW is close (it's flip) but not the same en.wikipedia.org/wiki/B,C,K,W_system why not have some fun and come up with the combination of those combinators that results in your function :) –  Jimmy Hoffa May 18 '13 at 13:50

5 Answers 5

In Haskell, \x.\f.f x is flip ($) which as $ is read as apply, I would read as reverse apply.

Roughly based on http://stackoverflow.com/questions/4090168/is-there-an-inverse-of-the-haskell-operator

share|improve this answer
    
This wrong... flip is \f.\x.\y.f y x flip is C here en.wikipedia.org/wiki/B,C,K,W_system –  Jimmy Hoffa May 18 '13 at 13:46
    
also adding $ to flip like this is expecting a partially applied function that takes over 2 arguments where you're going to only flip the last 2 so you partially apply all but those 2 –  Jimmy Hoffa May 18 '13 at 13:52
5  
So you doubt that (\f.\x.\y.f y x) (\f.\x.f x) reduces to (\x.\f.f x) modulo renaming? Which it does. –  Dan D. May 19 '13 at 0:02

Using the standard combinators you can express this function as

C I

where

C f x y = (f y) x

In Haskell it would be

flip id

Here id's type is specialized to (a -> b) -> a -> b and flip swaps a -> b and a.

You can also express it in the SKI calculus:

S (K (S I)) K
share|improve this answer
    
+1 for deducing the combinators for this. I really don't suspect it's a much known thing, though if as he identified it's something related to church numerals, I'm inclined to wonder if CI is documented anywhere as relevant in anyones church numeral studies –  Jimmy Hoffa May 19 '13 at 7:17
up vote 3 down vote accepted

In the original Alonzo Church's "The calculi of lambda-conversion", he denotes this combinator by T.

In the context of Church numerals, it is called exp. This matches the "shorthand" notation used by Church for the "application" of a term N to a term M: "[MN]" stands for "(NM)".

I haven't heard yet of a standard name for an analogous function in programming.

share|improve this answer

This is sometimes referred to as the thrush combinator, and in Clojure it's called the thread-first macro. It's primary use is in allowing you to express a computation as a series of chained computations in the order they execute in. For instance, taking a value x, passing it to a function f, then passing the results of f(x) to a function g, would be written as g(f(x)) using standard function composition (or g (f x) if you're working with implicit parentheses.) This can be awkward when there's a large number of chained functions because you have to read them in the reverse order of how they execute. The thrush combinator lets you express this differently, if we define the thrush combinator as:

T x f = f x
T x f g ... = T (T x f) g ...

Then the expression T x f g h becomes h (g (f x)).

(For those looking for more information as well as a concrete implementation in the language Racket, I have a blog post on the subject: Thrush Combinator in Racket)

share|improve this answer

I hope I understand your question correctly, but I believe this is known as the (reverse) Pipe Operator in ML languages.

[1; 2; 3] |> List.map sq // let it = [1; 4; 9]

There is also the Reverse Pipe Operator which helps with order of operations.

printf "The value is.." <| 2 + 3 // let it = "The value is..5"

This is useful because the unpiped form

printf "The value is.." 2 + 3 ;; error

would error because printf would try to evaluate "The value is.." 2 and error because there is no defined + operator. In order to make that work, use parenthesis:

printf "The value is.." (2 + 3) // let it = "The value is..5"

As for practical use, the |> operator is incredibly useful and the bread-and-butter of many ML and ML-inspired languages such as F#, LiveScript and Elixir. <| is less common and typically only used when it increases readability.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.