Church numerals: Difference between revisions
Added FreeBASIC
imported>Rowsety Moid |
(Added FreeBASIC) |
||
| (4 intermediate revisions by 4 users not shown) | |||
Line 794:
===Further Church functions===
The predecessor of a Church numeral ''n'' has to call the function it's given one fewer times than ''n'' would. How can that be arranged? The trick used here, based on the [[wp:Church_encoding#Derivation_of_predecessor_function|derivation of the predecessor function]] on the Wikipedia [[wp:Church_encoding|Church encoding]] page, is that the predecessor doesn't call ''f'' directly; instead ''f'' is given to a ''container function'' that can call ''f'' or not.
<code>Value</code> returns a container that calls the function; <code>const</code> is a container that doesn't. <code>Inc</code>, given a container, calls the container on ''f'' and returns the result in a calling container. The predecessor uses ''n'' to call <code>inc</code> ''n'' times but gives it a non-calling container (<code>const</code>) initially. So ''f'' isn't called the first time ''n'' calls <code>inc</code> but is called each time thereafter. This process therefore calls ''f'' ''n-1'' times.
Line 1,372:
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|FreeBASIC}}==
FreeBASIC does not directly support higher-order functions, but we can achieve something similar using pointers to functions or subroutines.
<syntaxhighlight lang="vbnet">Type church
' eg {r_add,1,{a,b}}
op As Integer
n As Integer
x(1 To 2) As Integer
End Type
Dim Shared As church zero = Type<church>(1, 0, {0, 1})
Function succ(c As church) As church
' eg {r_add,1,{a,b}} => {r_add,2,{a,b}} aka a+b -> a+b+b
c.n += 1
Return c
End Function
' three normal integer-handling routines...
Function sum(n As Integer, a As Integer, b As Integer) As Integer
For i As Integer = 1 To n
a += b
Next i
Return a
End Function
Function mul(n As Integer, a As Integer, b As Integer) As Integer
For i As Integer = 1 To n
a *= b
Next i
Return a
End Function
Function pow(n As Integer, a As Integer, b As Integer) As Integer
For i As Integer = 1 To n
a = a ^ b
Next i
Return a
End Function
' ...and three church constructors to match
' (no maths here, just pure static data)
Function churchSum(c As church, d As church) As church
Dim res As church
res.op = 1 ' 1 for add
res.n = 1
res.x(1) = c.n
res.x(2) = d.n
Return res
End Function
Function churchMul(c As church, d As church) As church
Dim res As church
res.op = 2 ' 2 for mul
res.n = 1
res.x(1) = c.n
res.x(2) = d.n
Return res
End Function
Function churchPow(c As church, d As church) As church
Dim res As church
res.op = 3 ' 3 for pow
res.n = 1
res.x(1) = c.n
res.x(2) = d.n
Return res
End Function
Function churchToNum(c As church) As Integer
' note this is where the bulk of any processing happens
Select Case c.op
Case 1
Return sum(c.n, c.x(1), c.x(2))
Case 2
Return mul(c.n, c.x(1), c.x(2))
Case 3
Return pow(c.n, c.x(1), c.x(2))
End Select
End Function
Function numToChurch(i As Integer) As church
Return Iif(i = 0, zero, succ(numToChurch(i - 1)))
End Function
Dim As church three = succ(succ(succ(zero)))
Dim As church four = succ(three)
Print "three -> "; churchToNum(three)
Print "four -> "; churchToNum(four)
Print "three + four -> "; churchToNum(churchSum(three, four))
Print "three * four -> "; churchToNum(churchMul(three, four))
Print "three ^ four -> "; churchToNum(churchPow(three, four))
Print "four ^ three -> "; churchToNum(churchPow(four, three))
Print "5 -> five -> "; churchToNum(numToChurch(5))
Sleep</syntaxhighlight>
{{out}}
<pre>Same as Phix entry.</pre>
=={{header|Fōrmulæ}}==
Line 1,576 ⟶ 1,675:
5 -> five -> 5
</pre>
===Go (Generics)===
<syntaxhighlight lang="go">package main
import "fmt"
type Church func(Church) Church
func id[X any](x X) X {
return x
}
func compose[X any, Y any, Z any](f func(Y) Z, g func(X) Y) func(X) Z {
return func(x X) Z {
return f(g(x))
}
}
func zero() Church {
return func(f Church) Church {
return id[Church]
}
}
func one() Church {
return id[Church]
}
func succ(n Church) Church {
return func(f Church) Church {
return compose(f, n(f))
}
}
func plus(m, n Church) Church {
return func(f Church) Church {
return compose(m(f), n(f))
}
}
func mult(m, n Church) Church {
return compose(m, n)
}
func exp(m, n Church) Church {
return n(m)
}
func toInt(x Church) int {
counter := 0
fCounter := func(f Church) Church {
counter++
return f
}
x(fCounter)(id[Church])
return counter
}
func toStr(x Church) string {
counter := ""
fCounter := func(f Church) Church {
counter += "|"
return f
}
x(fCounter)(id[Church])
return counter
}
func main() {
fmt.Println("zero =", toInt(zero()))
one := one()
fmt.Println("one =", toInt(one))
two := succ(succ(zero()))
fmt.Println("two =", toInt(two))
three := plus(one, two)
fmt.Println("three =", toInt(three))
four := mult(two, two)
fmt.Println("four =", toInt(four))
eight := exp(two, three)
fmt.Println("eight =", toInt(eight))
fmt.Println("toStr(four) =", toStr(four))
}
</syntaxhighlight>
{{out}}
<pre>
zero = 0
one = 1
two = 2
three = 3
four = 4
eight = 8
4 ^ 3 = 64
toStr(four) = ||||
</pre>
=={{header|Groovy}}==
<syntaxhighlight lang="groovy">class ChurchNumerals {
Line 3,512 ⟶ 3,715:
three ^ four = 81
four ^ three = 64</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
object Church {
trait ChurchNum extends (ChurchNum => ChurchNum)
def zero: ChurchNum = f => x => x
def next(n: ChurchNum): ChurchNum = f => x => f(n(f)(x))
def plus(a: ChurchNum)(b: ChurchNum): ChurchNum = f => x => b(f)(a(f)(x))
def mult(a: ChurchNum)(b: ChurchNum): ChurchNum = f => x => b(a(f))(x)
def pow(m: ChurchNum)(n: ChurchNum): ChurchNum = n(m)
def toChurchNum(n: Int): ChurchNum = if (n <= 0) zero else next(toChurchNum(n - 1))
def toInt(c: ChurchNum): Int = {
var counter = 0
val funCounter: ChurchNum = f => { counter += 1; f }
plus(zero)(c)(funCounter)(x => x)
counter
}
def main(args: Array[String]): Unit = {
val zero = Church.zero
val three = next(next(next(zero)))
val four = next(next(next(next(zero))))
println(s"3+4=${toInt(plus(three)(four))}") // prints 7
println(s"4+3=${toInt(plus(four)(three))}") // prints 7
println(s"3*4=${toInt(mult(three)(four))}") // prints 12
println(s"4*3=${toInt(mult(four)(three))}") // prints 12
// exponentiation. note the reversed order!
println(s"3^4=${toInt(pow(four)(three))}") // prints 81
println(s"4^3=${toInt(pow(three)(four))}") // prints 64
println(s" 8=${toInt(toChurchNum(8))}") // prints 8
}
}
</syntaxhighlight>
{{out}}
<pre>
3+4=7
4+3=7
3*4=12
4*3=12
3^4=64
4^3=81
8=8
</pre>
=={{header|Standard ML}}==
<syntaxhighlight lang="standard ml">
Line 3,848 ⟶ 4,108:
=={{header|Wren}}==
{{trans|Lua}}
<syntaxhighlight lang="
static zero { Fn.new { Fn.new { |x| x } } }
Line 3,887 ⟶ 4,147:
four ^ three -> 64
</pre>
=={{header|zkl}}==
<syntaxhighlight lang="zkl">class Church{ // kinda heavy, just an int + fcn churchAdd(ca,cb) would also work
| |||