Functional Programming - Fun Monoid (Unit semigroup)

preface

Monoid (unit semigroup), a concept derived from mathematics; Due to its abstract nature, Monoid plays an important role in functional programming.

This article will introduce concepts related to Monoid from an engineering perspective, and combine several interesting data structures (such as Middleware and Writer) to show the powerful power and usefulness of Monoid itself.

Semigroup

Before we start Monoid’s performance, let’s get a feel for Semigroup, which is defined on Wikipedia as:

Set S and binary operations on it ·:S×S→S. If meet the associative law, i.e., ∀ x, y, z ∈ S, have (x, y), z = x, y, z), says that in order to (S, ·) for semigroup, operation, known as the multiplication of semigroup. In practice, when the context is clear, it can be abbreviated as “semigroup S”.

The mathematical concepts above are abstract and can be difficult to understand. Here is a simple example to illustrate:

For the natural numbers1, 2, 3, 4, 5...In terms of addition+Two natural numbers can be added, and the result is still a natural number, and the addition satisfies the associative law :(2 + 3) + 4 = 2 + (3 + 4) = 9. In this way we can think of the natural numbers and addition as forming a semigroup. There are also natural numbers and multiplication operations.

Semigroup Semigroup Semigroup Semigroup Semigroup Semigroup Semigroup Semigroup

// MARK: - Semigroup

infix operator< > :AdditionPrecedence

protocol Semigroup {
    static func <> (lhs: Self, rhs: Self) -> Self
}
Copy the code

The protocol Semigroup declares an operation method whose two parameters and return values are of the same type that implements semigroups. We usually refer to this operation as append.

Semigroup is a String and Array type.

extension String: Semigroup {
    static func <> (lhs: String, rhs: String) -> String {
        return lhs + rhs
    }
}

extension Array: Semigroup {
    static func <> (lhs: [Element], rhs: [Element])- > [Element] {
        return lhs + rhs
    }
}

func test(a) {
    let hello = "Hello "
    let world = "world"
    let helloWorld = hello <> world
    
    let one = [1.2.3]
    let two = [4.5.6.7]
    let three = one <> two
}
Copy the code

Monoid (Unit semigroup)

define

Monoid is also a Semigroup, but it is called a Semigroup because it has identity elements. The identity element is defined on Wikipedia as:

There exists an element e on the set S of semigroup S such that any element a of the set S conforms to a·e = e·a = a

For example, in the introduction to Semigroup above, the natural numbers form a Semigroup with addition. It is obvious that the natural number 0 added to any other natural number is equal to the original number: 0 + x = x. So we can add 0 as the identity element to a semigroup of natural numbers and addition operations to get a semigroup of identity.

Here is the definition of Monoid in Swift:

protocol Monoid: Semigroup {
    static var empty: Self { get}}Copy the code

As you can see, the Monoid protocol inherits from Semigroup and uses the empty static attribute to represent the unit element.

Let’s implement Monoid again for String and Array and briefly demonstrate its use:

extension String: Monoid {
    static var empty: String { return ""}}extension Array: Monoid {
    static var empty: [Element] { return[]}}func test(a) {
let str = "Hello world" <> String.empty // Always "Hello world"
let arr = [1.2.3] < > [Int].empty / / Always [1, 2, 3]
}
Copy the code

combination

For continuous operations with multiple Monoids, we now write the following code:

let result = a <> b <> c <> d <> e <> ...
Copy the code

If monoids were numerous, or if they were wrapped in an array or Sequence, it would be difficult to write chain operations all the time, or the code would become awkward. At this point, we can define our serial Monoid operation concat based on the Reduce method of Sequence:

extension Sequence where Element: Monoid {
    func concat(a) -> Element {
        return reduce(Element.empty, <>)
    }
}
Copy the code

In this way, we can easily concatenate several monoids in an array or Sequence:

let result = [a, b, c, d, e, ... ] .concat()Copy the code

conditions

Before we get into the conditional nature of Monoid, let’s introduce a very simple data structure that is used to handle some tasks in a plan. I’ll call it Todo:

struct Todo {
    private let _doIt: () -> ()
    init(_ doIt: @escaping () -> ()) {
        _doIt = doIt
    }
    func doIt(a) { _doIt() }
}
Copy the code

It is simple to use: we first build an instance of Todo from an operation to be processed, and then call the doIt method when appropriate:

func test(a) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")}// Wait a second...

    sayHello.doIt()
}
Copy the code

Not yet powerful enough, let’s implement Monoid for it:

