The original link

Those who know functional programming may have heard of Functor, Applicative, Monad and other concepts more or less, but fewer of them can really understand them. There are many articles on the Internet, and even books with chapters on them, but very few explain them clearly. Recently, I took the time to explore these concepts out of the RxSwift source code. This article is my summary after understanding the concepts of functor, applicable functor, monad and so on.

The sample programming language used in this article is Swift.

The basic concept

Type structure

Type Constructor, in short, types that take generics as arguments to build concrete types, can be referred to simply as generic classes. With type constructors, we can abstract out more general data types. The Optional

and Array

built into Swift are type constructors.

Disjoint union

Disjoint Union is similar to the Union data type in C and can be thought of as a wrapper type that can hold a single instance of different types in the same location. The data structure Either is a disjoint union type, as shown in the following example:

enum Either {
    case left(Int)
    case right(Int)}Copy the code

Generic disjoint union

When we use type constructors and disjoint unions together, we can abstract out more general generic disjoint union types. As shown below, Either classes can define a wrapper class by binding different generic types for L and R.

enum Either<L.R> {
    case left(L)
    case right(R)}Copy the code

In Swift, the built-in Optional type is a wrapper class that can be bound by generics, as follows:

enum Optional<Wrapped> {
    case none
    case some(Wrapped)}Copy the code

Array in Swift is also a special wrapper class, but Array can be bound to only one generic type.

In the following sections, we will introduce functors, applicable functors, and monads by customizing a disjoint union Result type.

enum Result<T> {
    case success(T)
    case failure
}
Copy the code

Functor

In the ordinary case, we can use a function to operate on a value, such as +3 on an Int, we can define a plusThree function:

func plusThree(_ addend: Int) -> Int {
    return addend + 3
}
Copy the code

The above plusThree can do +3 on Int, but it doesn’t seem possible to do the same on the wrapper class Result. So how to solve this problem? Functor is used to solve the problem in this scenario.

Functors can apply ordinary functions to a wrapper type.

In Swift, the type that implements the map method (fmap in Haskell) by default is a functor, that is, the map method can apply ordinary functions to a wrapper type. Such as:

Result.success(2).map(plusThree)
// => .success(5)

// Use trailing closure syntax
Result.success(2).map { $0 + 3 }
// => .success(5)
Copy the code

Let’s take the Result type as an example and make it a functor by implementing the Map method. As follows:

extension Result {
    // Satisfy Functor's condition: The map method can apply ordinary functions to wrapped classes
    func map<U> (_ f: (T) - >U) -> Result<U> {
        switch self {
        case .success(let x): return .success(f(x))
        case .failure: return .failure
        }
    }
}
Copy the code

The map implementation works by taking a value from the wrapper class through pattern matching, applying a normal function to that value, and finally putting the calculation back into the wrapper class for return. The process is shown in the figure below:

For simplicity, we can define an infix operator <^> (<$> in Haskell) for the map method as follows:

precedencegroup ChaningPrecedence {
    associativity: left
    higherThan: TernaryPrecedence
}
infix operator < ^ >: ChaningPrecedence
func < ^ > <T.U>(f: (T) - >U, a: Optional<T- > >)Optional<U> {
    return a.map(f)
}
Copy the code

<^> is used as follows:

let result1 = plusThree < ^ > Result.success(10)
// => success(13)
Copy the code

In Swift, the built-in Array type is a functor, and the map method implemented by default applies ordinary methods to the Array type, eventually returning an Array type. As follows:

let arrayA = [1.2.3.4.5]
let arrayB = arrayA.map { $0 + 3 } 
// => [4, 5, 6, 7, 8]
Copy the code

In RxSwift, the Observable type is also a functor, and the map method implemented by default applies ordinary methods to the Observable type, eventually returning an Observale type. As follows:

let observe = Observable<Int>.just(1).map { $0 + 3 }
Copy the code

Applicative

Functors can apply ordinary functions to wrapper classes, so how do you apply wrapper functions to wrapper classes? What is a wrapper function? A wrapper function can be thought of as using a wrapper class to encapsulate a normal function. As follows:

// The function is wrapped as a value in the Result class
let wrappedFunction = Result.success({ $0 + 3 })
Copy the code

So how to solve this problem? The Applicative is used to solve the problem in this scenario.

Application functors can apply a wrapper function to a wrapper type.

In Swift, the type that implements the apply method by default is the application functor, that is, the apply method can apply a wrapper function to a wrapper type.

Let’s take the Result type as an example and make it an applicable functor by implementing the apply method. As follows:

