 |
|
| |
|
|
|
at Global Oneness Community.
Share your dreams and let others help you with the interpretation!
Dream Sharing Forum
|
|
Fixed point combinator - Other fixed point combinators | | Fixed point combinator - Other fixed point combinators: Encyclopedia II - Fixed point combinator - Other fixed point combinators | | A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
The Y combinator can be expressed in the SKI-calculus as
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
The simplest fixed point combinator in the SK-calculus, found by John Tromp, is
Y = S S K (S (K (S S (S (S S K)))) K)
which corresponds to the lambda expres ...
See also:Fixed point combinator, Fixed point combinator - Existence of fixed point combinators, Fixed point combinator - Example, Fixed point combinator - Other fixed point combinators | | | Fixed point combinator, Fixed point combinator - Example, Fixed point combinator - Existence of fixed point combinators, Fixed point combinator - Other fixed point combinators, combinatory logic, untyped lambda calculus, typed lambda calculus, anonymous recursion | | |
| | | Fixed point combinator: Encyclopedia II - Fixed point combinator - Other fixed point combinators
Fixed point combinator - Other fixed point combinators
A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:
Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
The Y combinator can be expressed in the SKI-calculus as
Y = S (K (S I I)) (S (S (K S) K) (K (S I I)))
The simplest fixed point combinator in the SK-calculus, found by John Tromp, is
Y = S S K (S (K (S S (S (S S K)))) K)
which corresponds to the lambda expression
Y = (λx λy. x y x) (λy.λx. y(x y x))
Another common fixed point combinator is the Turing fixed-point combinator (named for its discoverer, Alan Turing):
Θ = (λx. λy. (y (x x y))) (λx. λy. (y (x x y)))
It also has a simple call-by-value form:
Θv = (λx. λy. (y (λz. x x y z))) (λx. λy. (y (λz. x x y z)))
Fixed point combinators are not especially rare (there are infinitely many of them). Some, such as this one (constructed by Jan Willem Klop) are useful chiefly for amusement:
Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L L L)
where:
L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))
Other related archivesAlan Turing, Church encoding, Haskell B. Curry, SKI-calculus, Standard ML, anonymous recursion, applicative-order, call-by-name, call-by-value, combinatorial calculus, combinatory logic, example, fixed point, higher-order function, lambda abstractions, recursive functions, recursive types, simply typed lambda calculus, typed lambda calculus, untyped lambda calculus, η-expansion
 Adapted from the Wikipedia article "Other fixed point combinators", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki |
|
|
|
More material related to Fixed Point Combinator can be found here:
|
|
|
« Back
|
Search the Global Oneness web site |
|
|
|
|
|
Sneak-Peek of Global Oneness Community
Hi friend! The Global Oneness Community, the place for information and sharing about Oneness is not really launched yet (you will see there is still some clean up to do) ...but it is now open for a sneak-peek! And if you wish - please register and become one of the very first members to do so! Jonas
Forum Home,
Articles,
Photo Gallery,
Videos,
News,
Sitemap
...and much more!
|