extension Todo: Monoid {
    static func <> (lhs: Todo, rhs: Todo) -> Todo {
        return .init {
            lhs.doIt()
            rhs.doIt()
        }
    }

    static var empty: Todo {
        // Do nothing
        return .init{}}}Copy the code

In the append operation we return a new Todo, and all it needs Todo is do the work of the Todo parameters passed in to the left and right. In addition, we set a Todo that does nothing as the identity element, which satisfies the Monoid definition.

Now we can concatenate multiple toDos. Let’s play with it:

func test(a) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")}let likeSwift = Todo {
        print("I like Swift.")}let likeRust = Todo {
        print("And also Rust.")}let todo = sayHello <> likeSwift <> likeRust

    todo.doIt()
}
Copy the code

Sometimes, the task is to determine whether it is executed according to certain conditions, such as in the test function above, we need to determine whether three TODos are executed according to certain conditions, and redefine the function signature:

func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool)

In order to achieve this requirement, there are generally two painful approaches:

// One
func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")}let likeSwift = Todo {
        print("I like Swift.")}let likeRust = Todo {
        print("And also Rust.")}var todo = Todo.empty
    if shouldSayHello {
        todo = todo <> sayHello
    }
    if shouldLikeSwift {
        todo = todo <> likeSwift
    }
    if shouldLikeRust {
        todo = todo <> likeRust
    }

    todo.doIt()
}

// Two
func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")}let likeSwift = Todo {
        print("I like Swift.")}let likeRust = Todo {
        print("And also Rust.")}var arr: [Todo] = []
    if shouldSayHello {
        arr.append(sayHello)
    }
    if shouldLikeSwift {
        arr.append(likeSwift)
    }
    if shouldLikeRust {
        arr.append(likeRust)
    }
    arr.concat().doIt()
}
Copy the code

Both are slightly complicated and introduce variables, and the code is not elegant at all.

At this point, we can introduce a conditional judgment for Monoid:

extension Monoid {
    func when(_ flag: Bool) -> Self {
        return flag ? self : Self.empty
    }

    func unless(_ flag: Bool) -> Self {
        returnwhen(! flag) } }Copy the code

In the when method, if true is passed in, the method returns itself as it is, whereas if false is passed in, the function returns an identity element, discarding itself (because any append to an identity element is the element itself). The unless method simply swaps the Boolean values in the when parameter.

Now we can optimize the code for the test function:

func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Todo {
        print("Hello, I'm Tangent!")}let likeSwift = Todo {
        print("I like Swift.")}let likeRust = Todo {
        print("And also Rust.")}let todo = sayHello.when(shouldSayHello) <> likeSwift.when(shouldLikeSwift) <> likeRust.when(shouldLikeRust)
    todo.doIt()
}
Copy the code

It’s a little bit more elegant than the previous two.

Some useful monoids

Next, I’ll introduce a few useful Monoids that can be used in everyday project development to make your code more readable, cleaner, and maintainable (most importantly elegant).

Middleware

The Middleware structure is very similar to the Todo mentioned above:

struct Middleware<T> {
    private let _todo: (T) - > ()init(_ todo: @escaping (T) -> ()) {
        _todo = todo
    }
    func doIt(_ value: T) {
        _todo(value)
    }
}

extension Middleware: Monoid {
    static func <> (lhs: Middleware, rhs: Middleware) -> Middleware {
        return .init {
            lhs.doIt($0)
            rhs.doIt($0)}}// Do nothing
    static var empty: Middleware { return .init { _ in}}}Copy the code

Instead of Todo, Middleware sets a parameter on the Todo closure of the generic type defined in Middleware.

Middleware’s job is to pass a value through a bunch of Middleware that does different things, either processing the value or performing side effects (logging, database operations, network operations, etc.). Monoid’s append operation groups each piece of middleware together into a unified entry point that we ultimately just need to pass in values.

For a simple example of using Middleware, let’s say we need to make a parser that decorates rich text NSAttributedString. In this parser, we can provide specific decorations for rich text (change font, foreground, background color, etc.). We can define it like this:

// MARK: - Parser
typealias ParserItem = Middleware<NSMutableAttributedString>

func font(size: CGFloat) -> ParserItem {
    return ParserItem { str in
        str.addAttributes([.font: UIFont.systemFont(ofSize: size)], range: .init(location: 0, length: str.length))
    }
}

func backgroundColor(_ color: UIColor) -> ParserItem {
    return ParserItem { str in
        str.addAttributes([.backgroundColor: color], range: .init(location: 0, length: str.length))
    }
}

