Lambda calculus

Lambda calculus

Mathematical Functions:

- F(x) = x + 1

- G(x) = x + 2

- H(x) = x + 3

The composition of these functions is expressed as (F(G(H(x)))) and results in (x + 6). This indicates that the H function is first applied to the value (x), followed by the application of the G function to this result, and finally, the F function is applied to the last obtained value.

Lambda Calculus Notation:

In lambda calculus, these functions and their composition are expressed as follows:

- (F = λ x. x + 1)

- (G = λ x. x + 2)

-(H = λ x. x + 3)

The composition of the functions is:

F(G(H(x))) = (λ x. x + 1)((λ x. x + 2)((λ x. x + 3)(x)))

Additionally, a more general expression in lambda calculus for this composition is provided:

λ f.λ g.λ h.λ x. f(g(h(x)))

This general formulation can be directly applied to our example:

λ f.λ g.λ h.λ x. f(g(h(x))) = λ x. (λ x. x + 1)((λ x. x + 2)((λ x. x + 3)(x)))

This detailed expression illustrates how each function (f), (g), and (h) is sequentially applied to the result of the previous one in the composition, resulting in a new function that applies to (x). This structure exemplifies the use of higher-order functions in lambda calculus, allowing for a concise and powerful representation of function composition.

Programmatically we can express this formulation:

val f: (Int) -> Int = { x -> x + 1 }

val g: (Int) -> Int = { x -> x + 2 }

val h: (Int) -> Int = { x -> x + 3 }

val composition: (Int) -> Int = { x -> f(g(h(x))) }

or:

fun f(x: Int): Int = x + 1

fun g(x: Int): Int = x + 2

fun h(x: Int): Int = x + 3

fun composeFunctions(f: (Int) -> Int, g: (Int) -> Int, h: (Int) -> Int): (Int) -> Int {

  return { x: Int -> f(g(h(x))) }

}

fun main() {

  // Define three simple functions using function declarations

  fun f(x: Int): Int = x + 1

  fun g(x: Int): Int = x + 2

  fun h(x: Int): Int = x + 3

  // Higher-order function that composes three functions into one

  fun composeFunctions(f: (Int) -> Int, g: (Int) -> Int, h: (Int) -> Int): (Int) -> Int {

    return { x: Int -> f(g(h(x))) } // The composition order is h, then g, then f

  }

  // Using the higher-order function to create a composed function from f, g, and h

  val composed = composeFunctions(::f, ::g, ::h)

  // Alternatively, define the same functions as lambda expressions

  val lambdaF: (Int) -> Int = { it + 1 }

  val lambdaG: (Int) -> Int = { it + 2 }

  val lambdaH: (Int) -> Int = { it + 3 }

  // Directly compose the lambda expressions into a new lambda

  val composition: (Int) -> Int = { x -> lambdaF(lambdaG(lambdaH(x))) }

  // Apply the composed lambda to a value and print the result

  val x = 5

  val result = composition(x)

  println("Result: $result") // Shows how ((5 + 3) + 2) + 1 = 11, illustrating function composition

  // Apply the composed function (from composeFunctions) to a different value and print the result

  println("Composed function applied to 3: ${composed(3)}") // Demonstrates applying the composed function, expecting ((3 + 3) + 2) + 1 = 9

}

for more information:

https://en.wikipedia.org/wiki/Lambda_calculus#:~:text=Lambda%20calculus%20(also%20written%20as,to%20simulate%20any%20Turing%20machine.