Functional Challenge 3

[)roi(]

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
6,282
Reaction score
405
Location
ッ
Introduction
This functional challenge thread is intended to serve two goals:
  • Challenge MyBB programmers to a "function" oriented programming problem.
  • Provide a beginner friendly introduction to one of the key building blocks of programming: Functions, and to hopefully share some interesting ways in which these can be leveraged in your code.

Programming Challenge
Create a function called "recursive" that has a single parameter, a closure (lambda), that can be used to create recursive function variables for many recurrence relationship computations, for example:

Usage example 1: Factorial of n
5! = 5 * 4 * 3 * 2 * 1 = 120
PHP: 
let factorial = recursive({ recurse in
  { n in n > 0 ? n * recurse(n - 1) : 1 }
})

print(factorial(5)) 

\\\ 120

[table="width: 500, class: outer_border, align: center"]
[tr]
[td]Note: This part of the above recursive function is the parameter value i.e. a closure (lambda) to calculate the n'th factorial
PHP: 
{ recurse in
  { n in n > 0 ? n * recurse(n - 1) : 1 }
}
Which is essentially a ternary (if statement) that recursively calls the outer closure, resulting in the following composition through the recursion:
PHP: 
5 * (5 - 1) * (4 - 1) * (3 - 1) * (2 - 1)
[/td]
[/tr]
[/table]

Please use the language you are most comfortable in to submit your solution. Ps. please also go ahead and submit a OOP styled solutions if you're more comfortable working with class types. Only proviso is that is it's flexible enough to solve all 3 problems without rewriting the
body or method signature.

Usage example 2: n'th Fibonacci number
12th Fibonacci = 89
PHP: 
typealias F3 = (x: Int, y: Int, n: Int)
let fibonacci = recursive({ (recurse: escaping (F3) -> F3) in
  { (e: F3) in e.n > 2 ? recurse((e.y, e.x + e.y, e.n - 1)) : (e.x, e.y, e.n) }
})

print(fibonacci(12)) 

\\\ 89

Usage example 3: first n'th Even numbers as an Array
Array of the 4 positive Integer numbers above zero = [8, 6, 4, 2]
PHP: 
typealias E2 = (n: Int, v: [Int])
let even = recursive({
  (recurse: escaping (E2) -> E2) in {
    (e: E2) in e.n > 0 ? (e.n, e.v + recurse((e.n - 1, [2 * e.n])).v) : (e.n, e.v)
  }
})

print(even((40, [])).1) \\ [80, 78, 76, 74, 72, 70, 68, 66, 64, 62, 60, 58, 56, 54, 52, 50, 48, 46, 44, 42, 40, 38, 36, 34, 32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2]

\\\ returns the first 40 even numbers as an array.

[table="width: 600, class: outer_border, align: center"]
[tr]
[td]Hint: The recursive function is a higher order function, meaning it takes a function ./ closure as it's single parameter; the recursion occurs naturally within the body of the function in that that the function calls itself during the computation of the closure.[/td]
[/tr]
[/table]


Second part scope
The second part of this thread is targeted to be beginner friendly and therefore I'm going to try to avoid making any assumptions. This part of the thread will cover areas like:
  • Define a function (and clarify how is it differs from a method)
  • Function Application
  • Function Composition
  • Higher order functions
  • What makes a function pure?
  • Side effects
  • Computing with effects
  • Composition with effects
  • Testing with effects.
  • Functional Operators (I will also show how this can be achieved with methods i.e. in the absence of operator overloading):
    • |> pipe forward (aka reverse application)
    • <| pipe backward (aka normal application)
    • >>> forward composition (occasionally this is also represented as >>): NB this is not bit shifting
    • <<< reverse composition (occasionally this is also represented as <<): NB this is not bit shifting
    • >=> fish operator (aka composition with effects)
 
Last edited:
Define a function

A function is a computation with input and output, for example:

A predicate function
... is a logic computation with a boolean output, for example determining if the Integer inout value is greater than zero.
Predicate Function.png
PHP: 
func greaterThanZero(_ value: Int) -> Bool {
  return value > 0
}

print(greaterThanZero(1)) // True

A unary function
... is a computation with a single argument, a typical example the increment function, which has a single Integer input to which it adds 1.
Unary Function.png
PHP: 
func increment(_ value: Int) -> Int {
  return value + 1
}

print(increment(1)) // 2

A binary function
... is a computation with two arguments, a typical example is the plus operator, which has two Integers as its arguments; added together, the output being the sum of the two.
Binary Function.png
PHP: 
func +(_ lhs: Int, rhs: Int) -> Int {
  return lhs + rhs
}

print(1 + 2) // 3

Naturally functions come in all shapes and sizes, and are certainly not limited to 1 or 2 input or output values.
 
Last edited:
Let's define two functions:

Increment
A function that takes an Int and returns an Int + 1:

Increment Function.png

PHP: 
func increment(_ value: Int) -> Int {
  return value + 1
}

To execute this computation, we call it and pass in a value:
PHP: 
increment(2) // 3

Square
A function that takes an Int and returns an Int multiplied by itself:

Square Function.png

PHP: 
func square(_ value: Int) -> Int {
  return value * value
}

Similarly to execute this computation, we call it and pass in a value:
PHP: 
square(2) // 4

Composition (nesting function calls)
We can nest these function calls with composition, for example incrementing and then squaring the result:

Composition of Increment & Square.png

PHP: 
square(increment(2)) // 9

Easy peasy; this basic concept of composition leans heavily on the OOP adage that we should "favour composition over inheritance", stemming largely from the brittleness of inheritance and its typical tight coupling between base and sub classes.

However even with this knowledge its rare to find codebases that are built from standalone functions, why?
One reason could stem from another OOP fundamental concept: "Encapsulation"; the idea of bundling related data and methods (computations) in a single OOP unit, the class.

Problem is that methods unlike functions are not typically built to enable composition; because of a reliance on shared (class) state i.e. hidden inputs and outputs. Whereas Functions like their mathematical counterparts strictly define inputs and outputs; a concept we call pure functions.

Let's for clarity review a simple class style construction of increment and square using encapsulation.
PHP: 
class Number: CustomStringConvertible {
  let value: Int
  
  init(_ value: Int) {
    self.value = value
  }
  
  var description: String { return "\(self.value)" }
  
  func increment() -> Number {
     return Number(self.value + 1)
  }
  