extension Result {
    // Satisfy the Applicative condition: the apply method can apply a wrapper function to a wrapper class
    func apply<U> (_ f: Result< (T) - >U>) -> Result<U> {
        switch f {
        case .success(let normalF): return map(normal)
        case .failure: return .failure
        }
    }
}
Copy the code

The specific principle of apply implementation is to take the common function and value from the wrapper function and wrapper type respectively through pattern matching, apply the common function to the value, then put the result into the wrapper type, and finally return the wrapper type. The process is shown in the figure below:

For simplicity, we can define an infix operator <*> for the apply method as follows:

infix operator < * >: ChainingPrecedence
func < * > <T.U>(f: Result< (T) - >U>, a: Result<T- > >)Result<U> {
    return a.apply(f)
}
Copy the code

<*> is used as follows:

let wrappedFunction: Result< (Int) - >Int> = .success(plusThree)
let result = wrappedFunction < * > Result.success(10)
// => success(13)
Copy the code

To facilitate daily development, we can implement the Apply method for the common Optional and Array types of Swift to become applicable functors. As follows:

extension Optional {
    func apply<U> (_ f: Optional< (Wrapped) - >U>) -> Optional<U> {
        switch f {
        case .some(let someF): return self.map(someF)
        case .none: return .none
        }
    }
}

extension Array {
    func apply<U> (_ fs: [(Element) - >U])- > [U] {
        var result = [U] ()for f in fs {
            for element in self.map(f) {
                result.append(element)
            }
        }
        return result
    }
}
Copy the code

Monad

Functors can apply ordinary functions to wrapper types; You can apply a wrapper function to a wrapper type using functors; Monads can apply ordinary functions that return a wrapper type to a wrapper type.

Ordinary functions that apply functors that can return a wrapper type are applied to a wrapper type.

In Swift, the type that implements the flatMap method (or bind) by default is a monad, that is, the flatMap method can apply ordinary functions that return the wrapper type to a wrapper type. Many people like to describe flatMap’s ability to reduce dimension, but flatMap can do more than that.

Let’s take the Result type as an example and make it a monad by implementing the flatMap method. As follows:

extension Result {
    func flatMap<U> (_ f: (T) - >Result<U>) -> Result<U> {
        switch self {
        case .success(let x): return f(x)
        case .failure: return .failure
    }
}
Copy the code

For simplicity, we can define an infix operator >>- (>>= in Haskell) for the flatMap method as follows:

func < * > <T.U>(f: Result< (T) - >U>, a: Result<T- > >)Result<U> {
    return a.apply(f)
}
Copy the code

>>= is used as follows:

func multiplyFive(_ a: Int) -> Result<Int> {
    return Result<Int>.success(a * 5)}let result = Result.success(10) >>- multiplyFive >>- multiplyFive
// => success(250)
Copy the code

In RxSwift, the Observable type is also a monad, and the default implementation of the flatMap method applies methods that return an Observable type to an Observable, eventually returning an Observale type. As follows:

let observe = Observable.just(1).flatMap { num in
    Observable.just("The number is \(num)")}Copy the code

conclusion

Finally, we summarize the definitions of functors, applicable functors and monads:

Functor: Yesmap 或 < ^ >Apply a generic function to a wrapper type
Applicable functor: Can passapply 或 < * >Apply the wrapper function to the wrapper type
Monad: Can passflatMap 或 >>-Apply the normal function that returns the wrapper type to the wrapper type

By combining functors, applicable functors, and monads, we can maximize the power of functional programming. In RxSwift, functors, trial functors and monads are also widely used. In future articles, we’ll explore further how RxSwift uses them to build a functional responsive framework.

reference

Haskell
Scheme
Functors, Applicatives, And Monads In Pictures
Three Useful Monads
Swift Functors, Applicative, and Monads in Pictures
What is Monad (Functional Programming)? What exactly is a functor? ApplicativeMonad
The religion of functional languages
Functional Programming Design Patterns
Railway Oriented Programming
Functional Programming – An overview of an article Functor, Monad, Applicative
Improved operator declarations

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Functional programming — Functor, Applicative, Monad

The basic concept

Type structure

Disjoint union

Generic disjoint union

Functor

Applicative

Monad

conclusion

reference

Functional programming — Functor, Applicative, Monad

The basic concept

Type structure

Disjoint union

Generic disjoint union

Functor

Applicative

Monad

conclusion

reference

Related Posts

Read this article on how to implement Flutter rich text cheaply!

The old driver iOS # 44 | 2018-11-19 weekly newspaper

An iOS development tour of Android development – six layout