func foregroundColor(_ color: UIColor) -> ParserItem {
    return ParserItem { str in
        str.addAttributes([.foregroundColor: color], range: .init(location: 0, length: str.length))
    }
}

func standard(withHighlighted: Bool = false) -> ParserItem {
    return font(size: 16) <> foregroundColor(.black) <> backgroundColor(.yellow).when(withHighlighted)
}

func title(a) -> ParserItem {
    return font(size: 20) <> foregroundColor(.red)
}

extension NSAttributedString {
    func parse(with item: ParserItem) -> NSAttributedString {
        let mutableStr = mutableCopy() as! NSMutableAttributedString
        item.doIt(mutableStr)
        return mutableStr.copy() as! NSAttributedString}}func parse(a) {
    let titleStr = NSAttributedString(string: "Monoid").parse(with: title())
    let text = NSAttributedString(string: "I love Monoid!").parse(with: standard(withHighlighted: true))}Copy the code

In the code above, we first defined three basic middleware pieces that can be used to decorate the font, background color, and foreground color for NSAttributedString. Standard and Title combine basic middleware for specific situations (for rich text decoration as headers and as text), and the final text is parsed through calls to the specified middleware.

Todo and Middleware are both abstractions of behavior. The difference is that Todo does not receive input from the environment while Middleware takes input from the environment.

Order

Think about the problems we often encounter in our daily development:

ifCondition 1 is met. {Perform the operation with the highest priority... }else ifCondition 2 is met {perform the second-priority operation}else ifCondition 3 is met {perform the third-priority operation}else ifCondition 4 is met {perform the fourth-priority operation}else if.Copy the code

There may be a problem here, and that is the priority situation. Suppose that one day the program asks us to change the priority of a branch operation, such as raising the third-priority operation to the highest, then we have to change most of the code to do this: for example, to switch the positions of two or more if branches would be painful to change.

Order is used to solve this kind of priority problem related to conditional judgment:

// MARK: - Order
struct Order {
    private let _todo: () -> Bool
    init(_ todo: @escaping () -> Bool) {
        _todo = todo
    }
    
    static func when(_ flag: Bool, todo: @escaping (a)- > () - >Order {
        return .init {
            flag ? todo() : ()
            return flag
        }
    }
    
    @discardableResult
    func doIt(a) -> Bool {
        return _todo()
    }
}

extension Order: Monoid {
    static func <> (lhs: Order, rhs: Order) -> Order {
        return .init {
            lhs.doIt() || rhs.doIt()
        }
    }