  func square() -> Number {
    return Number(self.value * self.value)
  }
}

Usage example:
PHP: 
Number(2).increment().square() // n.value == 9

Comparing the two (.dot chaining versus function composition)
PHP: 
square(increment(2)) // 9

Number(2).increment().square() // n.value == 9
If we compare the two we should clearly see that the .dot method chaining solution reads a little more naturally (left to right) in comparison with the (right to left) style of standard function composition.

This however isn't the end of this story; because we have some techniques that will allow us to turn the function composition into a left to right style, and on top of this what may not be apparent at the moment is the glaring limitation of the .dot method chaining solution. i.e. it breaks composition.

That'll be covered in the next post.
 
Function Application
The standard pattern (in many programming languages) for the application of an input value to a function tends to be right to left application of values to functions.

Pipe Forward.png
The above diagram is a representation of a function on the left hand side (lhs) and an input value on the right hand side (rhs), for example:

PHP: 
func increment(_ value: Int) -> Int {
  return value + 1
}
The increment function is a pattern match for the lhs of the above diagram; a function with a single input value that returns a single output value. The rhs represents the value being applied (or wrapped in brackets as input to the function on the lhs, for example:

PHP: 
increment(2)
Matching up with the diagram:
  • 2 is the rhs input value
  • increment is the lhs function

Composing function calls also follows right to left application, for example:
PHP: 
square(increment(2))
Result of increment is passed into square as it's input value. This default style of right to left function application can get quite messy, for example:
PHP: 
String(sqrt(Double(square(increment(2))))) // "3.0"

Perfect example where .dot method chaining is more elegant
PHP: 
Number(2).increment().square()
...but it's not perfect as the crud will will inevitably start showing when a required computation is not a feature of the encapsulating class, for example:
PHP: 
String(sqrt(Double(Number(2).increment().square()))
[table="width: 500, class: outer_border, align: center"]
[tr]
[td]Note:It simply isn't practical for every class unit to provide .dot method chaining for every eventuality.[/td]
[/tr]
[/table]

How we solve this in a more functional way will be shown in the next post.
 
Last edited:
So how do we invert the typical right to left function application?
Functional languages like F#, Haskell and others solve this with both different language semantics and operators. Naturally we can't change the language semantics of Java, Swift, Kotlin, and others but we can where supported, we can use either, or a combination of:
  • Custom Operator Overloading (e.g. Swift, Kotlin, Scala, ...)
  • Method extensions (e.g. C#, Swift, Kotlin, Scala, ...)
  • Functional Interfaces (e.g. Java)
To change the usage dynamics within our choice language.

Custom Operator Overloading
In F# the pipe forward operator |> is a central feature in how F# code is composed. In Haskell the similar operator is the ampersand & operator -- both of these are reverse function application operators, because they essentially invert the default way (right to left) of function application.

Pipe Forward.png

Swift doesn't have a reverse function application operator in its standard library, but we can add it:
PHP: 
infix operator |> // defines a new infix operator symbol

func |> (value: Int, fn: (Int) -> Int) -> Int {
  return fn(value)
}
In the above code, we have first defined a new infix operator symbol, then we implemented this as a function, where the lhs is the value and the rhs is a function that takes an Integer value and returns a Integer value. Internally the functional application follows the default right to left behaviour; whereas the |> operator has the function and values inverted in its signature.

Let's see this in use:
PHP: 
2 |> increment |> square // output is 9
We use this operator no differently to how we would use the + operator, except differently to the normal right to left function application, we start with our input value on the left and then chain our function computations together with our new pipe forward |> operator. Bonus points is we can leave out the brackets when the input from the left matches the signature of the receiving function on the right (This is btw referred to as a point-free style of coding).

Pipe forward chaining code is often styled as follows:
PHP: 
let result = 2
    |> increment
    |> square
The reason for this is that we can easily comment out any computation in a sequence of computations.

The above operator implementation is however limited to only Integer functions, what if we need to pipe our computations through a number of varying types; e.g. the more messy example from the previous post that use Double and String conversions?

This is where we lean on Generics
So let's rewrite the |> operator to work over any input and any output types.
PHP: 
public func |> <A, B>(a: A, fn: (A) -> B) -> B {
  return fn(a)
}
We have defined two generic types placeholders A and B; our value is of type A, and our function takes an A and returns a B. This allows us to support any input type to any output type e.g. Integer to String, ...


Ok so let's look at how this would transform this code:
PHP: 
String(sqrt(Double(square(increment(2))))) // "3.0"

It transforms to this... with our |> operator...
PHP: 
2 |> increment |> square |> Double.init |> sqrt |> String.init // "3.0"

...or we can stylise it more typically as follows:
PHP: 
let result = 2 
  |> increment 
  |> square 
  |> Double.init 
  |> sqrt 
  |> String.init
For String and Double, for the type conversion we have explicitly indicated that we want to call an initialiser method for this. This is the same as method references in Java, Scala or Kotlin, for example:

Code: 
System.out::println


How do we achieve this in a language that doesn't support custom operator overloading and/or infix functions (e.g. Java, C#), will be covered in the next post.
 
Last edited:
Pipe Forward Operator implementation in Java
I've decided to show how reverse function application can be implemented in Java; considering that it's one of the least easily adapted languages in general use. Point is to prove that these concepts can translate to almost any language.

In Java functions as a first class type was an after thought; so it's implementation requires a bit more plumbing to get it to work, primarily because we need to tie it in with Java's Functions Interfaces.

To start let's define a Functional interface for a unary function; 1 input to 1 output.
Code: 
[MENTION=235172]Fun[/MENTION]ctionalInterface
public interface Function1<A, B> {
  R apply(A arg0);

  default <C> Function1<A, C> andThen(Function1<B, C> after) {
    Objects.requireNonNull(after);
    return arg0 -> after.apply(apply(arg0));
  }
}
...because we're creating a .dot chaining method solution we need to pick method name that well describes the role of the pipe forward operator.

I have chosen to call it "andThen".

Next to make it easy to lift any existing function into this functional interface, I created a helper method to more easily lift and translate an existing Java method reference to our new functional interface.
PHP: 
public abstract static class Function {
  public static <A, B> Function1<A, B> of(Function1<A, B> f) {
    return f;
  }
}

Next let's redefine our two unary functions, and show how this all ties together:
PHP: 
public class PipeExample{
  static int increment(int value) {
    return value + 1;
  }

  static int square(int value) {
    return value * value;
  }

  public static void main(String[] args) {
     String result = Function.of(PipeExample::increment)
      .andThen(PipeExample::square)
      .andThen(Double::valueOf)
      .andThen(Math::sqrt)
      .andThen(String::valueOf)
      .apply(2);
    
    System.out.println(result); // 3.0
  }
}
In the above code you can see we have used Java's method references to nominate which methods to convert to our functional interface, and just like in Swift we do not need to provide brackets around our arguments i.e. we achieve point free code in Java with our custom pipe forward method ("andThen").

You should be able to achieve the same in the other JVM languages like Scala and Kotlin, but in the case of scala you would also be able to define the |> operator and in Kotlin you could choose to use its infix functions, which work similar to an operator.

[table="width: 600, class: outer_border, align: center"]
[tr]
[td]Note: The only major limitation that I have found with Scala and Kotlin's infix operators / functions is precedence i.e. the ability to define the compilers order of priority when these infix operators are used in conjunction with existing standard library operators or any other operators we define. The fall back as with everything is to wrap parts of the computation in brackets to prioritise 1 over the other,

In Swift we however have a very powerful fixity mechanism to control not only precedence, but also associativity (left or right), for example in Swift we can define a precedence group and then link this group to our operator:

PHP: 
precedencegroup infixl0 {
  associativity: left
  higherThan: AssignmentPrecedence
}

infix operator |>: infixl0
This not only specifies that our operator is left associative, but also specifies that our operator's precedence is higher than variable assignment precedence i.e. our computation is computed before assignment. Similarly with other operators we can define precedence groups that set any operator higher and / or lower than another precedence group i.e. we can have a very exact control over what takes precedence.

The outcome for Swift code is that we don't have to use as much brackets as either Scala or Kotlin does.
[/td]
[/tr]
[/table]


Ps. Just ask if you'd like advice on how to achieve this in another language.

FYI The next post will focus on composition and higher order functions.
 
Last edited:
No attempts on the recursive high order function? ... is there anyone who wants to still attempt this?

hint: inner recursion can easily be attained with the new inner function features (function within a function); closures can achieve something similar.

I'll post a solution on Friday if nobody is "brave" enough to attempt it.
 
Last edited:
Recursion Solution:
In mathematics and computer science, a higher-order function is a function that does at least one of the following:
  • takes one or more functions as arguments (i.e. procedural parameters),
  • returns a function as its result.
[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Flexibility to inject an as yet undefined computation:

This Increases the modularity and extension of these type of functions in a concept similar to IoC (inversion of control) and dependency injection.[/td]
[/tr]
[/table]

Creating a higher-order function that enables recursive closures to be injected
The design of this higher-order function using two closure allows us to achieve recursion without the typical two step assignment dance that usually accompanies recursive computation.

We achieve this by splitting the function parameter into two parts:
  • A parameter function, a unary function from generic type A to B
  • A result function, a unary function also from generic type A to B
Essentially we wrapped a function within a function (or... similarly a closure within closure)


Let's define this in Swift
For clarity sake I am going to use type aliases to delineate one generic unary function from the other by giving each a type alias that more appropriately describes its purpose.

PHP: 
public typealias ParameterFunction<A, B> = (A) -> B
public typealias ResultFunction<A, B> = (A) -> B
public typealias ParameterToResult<A, B> = (escaping ParameterFunction<A, B>) -> ResultFunction<A, B>
As you can see the ParameterFunction type alias defines a generic unary function from A to B; these generic placeholder variables can be of any type, for example:
  • (String) -> Int
The ResultFunction type alias has the same unary type signature, because essentially it's the inner function that recursively calls back to the parameter with update values. e.g. subtracting one from our recursive loop variable, etc.

The 3rd type alias is simply a conjoining of the ParameterFunction and the ResultFunction i.e. the ParameterFunction returns a ResultFunction.

[table="width: 60%, class: outer_border, align: center"]
[tr]
[td]Recursion is achieved when the ResultFunction calls back to the ParameterFunction[/td]
[/tr]
[/table]
Let's now define the function
PHP: 
public func recursive<A, B>(_ param2result: escaping ParameterToResult<A,B>) -> ResultFunction<A, B> {
  return { parameterFunction in param2result(recursive(param2result))(parameterFunction) }
}
...and here's an alternative version without using the type aliases:
PHP: 
public func recursive <A, B>(_ f: escaping (escaping (A) -> B) -> (A) -> B) -> (A) -> B {
  return { f(recursive(f))($0) }
}
You should hopefully agree the type alias version is a bit easier to understand re how it works.


Finally let's re-look at a use case example:
PHP: 
let factorial = recursive({ recurse in
  { n in n > 0 ? n * recurse(n - 1) : 1 }
})

print(factorial(7)) // 5040
print(factorial(10)) // 3628800

...and here's another example using a struct to provide more control flexibility over the recursion.
PHP: 
typealias Terms = (x: Int, y: Int) // Tuple of the terms of Fibonacci recurrence relationship i.e. previous 2 numbers
struct Fibonacci {
  let value: Int
  let next: () -> Fibonacci
}

let fibonacci: (Terms) -> Fibonacci = recursive({ (recurse:  escaping (Terms) -> Fibonacci) in {
  (t: Terms) in Fibonacci(value: t.x + t.y, next: { recurse((t.y, t.x + t.y)) })
  }
})

print(fibonacci((0,1)).next().next().next().value) // returns the 6th fibonacci number : 5

That's it for the solution. Let me know if you need help translating this to your language of choice.

[table="width: 70%, class: outer_border, align: center"]
[tr]
[td]Note:
This function has the same limitations relevant to all recursive code i.e. without tail call optimisation it can easily overrun the stack i.e. stack overflow. If your language doesn't provide adequately for optimisation of tail calls, you would have to look at re-implementing this around a Trampoline routine which will optimise out the problem of stack loading by using thunks; essentially a closure built around a conditional loop.

In all the Swift code examples; the keyword "escaping" must be proceeded by an ampersand symbol. MyBB's forum keeps modifying any code that includes an ampersand. All "escaping", should be [MENTION=14943]esca[/MENTION]ping[/td]
[/tr]
[/table]
 
Last edited:
[MENTION=8711][)roi(][/MENTION] is it possible for you to create a master thread that acts as a table of contents for all your functional challenges? Currently doing assignments/exams next week, so a bit busy but would like to go through them all afterwards.
 
Johnatan56 said:
[MENTION=8711][)roi(][/MENTION] is it possible for you to create a master thread that acts as a table of contents for all your functional challenges? Currently doing assignments/exams next week, so a bit busy but would like to go through them all afterwards.
Click to expand...
Sure I'll do that later today.

Ps. look out for the next post in the current thread; I'm going to be expanding on higher-order functions (more examples) and also showing how composition can avoid unnecessary computation cycles.
 
Higher Order Functions
As mentioned in the last post, functions are considered to be higher-order when it does at least one of the following:
  • takes one or more functions as arguments (i.e. procedural parameters),
  • returns a function as its result.

The focus of this post is to explore a specific higher order function called map.
The concept of mapping over a set of elements to apply a function derives from mathematics. In particular mapping over an elements stored in a container type like an Array. map allows us to apply a transformative function to the elements within the Array and then recompose the transformed elements back into a new Array.


[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Note: The transformation process performed by functor's map method can alter the elements within the Array; but will not alter the Array. i.e. it's quite valid to convert an Array of integer values to an Array of Strings.[/td]
[/tr]
[/table]

Mapping over elements
The concept of iterating over the elements in a structure like an Array in order to apply a transformation is by no means a new concept; hence the following parcel of code tends to repeat quite often in the programs we write:
PHP: 
let values = [1, 2, 3, 4, 5]
print(values)
// --------------------------
var result = [Int]()
for value in values {
  result.append(increment(value))
}
// --------------------------
print(result)
The part between the two comment lines is essentially the task that map performs. In functional programming even small parcels of code like this are considered to be repetition, and hence following a concept similar to DRY, the mathematicians derived a algebra (pattern) for this parcel of code, or more specifically the expected behaviour for all code of this nature.

The concept of map is certainly not limited to Arrays, its just as relevant for other container type like:
  • Optional
  • Either
  • Dictionary
  • Tuples
  • etc...x
The only requirement is that all renditions of map have a consistent behaviour; a set of laws are always defined to govern every functional algebra (pattern) we use. These laws ensure that the behavior and outcome remains constant in the mathematical and hence in use the outcome should always be unsurprising.

Functor laws:
  • Functors must preserve identity morphisms
  • Functors preserve composition of morphisms
This probably will initially sound a bit like mathspeak / gobbledygook -- but as with anything, terms are a necessary evil to avoid misunderstanding, OOP programming in that sense is no different; nobody starts out understanding inheritance or polymorphism.

Ok so let's remove the confusion by explaining each of these laws through an example:

Example: Functors must preserve identity morphisms
  • Morphism is a greek term that means to "maintain the shape or form"
  • In mathematics an identity is an equality relation; for example:
    • The number zero (0) is considered the identity value for addition, because adding it doesn't change the result, for example: 1+ 0 = 1
    • The number one (1) is considered the identity value for multiplication, because multiplying by 1, doesn't change the result, for example: 1 * 1 = 1
We can however define an identity function for any type as follows:
PHP: 
public func id<A>(_ a: A) -> A {
  return a
}
Basically this is a function that simply returns the same value that it received unchanged; in the same way that zero (0) is identity for addition and one (1) is identity for multiplication.

Ok to summarise the 1st law state that "Functors must preserve identity morphisms" i.e. if we map over any array using the identity function, we should always expect to see the same result unchanged, for example:
PHP: 
let values = [1, 2, 3, 4, 5] 
let result = values.map(id)
print(result) // [1, 2, 3, 4, 5] -- same shape re it's still an Array, and secondly same values re identity.

Example: Functors preserve composition of morphisms
Ok so we should by now be familiar with the term morphism i.e. it's a computation that preserves the same shape
Next let's look at composition in terms of mathematics.
composition.png

Basically if we have a function (f) that takes an A and returns a B, and we feed that into a function (g) that takes a B and returns a C, it should be the same as the feeding an A into a function that is the composition of the f and g i.e. f • g

Ok let's see that in code using our two previous defined functions: increment and square:
PHP: 
let values = [1, 2, 3, 4, 5] 
let result = values.map(increment).map(square)
print(result) // [4, 9, 16, 25, 36]

let incrementSquare = { square(increment($0)) }
let result2 = values.map(incrementSquare)
print(result2) // // [4, 9, 16, 25, 36]
result is the same as result2; composition is preserve, i.e. same as mapping over increment and then square.

2 Iterations: Map over increment and then again map over square
Array map twice with increment then square.jpg

1 Iteration: Map over a single function that is the composition of increment and square
Array map once with composition of increment and square.jpg

[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Note:
  • By ensuring that our types comply with these functor laws, we can ensure that our map method will behave properly i.e. no surprises.
  • Map twice naturally is more costly ito computation because we essentially iterate twice over every element, whereas if we map over the composition, we only iterate once.

[/td]
[/tr]
[/table]

...but... you maybe wondering how is it possible for Array's map to behave the same way as Optional map?
Let summarised the differences between Array and Optional:
  • Array is a type with zero or an infinite number of elements of any type, for example: an Array of Prices (multiple integer values)
  • Optional is a type with None, or Some element of any type, for example: An Optional of a salary (single Integer value)
As you should see both can have zero, and both can have a value(s). In a different context we could imagine something that is null or not null. So in both cases we need to ensure that our map method behaves correctly with no values or some values:
  • No values == doing nothing
  • Some values == apply the function (morphism) to each element. In the case of Optional that wll always be one, but applying it to one or more is still logically the same. The only part that differs is how many elements i.e. a simple matter of iteration.

...and if you missed it. Map by design allows us to skip using the following code patterns:
PHP: 
if (*insert object* != null) {
  // do something with the object
}

// Using a functor container type like Array or Optional allows us to replace that code with...
*object in a container*.map( *do something* )

// for example (non null):
let salary1: Int? = 23
let increase1 = salary1.map(increment) // Optional<Int>.some(24)

// for example (null / nil)::
let salary2: Int? = nil
let increase2 = salary2.map(increment) // Optional<Int>.none & no null pointer exception
 
Last edited:
Composition Operators

Composition
We've briefly touched on the concept of composition in this thread a few times already; however we haven't specifically addressed why encapsulation and the subsequent methods tend to break composition.

[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Concept of encapsulation in OOP promotes a class design that bundles related data and methods.[/td]
[/tr]
[/table]

The problem is that encapsulation in the norm tends to break composition rather than enable it; which is a problem considering that another OOP adage recommends that we should "favour composition over inheritance".

As with most things, its best to illustrate the problem rather than simply talking around the sidelines. This post aims to demonstrate this problem, and secondly to introduce composition operators and the compositional benefits of standalone functions.

OOP encapsulation and .dot method chaining
Ok, let's assume we need to add 2 computations to the Int type; increment and square.

Let's add this as extension methods on Int:
PHP: 
extension Int {
  func increment() -> Int {
    return self + 1
  }
  
  func square() -> Int{
    return self * self
  }
}

// usage is simple
print(2.increment()) // 3
print(2.increment().square()) // 9
This is easily interpreted from left-to-right, whereas normal free functions tend to read from right-to-left or inside-out. So why have I stated that methods tend to break composition rather than enable it?

Ok let's consider how we would create a composition of two methods, as example let's create a new method that is the composition of increment and square. To achieve this we need to create a new method, for example:
PHP: 
extension Int {
  func incrementAndSquare() -> Int {
    return self.increment().square()
  }
}

// Usage example:
print(2.incrementAndSquare()) // 9
Naturally this works, but we ended up having to write 5 lines of code to achieve this; quite a bit of boilerplate for composition that again won't easily compose without creating yet another extension method.

Ok, so how does this work with functions?
First off let's review the code for our standalone functions for increment and square:
PHP: 
func increment(_ value: Int) -> Int {
  return value + 1
}

func square(_ value: Int) -> Int {
  return value * value
}

// usage is similarly simple
print(increment(2)) // 3
print(square(increment(2))) // 9
... but the composition of increment and square is not as easily to interpret as the .dot method chaining alternative. So how can we make this better?

Option1: Use our pipe forward operator |> (reverse application)
PHP: 
print(2 |> increment |> square) // 9
Whilst this looks better; it has a limitation in that the pipe forward operator is actually reverse application; the important keyword being application i.e. at each function the result is calculated before it's piped forward to the next function -- which is not composition. Composition would perform increment and square in a single step.

Option 2: Let's define a new forward composition operator >>>
PHP: 
infix operator >>>: infixr9
[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Note:
This has a precedence group that is right associative and at a higher precedence that all other operators. i.e. we want the compiler to prioritise composition.
I have chosen to use the >>> symbols for this operator, because it's very similar to the composition operator >> used in Elm, however to avoid confusion with bit shifting, I've opted to use >>> instead of >>.[/td]
[/tr]
[/table]
Here's the definition of the forward compose operator >>>
Code: 
public func >>> <A, B, C>(f:    [MENTION=14943]esca[/MENTION]ping (A) -> B, g:    [MENTION=14943]esca[/MENTION]ping (B) -> C) -> (A) -> C {
  return { a in g(f(a)) }
}
Essentially this generic definition wraps whatever function is on the right around the output from the function on the left, for example: square(increment...

Ok let's see how to use this:
PHP: 
print(2 |> increment >>> square) // 9
Quite easy; the higher precedence of the forward compose operator ensures that the two functions are composed together before the pipe forward operator applies the value of 2.

...and unlike our class method extension we are not limited to methods on our type, meaning that it's easy to compose this with other functions, for example:
PHP: 
print(2 |> increment >>> square >>> Optional.some) // Optional(9)
Again the 2 is only applied to the composition of all 3 functions (increment, square & Optional.some)

Using this with higher order functions
In the previous post we saw an example of function composition to avoid map over an array's element's twice; however to achieve that we had to define a separate function, for example:
PHP: 
let values = [1, 2, 3, 4, 5]  
let incrementSquare = { square(increment($0)) } 
let result = values.map(incrementSquare) 
print(result) // [4, 9, 16, 25, 36]

With our new forward composition operator this is no longer necessary, and the above can be simplified:
PHP: 
let values = [1, 2, 3, 4, 5]  
let result = values.map(increment >>> square) 
print(result) // [4, 9, 16, 25, 36]

// but we can also compose it with a String initialiser to convert our Int result to a String.
let result = values.map(increment >>> square >>> String.init)
print(result) // ["4", "9", "16", "25", "36"]

The solutions presented here not only enable point-free (tacit) code, they also make it far easier to perform composition without the need to create more methods. It's an overall win-win because we not only avoid the extra boiler plate; we also gain more flexibility to compose new computations inline and across types.
 
Last edited:
Composition with Effects
Ok, let's wrap up this beginner's friendly functional thread with side effects.

Pure Functions
A pure function is a function where the return value is only computed by its input values, without observable side effects, for example:
PHP: 
func add2(_ value: Int) -> Int {
  return value + 2
}

print(add2(5)) // 7
print([1, 2, 3, 4].map(add2).map(add2)) // [5, 6, 7, 8]
print([1, 2, 3, 4].map(add2 >>> add2)) // [5, 6, 7, 8]
These types of computations are easily to work with and to reason about. more so we can assert that all of their output is correct in a test, for example:
PHP: 
assert(add2(5) == 7) 
assert(add2(10) == 12)

[table="width: 100%, class: outer_border, align: center"]
[tr]
[td]Note: `assert` will only work when the Swift compiler `Optimization Level` is set to `-Onone.`

Screen Shot 2018-05-28 at 11.44.10.png

A more complete way to add tests to your application is use a testing framework e.g. XCTest
[/td]
[/tr]
[/table]

Effectual Functions
This is the opposite of a pure function; a function is considered effectual when its output is not resultant solely from its input value and / or it has observable side effects.

Let's see an example of an effectual function.

PHP: 
func effectStars(_ value: Int) -> Int {
  let result = Int(sin(Double(value)) * 10) + 2
  let stars = String(repeating: "*", count: abs(result))
  print(stars)
  return result
}
The above function takes an integer value:
  1. applies a sine conversion to produce a Integer `result`
  2. compute an absolute number of asterisk `*` using the computed `result`
  3. print the `stars` to the console (the effect)
  4. returns the Integer `result`
For example:
PHP: 
print(effectStars(2)) 
// 11 is the value returned by our function for an input value of 2
However when we look at the console, we see the actual output was:
Code: 
***********  
11
The line of asterisk was produced by the side effect i.e. it affected our application's global state directly, in comparison with our `add2` function which strictly returns only the result of its computation as defined in the function's signature; and does not affect global state.

Ok but why is this a problem?
Direct changes to global state can produce some surprising results, that are often difficult to debug.

As we've seen previously, one of the functor laws emphasizes the need to preserve composition of morphisms, why this is important should hopefully be more clear after this example:
PHP: 
print([2, 3].map(effectStars).map(effectStars).map(effectStars))
Here we take in an array of 2 integers, and then use map to apply the effectStars function to each value, to which we then .dot chain 2 map applications of effectStars; basically we execute our function 3 times for each value element, passing the value from 1 compute cycle into the next map and so on.

Here's the output from this:
Code: 
***********
***
*******
***
****
***
[-4, 3]
The asterisk are produced by our function's effect on global state (direct output to the console), and the [-4, 3] is the output returned from our function (as defined by it's function signature).

Ok let's refactor our code...
Imagine you are asked to refactor this code e.g. to try to optimise away some of the compute cycles.

First thing we notice is that we are using 3 compute cycles to achieve this outcome; each map is the equivalent of a loop i.e. we loop over every element in the array; which in this case is 6 cycles (3 maps x 2 elements). This is naturally something we know by functor (or mathematical) laws that we should be able to optimise away with composition, for example:

PHP: 
print([2, 3].map(effectStars >>> effectStars >>> effectStars))

// Ps. this is the same as the expanded form below; 
// the >>> (composition) operator allows us to write terse code, with less brackets 
// and in a point-free style i.e. where we don't have to explicitly specify the `v` input variable:
// 
print([2, 3].map({ v in effectStars(effectStars(effectStars(v))) }))
So instead of mapping 3 times over effectStars, we map once over the composition of 3 effectStars; instantly reducing the compute cycles from 6 to 2.

...excellent, now let's run our code and check the output to make sure we haven't broken anything...
Code: 
***********
*******
****
***
***
***
[-4, 3]
nausea.jpg

Oops... whilst the return values are the same [-4, 3], the effect on global state is visibly different.

This is a key issue with unfettered changes to global state during the compute; we end up without realizing it breaking some of the key tenets we tend to rely upon; e.g. we broke composition.

[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]
This is why
...the functional approach is always to encapsulate those effects until the entire compute cycle is complete, instead of effecting changes during the compute, we effect changes in a controlled fashion at the end of a compute. Essentially we significantly reduce the number of places where global state can be affected.

In a typical application this can be very small, because most of what we do does not need to directly interact with global state.

Naturally the above example was derived for ease of illustration; real world state issues are far more complex, and hence the encapsulating of effects will be even more beneficial and apparent. With functionally pure code, we not only have code we can rely upon, we also have code that will be easier to test and easier to refactor.
[/td]
[/tr]
[/table]

... the next post will demonstrate how we encapsulate the state of our effectStars in order to:
  • not break composition.
  • make our function testable in the whole; i.e. test not only the return result, but also the effect.
  • separate the application of the effect from its computation.
 
Last edited:
Encapsulating Side Effects
All the visually intriguing part of programming is directly tied into side effects i.e. as much as they present us with challenges we simply can’t create applications without them.

...and that's certainly not a major issue, because by simply changing the way we approach problems we can better manage the side effects we encounter every day, and write code that is easier reason about and test, and in the process also not break composition.

How do we steer clear of side effects during the compute
One way to steer clear side-effects is to not execute side-effecting code i.e. instead of running side-effects, we can return values which we need to recreate the side-effects.

That way we get to choose not only when compute expensive UI code runs, but also to compute the least number of effects required to effect a change.
Let’s look at a simple way to control this side effect. Instead of executing the effect in the body of the function, we can return an extra value that can be used at a later time to recreate this effect.

Our effectChange function could print many variations, so in this instance we’ll encapsulate this using an array of strings.
Let's see how we accomplish this with the `effectStars` function
PHP: 
func effectStars(_ value: Int) -> (Int, [String]) {
  let result = Int(sin(Double(value)) * 10) + 2
  let stars = String(repeating: "*", count: abs(result))
  return (result, [stars])
}

// Using this:
print(effectStars(2))
The output from this is:
Code: 
(11, ["***********"])

[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Note: In the above code we have use a data structure called a Tuple to encapsulate both of our return values; the computed Integer value, and the encapsulated effect value. A Tuple is simply a structure that can hold 1 or more values of any type, and is helpful in a case like this where we need to output more than 1 value. In languages that don't by default support Tuples, we can either create them ourselves or we can create a data type expressly for this function.

Ps. just ask if you need help translating this to your preferred language[/td]
[/tr]
[/table]

Let's create a test for this
PHP: 
assert(effectStars(2) == (11, ["***********"])) // asserts both the computed value and the effect value
...and if we provide an incorrect value the assertion fails as expected, for example:
Screen Shot 2018-05-28 at 15.19.38.png
Now we’re getting validation of not only the computed value, but also validation of the effect we want to perform! e.g. Our test would fail if the side effect was in an unexpected format.

Recreating our side effect for the returned result
We can use the following syntax in Swift to separate out the Tuple values from the result.
PHP: 
let (computedValue, effectValue) = effectStars(2)

// Which then allows us to recreate the effect as follows:
effectValue.forEach { 
  print($0)
}
// ***********
We can also achieve this in a more terse way by simply accessing the tuple element by it's index, for example:
PHP: 
let result = effectStars(2)

// Which then allows us to recreate the effect as follows:
result.1.forEach { 
  print($0)
}
// ***********

[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Note:
  • `result.0` in the above example would access the computed value i.e. the first index in our Tuple.
  • `forEach` simply iterates over the elements in our String array.
[/td]
[/tr]
[/table]

Ok so let's recreate our original example that had two different outcomes:
PHP: 
print([2, 3].map(effectStars >>> effectStars >>> effectStars)) // ERROR!!!
...but that produces an error, because our function no longer returns a single output value that is compatible with the input of our second function in our composition. Essentially we are trying to feed a Tuple of 2 values into a effectStars function that only expects 1 Integer value.

So our standard forward compose >>> operator doesn't cater for this discrepancy; to fix this mismatch we expressly need a compose operator that can compose function of the type:
PHP: 
a -> m b  ... with ... b -> m c
The m being some type of container that encapsulates our result value(s)

Say hello to the "fish" compose operator >=>
This operator comes directly from the Haskell world and is used for composition with functions that return a container encapsulating our result(s). This function signature falls into the realm of what we refer to as Monads i.e. a transformation that encapsulates the result of a computation in some type of container type.

This algebra tends to be very useful for effectual computations; with most Haskell IO (input/output) operations being constructed from some type of a Monad.

Ok let's build this operator for our Tuple result; and I'll avoid some of the generics to hopefully make this more easier to understand.
Code: 
// first let's define our operator symbol, and we'll use the same precedence group as >>>
infix operator >=>: infixr9

// next let's create the function for the operator.
public func >=><A, B, C>( _ f:        [MENTION=14943]esca[/MENTION]ping (A) -> (B, [String]), _ g:        [MENTION=14943]esca[/MENTION]ping (B) -> (C, [String])) -> (A) -> (C, [String]) {
  return { a in
    let (b, bLog) = f(a)
    let (c, cLog) = g(b)
    return (c, bLog + cLog)
  }
}
Which is very similar to normal compose operator and...
Code: 
public func >>> <A, B, C>(f:        [MENTION=14943]esca[/MENTION]ping (A) -> B, g:        [MENTION=14943]esca[/MENTION]ping (B) -> C) -> (A) -> C {
  return { a in g(f(a)) }
}
...has two functions from A to B and B to C; the only difference with the fish >=> operator's function signature is that the result of both function f and function g is a tuple with the second element being an Array of String

Internally we still start with A as our input, however here we need to be cognisant that our function f will return a tuple: an Integer and an Array of String. We separate these values into variables b and bLog respectively; we then feed b in function g and compute that outcome, which is again split into the variable c and cLog.

Finally we return a new Tuple which contain c, the Integer result of the composition of functions f and g, and for the logs we simply add them together; i.e. add the contents of 1 String Array to the contents of another String Array. i.e. we end up with an Array of the effects from both function f and g.

Ok let's see this in use:
PHP: 
// Note the use of the fish >=> operator in place of the >>> operator
print([2, 3].map(effectStars >=> effectStars >=> effectStars))
...and now let's look at the output and our ability for assert (test) its validity
PHP: 
// testing of both the values and the effects
let result = [2, 3].map(effectStars >=> effectStars >=> effectStars)
assert(result[0] == (-4, ["***********", "*******", "****"]))
assert(result[1] == (3, ["***", "***", "***"]))
...and finally let's recreate out effects in the console:
PHP: 
// creating the effects in the console
let result = [2, 3].map(effectStars >=> effectStars >=> effectStars)
result.forEach {
  $1.forEach {
    print($0)
  }
}
i.e. we were returned an array of tuples containing and Integer computation and an Array of effect Strings. So we need to reach inside the array using the 1st forEach, then accessing the 2nd element of the tuple we use $1 (which is an array of effect Strings), so we iterate of that array with another forEach, and print the result ($0 is just syntactic sugar for the 1st returned value from forEach.

Finally here's the output from that:
Code: 
***********
*******
****
***
***
***
 
Last edited:
Alternative take on the recursion problem
After wrapping up all the topics I tabled in the contents; I thought it would be a good idea to leave you with an alternative solution for the recursion problem; and in turn recreate just a few of the tools in the Haskell toolkit related to generation of sequences and introduce infinite sequences and lazy computation.

More specifically we're going to recreate a Swift version of Haskell's:

Let's start with iterate
iterate returns an infinite list of repeated application of function to value. The notion of infinite list derived from a function should sound like a crazy idea, because in most languages these would imply that we are running a computation that never ends i.e. infinite sequence vs. infinite loop

This is quite normal in Haskell due to it's built in ability to delay the actual computation of something until it's required; a feature referred to as lazy evaluation.

This is however not the way things work in many languages including Swift, so to build this I'm going to recreate the concept of a sequence generator, which is a simple structure that will allows us to easily compute the next sequence value on demand.

Code: 
public struct Iterate<A> {
  fileprivate var initial: A
  private let transform: (A) -> A
  
  init(_ transform:            [MENTION=14943]esca[/MENTION]ping (A) -> A, _ initial: A) {
    self.transform = transform
    self.initial = initial
  }
  
  mutating public func next() -> A {
    initial = transform(initial)
    return initial
  }
}
My version of Iterate is built from struct i.e. a value type in Swift that is generic over a single type A, it has an initial value & a transform function from A to A i.e. to generate the next sequence value. It also has a single function called next which is a mutating function i.e. it changes the Iterate struct property values.

Ps. this happens to be the default behaviour for a class. My choice to use a struct instead of class is because of a preference for value semantics over reference semantics. i.e. former being inherently thread safe.

Next use to use our Iterate sequence generator, we need a helper function to extract values from our infinite sequence generator.

Let's create take
take take a n quantity of values from an infinite sequence.
PHP: 
public func take<A>(_ n: Int) -> (Iterate<A>) -> [A] {
  return {
    var iterate = $0
    return [iterate.initial] + (1..<n).map { _ in iterate.next() }
  }
}
Above function takes in two values; a n quantity of desired sequence values and an initialised Iterate struct and returns a n quantity of sequence values. In the map closure we expressly use a underscore character in place of a variable to indicate that we are ignoring the value provided by the range (1...n) i.e. this is because the range together with the map serves only as a loop; our actual sequence values are derive from the iterate.next() method call.

Ok now for the fun part. Let's see an example of lazy extraction of values from an infinite sequence based on a function.

Example using Iterate and take
PHP: 
print(Iterate({ $0 + 2 }, 1) |> take(10))

// output
// [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
I initialised my Iterate struct with a closure that takes a single value to which it adds 2, and I provide the sequence with an Initial value of 1; i.e. I am defining a sequence of all the positive odd Integers values above 0. Next I use the pipe forward operator |> to do a reverse application of the take function, which iteratively executes the next() method for a n specified numbers of times.

Ok let's implement a few more functions; drop, takeWhile, dropWhile -- functions that drop a specified quantity of values, take values while a condition is satisfied, and finally drop values while condition is satisfied.
Code for drop, takeWhile and dropWhile
Code: 
public func takeWhile<A>(_ condition:            [MENTION=14943]esca[/MENTION]ping (A) -> Bool) -> (Iterate<A>) -> [A] {
  return {
    var iterate = $0, value = iterate.initial
    var result = [A]()
    while condition(value) {
      result.append(value)
      value = iterate.next()
    }
    return result
  }
}

public func drop<A>(_ n: Int) -> (Iterate<A>) -> Iterate<A> {
  return {
    var iterate = $0
    (1...n).forEach({ _ in _ = iterate.next()})
    return iterate
  }
}

public func dropWhile<A>(_ condition:            [MENTION=14943]esca[/MENTION]ping (A) -> Bool) -> (Iterate<A>) -> Iterate<A> {
  return {
    var iterate = $0, value = iterate.initial
    while condition(value) {
      value = iterate.next()
    }
    return iterate
  }
}

Let's now have a look at a few use examples of our Iterate, take, drop, takeWhile and dropWhile functions
PHP: 
// generate Integer value from 11 to 20
print(Iterate({ $0 + 1 }, 1)
  |> drop(10)
  |> take(10))

// [11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

// generate odd Integer values from 91 to 99 
print(Iterate({ $0 + 2 }, 1)
  |> dropWhile({ $0 < 90 })
  |> takeWhile({ $0 < 100 })
)

// [91, 93, 95, 97, 99]

Next let's recreate the fibonacci sequence.
PHP: 
// here we need to a tuple i.e. there are two values we need to pass between each iteration of sequence
print(Iterate({ ($1, $0 + $1) }, (0, 1))
  |> take(10)
)

// output
[(0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), (21, 34), (34, 55)]
As you can see the output is less than desired as it returns an array of tuples values, but we really only need the fibonacci values. To achieve we have to extract the first value of a tuple. To achieve this with our pipe forward operator I'm go to also include the code for a standalone map function on Array.
Code: 
// standalone map function on Array
public func map<A, B>(_ transform:            [MENTION=14943]esca[/MENTION]ping (A) -> B) -> ([A]) -> [B] {
  return { $0.map(transform) }
}

// here's the iteration code for the fibonacci including the extraction of the first tuple value
print(Iterate({ ($1, $0 + $1) }, (0, 1))
  |> take(10)
  |> map({$0.0})
)

// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
We can however do 1 more simplification wrt to the tuple i.e. we can remove the syntactic sugar & the closure in order to make our code point free by adding a function that extracts the 1st element
PHP: 
// extract first tuple element
public func first<A, B>(_ tuple: (A, B)) -> A {
  return tuple.0
}

// modifying our fibonacci sequence to use this tuple function
print(Iterate({ ($1, $0 + $1) }, (0, 1))
  |> take(10)
  |> map(first)
)

// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
...and there we have it a recreation of the fibonacci sequence using our Iterate generator.

Let's now look at a few more examples
PHP: 
// fibonacci sequence dropping first 5 elements, and then taking the next 10
print(Iterate({ ($1, $0 + $1) }, (0, 1))
  |> drop(5)
  |> take(10)
  |> map(first)
)

//  [5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

// Fibonacci sequence drop elements below 900 and take values below 10000
print(Iterate({ ($1, $0 + $1) }, (0, 1))
  |> dropWhile({ $0.0 < 900 })
  |> takeWhile({ $0.0 < 10000 })
  |> map(first)
)

// [987, 1597, 2584, 4181, 6765]

Ok.... so assuming that not everybody is going to immediately love the use of so many new operators, let's look at how we adapt our iterate for the .dot chaining method crowd:

Ps... we simply add these extension methods...
Code: 
extension Iterate {
  public func take(_ n: Int) -> [A] {
    return self |> funk.take(n)
  }
  
  public func takeWhile(_ condition:            [MENTION=14943]esca[/MENTION]ping (A) -> Bool) -> [A] {
    return self |> funk.takeWhile(condition)
  }
  
  public func drop(_ n: Int) -> Iterate<A> {
    return self |> funk.drop(n)
  }
  
  public func dropWhile(_ condition:            [MENTION=14943]esca[/MENTION]ping (A) -> Bool) -> Iterate<A> {
    return self |> funk.dropWhile(condition)
  }
}

[table="width: 80%, class: outer_border, align: center"]
[tr]
[td]Note: the funk. in the above code refers to the Swift module that contains this function, substitute with the name of your project.[/td]
[/tr]
[/table]


Here's a few .dot chaining method examples:
PHP: 
print(Iterate({ $0 + 1 }, 1)
  .drop(10)
  .take(10))

print(Iterate({ $0 + 2 }, 1)
  .dropWhile({ $0 < 90 })
  .takeWhile({ $0 < 100 })
)

print(Iterate({ ($1, $0 + $1) }, (0, 1))
  .take(10)
  .map(first)
)

...and to finish off let's look at recreating an alternating binary sequence from our 1st functional challenge thread using our new Iteration struct:
PHP: 
print(Iterate({ $0 == 0 ? 1 : 0 }, 0)
  |> take(6)
)

// [0, 1, 0, 1, 0, 1]

Anyway that's it for this thread -- pm me for any request to help with translating this code to another language and / or to provide suggestions for a future thread.
 
Last edited:
Here's another take on the recursive higher order function:

[table="width: 90%, class: outer_border, align: center"]
[tr]
[td]
Recursively applies a endomorphic function to an argument until a given predicate returns true
until :: (a -> Bool) -> (a -> a) -> a -> a[/td]
[/tr]
[/table]

Code: 
public static func until<A>(_ p:      [MENTION=14943]esca[/MENTION]ping (A) -> Bool) ->        [MENTION=14943]esca[/MENTION]ping (A) -> A) -> (A) -> A {
  return { f in { a in p(a) ? a : self.until(p)(f)(f(a)) } }
}
Basically it's a predicate function that takes an endomorphic function (same type to same type, e.g. Int -> Int), which it recursively applies until the predicate returns true.


Here's a few usage examples:
PHP: 
let example1 = { $0 * 2 } |> until({$0 > 100}) <| 1
print(example1) // 128

let example2 = { $0 / 2 } |> until({$0 % 2 == 1}) <| 400
print(example2) // 25

let fib = { index in ({ (i, p, c) -> (Int, Int, Int) in (i + 1, c, p + c)}
  |> until({ (i, p, c) -> Bool in i >= index }) <| (1, 0, 1)).2 }

print("6th fibonacci value is \(fib(6))") // 8

Note: |> is a forward application operator, and <| is a reverse application operator (i.e. standard function application; function acts on the value on the right).
 
Last edited:
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X