Church numerals: Difference between revisions

Line 29:

=={{header|AppleScript}}==

Implementing '''churchFromInt''' as a fold seems to protect Applescript from overflowing its (famously shallow) stack with even quite low Church numerals.

<syntaxhighlight lang=applescript>--------------------- CHURCH NUMERALS --------------------

<syntaxhighlight lang="applescript">--------------------- CHURCH NUMERALS --------------------

-- churchZero :: (a -> a) -> a -> a

Line 202:

Line 201:

=={{header|C sharp|C#}}==

The following implementation using the "RankNTypes" facilities as per Haskell by using a delegate to represent the recursive functions, and implements the more advanced Church functions such as Church subtraction and division that wouldn't be possible otherwise; if the ability to map functions of higher ranked "Kind's" to be the same type were not included, the Church type would be an infinite undecidable type:

<syntaxhighlight lang=csharp>using System;

<syntaxhighlight lang="csharp">using System;

public delegate Church Church(Church f);

Line 259:

Line 257:

The Church Division function is implemented by recursively counting the number of times the divisor can be subtracted from the dividend until it reaches zero, and as C# methods do not allow direct recursion, rather than using a Y-Combinator to implement this just uses mutually recursive private sub methods.

=={{header|Chapel}}==

Chapel doesn't have first class closure functions, so they are emulated using the default method of inherited classes with fields containing the necessary captured values. The instantiated classes are `shared` (reference counted) to avoid any chance that references within their use causes memory leaks. As with some other statically typed languages, Chapel's implementation of generics is not "type complete" as to automatically doing beta reduction, so the following code implements a recursively defined class as a wrapper so as to be able to handle that, just as many other statically-typed languages need to do:

<syntaxhighlight lang=chapel>class Church { // identity Church function by default

<syntaxhighlight lang="chapel">class Church { // identity Church function by default

proc this(f: shared Church): shared Church { return f; }

}

Line 445:

Line 442:

The above exercise goes to show that, although Chapel isn't a functional paradigm language in many senses, it can handle functional paradigms, although with some difficulty and complexity due to not having true lambda functions that are closures...

=={{header|Clojure}}==

<syntaxhighlight lang=clojure>(defn zero [f] identity)

<syntaxhighlight lang="clojure">(defn zero [f] identity)

(defn succ [n] (fn [f] (fn [x] (f ((n f) x)))))

(defn add [n,m] (fn [f] (fn [x] ((m f)((n f) x)))))

Line 471:

Line 467:

81

64</pre>

=={{header|Crystal}}==

Although the Crystal language is by no means a functional language, it does offer the feature of "Proc"'s/lambda's which are even closures, meaning that they can capture environment state from outside the scope of their body. Using these plus a structure to act as a wrapper for the recursive typed Church functions and the Union types to be able to eliminate having to use side effects, the following code for the Extended Church Numeral functions was written (this wasn't written generically, but that isn't that important to the Task):

<syntaxhighlight lang=crystal>struct Church # can't be generic!

<syntaxhighlight lang="crystal">struct Church # can't be generic!

getter church : (Church -> Church) | Int32

def initialize(@church) end

Line 597:

Line 592:

=={{header|Elm}}==

Line 603:

Line 597:

<syntaxhighlight lang=elm>module Main exposing ( main )

<syntaxhighlight lang="elm">module Main exposing ( main )

import Html exposing ( Html, text )

Line 648:

Line 642:

<syntaxhighlight lang=elm>module Main exposing (main)

<syntaxhighlight lang="elm">module Main exposing (main)

import Html exposing (text)

Line 734:

Line 728:

The "churchToInt" function works by applying an integer successor function which takes an "arity zero" value and returns an "arity zero" containing that value plus one, then applying an "arity zero" wrapped integer value of zero to the resulting Church value; the result of that is unwrapped to result in the desired integer returned value. The idea of using "arity zero" values as function values is borrowed from Haskell, which wraps all values as data types including integers, etc. (all other than primitive values are thus "lifted"), which allows them to be used as functions. Since Haskell has Type Classes which F# and Elm do not, this is not so obvious in Haskell code which is able to treat values such as "lifted" integers as functions automatically, and thus apply the same Type Class functions to them as to regular (also "lifted") functions. Here in the F# code, the necessary functions that would normally be part of the Functor and Applicative Type Classes as applied to Functions in Haskell are supplied here to work with the Discriminated Union/custom type wrapping of this Function idea.

=={{header|Erlang}}==

<syntaxhighlight lang=erlang>-module(church).

<syntaxhighlight lang="erlang">-module(church).

-export([main/1, zero/1]).

zero(_) -> fun(F) -> F end.

Line 765:

Line 758:

64

</pre>

=={{header|F_Sharp|F#}}==

The following code uses the usual F# recommended work around to implement Haskell's "RankNTypes" so that the Church functions can represent functions of any Kind rank by using an abstract Interface type to represent it and create and instantiate a new type for every invocation of the wrapped function as required to implement this more complete set of Church functions, especially subtraction and division:

<syntaxhighlight lang=fsharp>type IChurch =

<syntaxhighlight lang="fsharp">type IChurch =

abstract Apply : ('a -> 'a) -> ('a -> 'a)

Line 831:

Line 823:

The following code uses F#'s Discriminated Unions to express the multi-ranked function Kinds that work like C# delegates; this code still uses side effects to convert the resulting Church Numerals, which is a facility that F# offers so we may as well use it since it is easily expressed:

<syntaxhighlight lang=fsharp>// types...

<syntaxhighlight lang="fsharp">// types...

type Church = Church of (Church -> Church)

let applyChurch (Church chf) charg = chf charg

Line 897:

Line 889:

One can achieve functional purity (without side effects) within the "RankNTypes" functions defined using the recursive Discriminated Unions as per the above code by including a tag of the "arity zero" case which just wraps a value. The following code uses that to be able to convert from Church Numerals to integers without using side effects:

<syntaxhighlight lang=fsharp>#nowarn "25" // eliminate incomplete pattern match warning

<syntaxhighlight lang="fsharp">#nowarn "25" // eliminate incomplete pattern match warning

// types...

Line 964:

Line 956:

The "churchToInt" function works by applying an integer successor function which takes an "arity zero" value and returns an "arity zero" containing that value plus one, then applying an "arity zero" wrapped integer value of zero to the resulting Church value; the result of that is unwrapped to result in the desired integer returned value. The idea of using "arity zero" values as function values is borrowed from Haskell, which wraps all values as data types including integers, etc. (all other than primitive values are thus "lifted"), which allows them to be used as functions. Since Haskell has Type Classes which F# does not, this is not so obvious in Haskell code which is able to treat values such as "lifted" integers as functions automatically, and thus apply the same Type Class functions to them as to regular (also "lifted") functions. Here in the F# code, the necessary functions that would normally be part of the Functor and Applicative Type Classes as applied to Functions in Haskell are supplied here to work with the Discriminated Union wrapping of this Function idea.

=={{header|Fōrmulæ}}==

Line 972:

Line 963:

In '''[https://formulae.org/?example=Church_numerals this]''' page you can see the program(s) related to this task and their results.

=={{header|Go}}==

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import "fmt"

Line 1,063:

Line 1,053:

5 -> five -> 5

</pre>

=={{header|Groovy}}==

<syntaxhighlight lang=~~Groovy~~>class ChurchNumerals {

<syntaxhighlight lang="groovy">class ChurchNumerals {

static void main(args) {

Line 1,112:

Line 1,101:

4 ^ 3 = 64

</pre>

=={{header|Haskell}}==

The following code implements the more complex Church functions using `unsafeCoerce` to avoid non-decidable infinite types:

<syntaxhighlight lang=haskell>import Unsafe.Coerce ( unsafeCoerce )

<syntaxhighlight lang="haskell">import Unsafe.Coerce ( unsafeCoerce )

type Church a = (a -> a) -> a -> a

Line 1,192:

Line 1,180:

The following code uses a wrapper `newtype` and the "RankNTypes" GHC Haskell extension to avoid the requirement for the unsafe coercion used above:

<syntaxhighlight lang=haskell>{-# LANGUAGE RankNTypes #-}

<syntaxhighlight lang="haskell">{-# LANGUAGE RankNTypes #-}

newtype Church = Church { unChurch :: forall a. (a -> a) -> a -> a }

Line 1,261:

Line 1,249:

Note that Haskell has directly recursive functions so the y-Combinator is not used to implement recursion in the Church division function.

=={{header|J}}==

Implementation:

<syntaxhighlight lang=J>chget=: {{(0;1;1;1) {:: y}}

<syntaxhighlight lang="j">chget=: {{(0;1;1;1) {:: y}}

chset=: {{

Line 1,295:

Line 1,282:

Task example:

<syntaxhighlight lang=J>three=: chNext^:3 ch0''

<syntaxhighlight lang="j">three=: chNext^:3 ch0''

four=: chNext^:4 ch0''

sixtyfour=: four chExp three

Line 1,313:

Line 1,300:

Illustration of the difference between a church numeral and the represented functions:

three apply 0

3

Line 1,328:

Line 1,315:

It's perhaps worth noting that J supports repeated negative applications of invertible functions:

<syntaxhighlight lang=J> four=: 4 chset ch0 +:`''

<syntaxhighlight lang="j"> four=: 4 chset ch0 +:`''

four apply 10

160

Line 1,337:

Line 1,324:

(sixtyfour chSub three chExp 4 chset ch0 5x&*`'') apply 10x^20

131072000</syntaxhighlight>

=={{header|Java}}==

<syntaxhighlight lang=java>package lvijay;

<syntaxhighlight lang="java">package lvijay;

import java.util.concurrent.atomic.AtomicInteger;

Line 1,416:

Line 1,402:

8=8

</pre>

=={{header|Javascript}}==

<syntaxhighlight lang=javascript>(() => {

<syntaxhighlight lang="javascript">(() => {

'use strict';

Line 1,531:

Line 1,516:

In jq, the Church encoding of the natural number $m as per the definition of this task would

be church(f; $x; $m) defined as:

<syntaxhighlight lang=jq>def church(f; $x; $m):

<syntaxhighlight lang="jq">def church(f; $x; $m):

if $m == 0 then .

elif $m == 1 then $x|f

Line 1,541:

Line 1,526:

However, since jq functions are filters,

the natural definition would be:

<syntaxhighlight lang=jq>def church(f; $m):

<syntaxhighlight lang="jq">def church(f; $m):

if $m < 0 then error("church is not defined on negative integers")

elif $m == 0 then .

Line 1,552:

Line 1,537:

the tasks that assume such functionality cannot be

directly implemented in jq.

=={{header|Julia}}==

We could overload the Base operators, but that is not needed here.

id(x) = x -> x

zero() = x -> id(x)

Line 1,585:

Line 1,569:

===Extended Church Functions in Julia===

<syntaxhighlight lang=julia>id = x -> x

<syntaxhighlight lang="julia">id = x -> x

always(f) = d -> f

struct Church # used for "infinite" Church type resolution

Line 1,644:

Line 1,628:

Note that this is very slow due to that, although function paradigms can be written in Julia, Julia isn't very efficient at doing FP: This is because Julia has no type signatures for functions and must use reflection at run time when the types are variable as here (as to function kind ranks) for a slow down of about ten times as compared to statically known types. This is particularly noticeable for the division function where the depth of function nesting grows exponentially.

=={{header|Lambdatalk}}==

{def succ {lambda {:n :f :x} {:f {:n :f :x}}}}

{def add {lambda {:n :m :f :x} {{:n :f} {:m :f :x}}}}

Line 1,664:

Line 1,647:

4^3 = {church {power {four} {three}}} -> 64

</syntaxhighlight>

=={{header|Lua}}==

function churchZero()

return function(x) return x end

Line 1,725:

Line 1,707:

'three' ^ 'four' = 81

'four' ^ 'three' = 64</pre>

=={{header|Nim}}==

===Macros and Pointers===

Using type erasure, pure functions, and impenetrably terse syntax to keep to the spirit of the untyped lambda calculus:

<syntaxhighlight lang=nim>import macros, sugar

<syntaxhighlight lang="nim">import macros, sugar

type

Fn = proc(p: pointer): pointer{.noSideEffect.}

Line 1,782:

Line 1,763:

===All closures and a union for type-punning===

Everything is an anonymous function, we dereference with a closure instead of a pointer,and the type-casting is hidden behind a union instead of behind a macro; the following code implements more extended Church functions such as Church subtraction and division than the task requires:

<syntaxhighlight lang=nim>import sugar

<syntaxhighlight lang="nim">import sugar

type # use a thunk closure as a data type...

Line 1,862:

Line 1,843:

Although Nim is by no means a functional language, we can implement this without using type erasure or raw type casting/"punning" by using object variants to represent what the Haskell/OCaml languages do with "forall RankNTypes" so that one wrapper represents functions nested to any Kind rank and also the actual value (int in this case). Generic types don't work so well here as the generic type must be known when instantiated in Nim, so we can't generate an object of a generic type from an int. However, what does work means that casting/"punning" isn't necessary while still being able to evaluate the Church Numeral representations to values without using side effects, as per the following code:

<syntaxhighlight lang=nim>import sugar

<syntaxhighlight lang="nim">import sugar

type

Line 1,956:

Line 1,937:

The "churchToInt" function works by applying an integer successor function which takes an "arity zero" value and returns an "arity zero" containing that value plus one, then applying an "arity zero" wrapped integer value of zero to the resulting Church value; the result of that is unwrapped to result in the desired integer returned value. The idea of using "arity zero" values as function values is borrowed from Haskell, which wraps all values as data types including integers, etc. (all other than primitive values are thus "lifted"), which allows them to be used as functions. Since Haskell has Type Classes which Nim does not (at least yet), this is not so obvious in Haskell code which is able to treat values such as "lifted" integers as functions automatically, and thus apply the same Type Class functions to them as to regular (also "lifted") functions. Here in the F# code, the necessary functions that would normally be part of the Functor and Applicative Type Classes as applied to Functions in Haskell are supplied here to work with the object variant wrapping of this Function idea.

=={{header|OCaml}}==

Original version by '''[http://rosettacode.org/wiki/User:Vanyamil User:Vanyamil]'''.

The extended Church functions as per the "RankNTypes" Haskell version have been added...

<syntaxhighlight lang=~~OCaml~~>(* Using type as suggested in https://stackoverflow.com/questions/43426709/does-ocamls-type-system-prevent-it-from-modeling-church-numerals

<syntaxhighlight lang="ocaml">(* Using type as suggested in https://stackoverflow.com/questions/43426709/does-ocamls-type-system-prevent-it-from-modeling-church-numerals

This is an explicitly polymorphic type : it says that f must be of type ('a -> 'a) -> 'a -> 'a for any possible a "at same time".

*)

Line 2,067:

Line 2,047:

=={{header|Octave}}==

zero = @(f) @(x) x;

succ = @(n) @(f) @(x) f(n(f)(x));

Line 2,098:

Line 2,077:

7 12 81 64</pre>

=={{header|Perl}}==

<syntaxhighlight lang=perl>use 5.020;

<syntaxhighlight lang="perl">use 5.020;

use feature qw<signatures>;

no warnings qw<experimental::signatures>;

Line 2,141:

Line 2,119:

=={{header|Phix}}==

with javascript_semantics

Line 2,245:

Line 2,222:

5 -> five -> 5

</pre>

=={{header|PHP}}==

<syntaxhighlight lang=php><?php

<syntaxhighlight lang="php"><?php

$zero = function($f) { return function ($x) { return $x; }; };

Line 2,309:

Line 2,285:

64

</pre>

=={{header|Prolog}}==

Prolog terms can be used to represent church numerals.

<syntaxhighlight lang=prolog>church_zero(z).

<syntaxhighlight lang="prolog">church_zero(z).

church_successor(Z, c(Z)).

Line 2,357:

Line 2,332:

7 12 81 64

</pre>

=={{header|Python}}==

<syntaxhighlight lang=python>'''Church numerals'''

<syntaxhighlight lang="python">'''Church numerals'''

from itertools import repeat

Line 2,494:

Line 2,468:

=={{header|Quackery}}==

Quackery is a postfix language, so these are Reverse Polish Church numerals.

<syntaxhighlight lang=~~Quackery~~> [ this nested ] is zero ( --> cn )

<syntaxhighlight lang="quackery"> [ this nested ] is zero ( --> cn )

[ this nested join ] is succ ( cn --> cn )

Line 2,547:

Line 2,520:

R was inspired by Scheme and this task offers little room for creativity. As a consequence, our solution will inevitably look a lot like Racket's. Therefore, we have made this easy and just translated their solution. Alternative implementations, denoted by asterisks in their code, are separated out and denoted by "[...]Alt".

<syntaxhighlight lang=rsplus>zero <- function(f) {function(x) x}

<syntaxhighlight lang="rsplus">zero <- function(f) {function(x) x}

succ <- function(n) {function(f) {function(x) f(n(f)(x))}}

add <- function(n) {function(m) {function(f) {function(x) m(f)(n(f)(x))}}}

Line 2,575:

Line 2,548:

[1] 64</pre>

Alternative versions (Racket's, again):

<syntaxhighlight lang=rsplus>zeroAlt <- function(x) identity

<syntaxhighlight lang="rsplus">zeroAlt <- function(x) identity

one <- function(f) f #Not actually requested by the task and only used to define Alt functions, so placed here.

oneAlt <- identity

Line 2,584:

Line 2,557:

exptAlt <- function(n) {function(m) m(mult(n))(one)}</syntaxhighlight>

Extra tests - mostly for the alt versions - not present in the Racket solution:

<syntaxhighlight lang=rsplus>churchToNat(addAlt(three)(four))

<syntaxhighlight lang="rsplus">churchToNat(addAlt(three)(four))

churchToNat(multAlt(three)(four))

churchToNat(exptAlt(three)(four))

Line 2,614:

Line 2,587:

===Extended Church Functions in R===

<syntaxhighlight lang=rsplus>const <- function(f) {function(d) f}

<syntaxhighlight lang="rsplus">const <- function(f) {function(d) f}

zero <- const(identity)

one <- identity

Line 2,659:

Line 2,632:

[1] 3

[1] 4</pre>

=={{header|Racket}}==

<syntaxhighlight lang=racket>#lang racket

<syntaxhighlight lang="racket">#lang racket

(define zero (λ (f) (λ (x) x)))

Line 2,706:

Line 2,678:

64

</pre>

=={{header|Raku}}==

(formerly Perl 6)

===Traditional subs and sigils===

<syntaxhighlight lang=raku line>constant $zero = sub (Code $f) {

<syntaxhighlight lang="raku" line>constant $zero = sub (Code $f) {

sub ( $x) { $x }}

Line 2,753:

Line 2,724:

===Arrow subs without sigils===

<syntaxhighlight lang=raku line>my \zero = -> \f { -> \x { x }}

<syntaxhighlight lang="raku" line>my \zero = -> \f { -> \x { x }}

my \succ = -> \n { -> \f { -> \x { f.(n.(f)(x)) }}}

my \add = -> \n { -> \m { -> \f { -> \x { m.(f)(n.(f)(x)) }}}}

Line 2,773:

Line 2,744:

=={{header|Ruby}}==

Line 2,780:

Line 2,750:

===Traditional methods===

<syntaxhighlight lang=ruby>def zero(f)

<syntaxhighlight lang="ruby">def zero(f)

return lambda {|x| x}

end

Line 2,832:

Line 2,802:

===Procs all the way down===

<syntaxhighlight lang=ruby>Zero = proc { |f| proc { |x| x } }

<syntaxhighlight lang="ruby">Zero = proc { |f| proc { |x| x } }

Succ = proc { |n| proc { |f| proc { |x| f[n[f][x]] } } }

Line 2,866:

Line 2,836:

81

64</pre>

=={{header|Rust}}==

<syntaxhighlight lang=rust>use std::rc::Rc;

<syntaxhighlight lang="rust">use std::rc::Rc;

use std::ops::{Add, Mul};

Line 2,973:

Line 2,942:

three ^ four = 81

four ^ three = 64</pre>

=={{header|Standard ML}}==

val demo = fn () =>

let

Line 2,998:

Line 2,966:

</syntaxhighlight>

output

demo ();

7

Line 3,005:

Line 2,973:

81

</syntaxhighlight>

=={{header|Swift}}==

<syntaxhighlight lang=swift>func succ<A, B, C>(_ n: @escaping (@escaping (A) -> B) -> (C) -> A) -> (@escaping (A) -> B) -> (C) -> B {

<syntaxhighlight lang="swift">func succ<A, B, C>(_ n: @escaping (@escaping (A) -> B) -> (C) -> A) -> (@escaping (A) -> B) -> (C) -> B {

return {f in

return {x in

Line 3,086:

Line 3,053:

=={{header|Tailspin}}==

In Tailspin functions can be used as parameters but currently not as values, so they need to be wrapped in processor (object) instances.

===Using lambda calculus compositions===

processor ChurchZero

templates apply&{f:}

Line 3,177:

Line 3,143:

===Using basic mathematical definitions===

Less efficient but prettier functions can be gotten by just implementing Add as a repeated application of Successor, Multiply as a repeated application of Add and Power as a repeated application of Multiply

processor ChurchZero

templates apply&{f:}

Line 3,244:

Line 3,210:

64

</pre>

=={{header|Wren}}==

<syntaxhighlight lang=ecmascript>class Church {

<syntaxhighlight lang="ecmascript">class Church {

static zero { Fn.new { Fn.new { |x| x } } }

Line 3,286:

Line 3,251:

four ^ three -> 64

</pre>

=={{header|zkl}}==

<syntaxhighlight lang=zkl>class Church{ // kinda heavy, just an int + fcn churchAdd(ca,cb) would also work

<syntaxhighlight lang="zkl">class Church{ // kinda heavy, just an int + fcn churchAdd(ca,cb) would also work

fcn init(N){ var n=N; } // Church Zero is Church(0)

fcn toInt(f,x){ do(n){ x=f(x) } x } // c(3)(f,x) --> f(f(f(x)))

Line 3,297:

Line 3,261:

fcn toString{ String("Church(",n,")") }

}</syntaxhighlight>

<syntaxhighlight lang=zkl>c3,c4 := Church(3),c3.succ();

<syntaxhighlight lang="zkl">c3,c4 := Church(3),c3.succ();

f,x := Op("+",1),0;

println("f=",f,", x=",x);

Line 3,318:

Line 3,282:

OK, that was the easy sleazy cheat around way to do it.

The wad of nested functions way is as follows:

<syntaxhighlight lang=zkl>fcn churchZero{ return(fcn(x){ x }) } // or fcn churchZero{ self.fcn.idFcn }

<syntaxhighlight lang="zkl">fcn churchZero{ return(fcn(x){ x }) } // or fcn churchZero{ self.fcn.idFcn }

fcn churchSucc(c){ return('wrap(f){ return('wrap(x){ f(c(f)(x)) }) }) }

fcn churchAdd(c1,c2){ return('wrap(f){ return('wrap(x){ c1(f)(c2(f)(x)) }) }) }

Line 3,326:

Line 3,290:

fcn churchFromInt(n){ c:=churchZero; do(n){ c=churchSucc(c) } c }

//fcn churchFromInt(n){ (0).reduce(n,churchSucc,churchZero) } // what ever</syntaxhighlight>

<syntaxhighlight lang=zkl>c3,c4 := churchFromInt(3),churchSucc(c3);

<syntaxhighlight lang="zkl">c3,c4 := churchFromInt(3),churchSucc(c3);

f,x := Op("+",1),0; // x>=0, ie natural number

T(c3,c4,churchAdd(c3,c4),churchMul(c3,c4),churchPow(c4,c3),churchPow(c3,c4))