    // Just return false
    static var empty: Order { return .init { false}}}Copy the code

When building an Order, we need to pass in a closure that will process the logic and return a Boolean value that, if true, indicates that the Order’s work is done, and then orders with a lower priority do nothing. If false is returned, It means that we have not done an operation in this Order (or an operation does not meet the execution requirements), then the next Order with a lower priority will try to execute its own operation, and then follow this logic.

Let result = orderA <> orderB <> orderC; let result = orderA <> orderB <> orderC; Because we use when defining append to the short-circuit operator | |.

The static method when makes it easier to build an Order from a Boolean value and a closure with no return value, and daily development can choose whether to use the constructor of Order itself or the WHEN method.

func test(shouldSayHello: Bool, shouldLikeSwift: Bool, shouldLikeRust: Bool) {
    let sayHello = Order.when(shouldSayHello) {
        print("Hello, I'm Tangent!")}let likeSwift = Order.when(shouldLikeSwift) {
        print("I like Swift.")}let likeRust = Order.when(shouldLikeRust) {
        print("And also Rust.")}let todo = sayHello <> likeSwift <> likeRust
    todo.doIt()
}
Copy the code

As in the example above, either none of the three Order operations will be executed, or only one will be executed, depending on the Boolean passed in by the WHEN method, in Order of precedence of the append operation.

Array

Array: Monoid: Array: Monoid: Array: Array: Monoid

class ViewController: UIViewController {
    func setupNavigationItem(showAddBtn: Bool, showDoneBtn: Bool, showEditBtn: Bool) {
        var items: [UIBarButtonItem] = []
        if showAddBtn {
            items.append(UIBarButtonItem(barButtonSystemItem: .add, target: self, action: #selector(add)))
        }
        if showDoneBtn {
            items.append(UIBarButtonItem(barButtonSystemItem: .done, target: self, action: #selector(done)))
        }
        if showEditBtn {
            items.append(UIBarButtonItem(barButtonSystemItem: .edit, target: self, action: #selector(edit)))
        }
        navigationItem.rightBarButtonItems = items
    }
    
    @objc func add(a){}@objc func done(a){}@objc func edit(a){}}Copy the code

As with Todo, this code is not elegant. To set the rightBarButtonItems for the ViewController, we first declare an array variable and then add elements to the array according to each condition. This code is not aesthetically pleasing!

Let’s refactor the above code using Array’s Monoid feature:

class ViewController: UIViewController {
    func setupNavigationItem(showAddBtn: Bool, showDoneBtn: Bool, showEditBtn: Bool) {
        let items = [UIBarButtonItem(barButtonSystemItem: .add, target: self, action: #selector(add))].when(showAddBtn)
            <> [UIBarButtonItem(barButtonSystemItem: .done, target: self, action: #selector(done))].when(showDoneBtn)
            <> [UIBarButtonItem(barButtonSystemItem: .edit, target: self, action: #selector(edit))].when(showEditBtn)
        navigationItem.rightBarButtonItems = items
    }
    
    @objc func add(a){}@objc func done(a){}@objc func edit(a){}}Copy the code

This is much more elegant

Writer Monad

Writer Monad is a Monad based on Monoid, which is designed to record specific information, such as logs or history records, while performing operations. It doesn’t matter if you don’t know Monad, it won’t be mentioned here too much, you just need to understand how it works when you read the code.

// MARK: - Writer
struct Writer<T.W: Monoid> {
    let value: T
    let record: W
}

// Monad
extension Writer {
    static func `return`(_ value: T) -> Writer {
        return Writer(value: value, record: W.empty)
    }
    
    func bind<O>(_ tran: (T) -> Writer<O.W- > >)Writer<O.W> {
        let newOne = tran(value)
        return Writer<O.W>(value: newOne.value, record: record <> newOne.record)
    }
    
    func map<O>(_ tran: (T) -> O) - >Writer<O.W> {
        return bind { Writer<O.W>.return(tran($0))}}}// Use it
typealias LogWriter<T> = Writer<T.String>
typealias Operation<T> = (T) - >LogWriter<T>

func add(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 + num, record: "\ [$0)add\(num),")}}func subtract(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 - num, record: "\ [$0)Reduction of\(num),")}}func multiply(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 * num, record: "\ [$0)take\(num),")}}func divide(_ num: Int) -> Operation<Int> {
    return { Writer(value: $0 / num, record: "\ [$0)In addition to\(num),")}}func test(a) {
    let original = LogWriter.return(2)
    let result = original.bind(multiply(3)).bind(add(2)).bind(divide(4)).bind(subtract(1))
    / / 1
    print(result.value)
    // 2 times 3, 6 plus 2, 8 divided by 4, 2 minus 1,
    print(result.record)
}
Copy the code

Writer is a structure, which contains two data, one is the value involved in the operation, the type is generic T, and the other is the information recorded during the operation, the type is generic W, and Monoid needs to be implemented.

The return static method creates a new Writer by passing in a value that will be stored directly in the Writer. Thanks to the nature of Monoid units, return directly sets empty to the information recorded by the Writer during the construction process.

All the bind method does is convert the original Writer by passing in a closure that converts the operand to a Writer. Bind appends the record information during the conversion process, which helps us to automatically record information.

The map method converts the operands inside Writer by passing in a mapping closure of the operands.

Map is derived from the functional programming concept Functor, while return and bind are derived from Monad. If you’re interested in this you can check it out, or you can read my previous article about these concepts.

With Writer Monad, you can focus on writing the business logic of your code instead of spending time taking notes of some information. Writer will automatically take notes for you.

The tail

There are many other monoids that are not mentioned in this article, such as Any, All, and Ordering. You can do this by referring to the relevant documentation.

For Monoid, the important thing is not to understand its related implementation examples, but to deeply understand its abstract concepts, so that we can say that we know Monoid, and then we can define our own Monoid instances by analogy.

In fact, the concept of Monoid is not complicated, but the philosophy of functional programming is that you want to take small abstractions, put them together, and eventually make a larger abstraction, and build an extremely elegant system.

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 – Fun Monoid (Unit semigroup)

preface

Semigroup

Monoid (Unit semigroup)

define

combination

conditions

Some useful monoids

Middleware

Order

Array

Writer Monad

The tail

Functional Programming – Fun Monoid (Unit semigroup)

preface

Semigroup

Monoid (Unit semigroup)

define

combination

conditions

Some useful monoids

Middleware

Order

Array

Writer Monad

The tail

Related Posts

RxSwift (II) Sequence core logic analysis

Awk for occasional use

IOS signature mechanism