発狂マニアック「ビット演算が入ってないやん」

どうも, 順序数の上にビット演算を定義できないかなとか日々生産性のない妄想を続けるタイプの別に数学が得意でもないたぬきです。

前置き省略。

```math
\def\coloneqq{\mathrel{\mathop:}\mathrel{\mkern-1.2mu}=}
\def\notni{\mathrel{\not \ni}}
\def\Brace#1{\left\{{#1}\right\}}
\def\Set#1#2{\left\{{#1} \; \middle| \; {#2}\right\}}
\def\bit{\mathbin{\text{bit}}}
\def\inc{\mathbin{\text{inc}}}
\def\shl{\mathbin{\text{shl}}}
\def\shr{\mathbin{\text{shr}}}
```

## Swift で遊びやすくなったので大好きなコードを写経してた

ヒャッホウ, Windows で Swift のツールチェインが提供されたぜ!

選民思想に染まった哀れな連中が「マー, Microsoft 製の野蛮なオモチャで Swift を使われるなんてブランドに傷がつくザマスわ」とか言ってそうな気がするが使えるんだからこっちの勝ちだぜ。 ズール皇帝こそが正義だ。

というわけで, @taketo1024 さんの [Swift でノイマン自然数を構成するコード](https://qiita.com/taketo1024/items/2ab856d21bf9b9f30357)を写経しよう。 いかんせん Swift が不安定だった時期のコードなのでそのまま写しても動かない部分が多いけど, 頑張ろう。

```swift
import Foundation

postfix operator +
postfix operator -

struct N {
    private let val: [Any]
}

extension N {
    private init(_ val: [Any]) {
        self.val = val
    }

    static var zero: N {
        return N([])
    }

    static postfix func +(n: N) -> N {
        return N(n.val + [n.val])
    }
    
    static postfix func -(n: N) -> N {
        if n.val.isEmpty {
           assertionFailure("0- doesn't exist.")
        }
        return N(n.val.last as! [Any])
    }

    static func +(n: N, m: N) -> N {
        if m.val.isEmpty {
            return n
        } else {
            return (n + m-)+
        }
    }

    static func *(n: N, m: N) -> N {
        if m.val.isEmpty {
            return N.zero
        } else {
            return (n * m-) + n
        }
    }
}

extension N: CustomStringConvertible {
    var description: String {
        return "\(val.count)"
    }
}

extension N: Equatable {
    static func ==(n: N, m: N) -> Bool {
        if (n.val.isEmpty && m.val.isEmpty) {
            return true
        } else if (n.val.isEmpty || m.val.isEmpty) {
            return false
        } else {
            return (n- == m-)
        }
    }
}

extension N: ExpressibleByIntegerLiteral {
    init(integerLiteral value: IntegerLiteralType) {
        var n = N.zero
        for i in 0..<value {
            n = n+
        }
        self.val = n.val
    }
}

```

こんな感じに完成した。 構造と実装, 適合を分けるのが Rust 流だ。 Rust も勉強中だろうがお前!

```swift
let a: N = 2
let b: N = 3

print("\(a + b)")
print("\(a * b)")

```

```
5
6

```

完璧じゃんね。 先人の功績は偉大だなぁ。

## ビット演算が入ってないやん, どうしてくれんのこれ

アイエエ狂人!!

というわけでビット演算を実装していく。

まず下準備として冪を実装。

```swift
extension N {
    func pow(_ m: N) -> N {
        if m.val.isEmpty {
            return N.zero+
        } else {
            return self.pow(m-) * self
        }
    }
}

```

```math
n^m \coloneqq
\begin{cases}
    \Brace{\varnothing} & \text{($m = \varnothing$)} \\
    n^{\hat{m}} \times n & \text{($m = \hat{m}^+$)}
\end{cases}
```

とくにおかしなこともありませんね。

つづいて「自然数の集合」つまり`Set<N>`について考えたいので, `N`を`Hashable`に適合。

```swift
extension N: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.val.count)
    }
}

```

ハッシュ関数の定義もずいぶんと楽になったなぁ。

ここで写像 $\inc: 2^\mathbb{N} \to 2^\mathbb{N}$ を定義しておく。

```swift
extension N {
    static func inc(_ s: Set<N>) -> Set<N> {
        if s.contains(N.zero) {
            return Set(inc(Set(s.subtracting([N.zero]).map {$0-})).map {$0+})
        } else {
            return s.union([N.zero])
        }
    }
}

```

```math
\inc(S) \coloneqq
\begin{cases}
    S \cup \Brace{\varnothing} & \text{($S \notni \varnothing$)} \\
    \Brace{n^+ \mid n \in \inc(\Brace{\bigcup n \mid n \in S \setminus \Brace{\varnothing}})} & \text{($S \ni \varnothing$)}
\end{cases}
```

うわあなんだこれは……。

次のようなふたつの写像 $\shl, \shr: 2^\mathbb{N} \to 2^\mathbb{N}$ を定義するとわかりやすくなる。

```math
\begin{aligned}
    \shl(S) &\coloneqq \Brace{n^+ \mid n \in S} \\
    \shr(S) &\coloneqq \Set{\bigcup n}{n \in S \setminus \Brace{\varnothing}}
\end{aligned}
```

つまり中身を全部 $1$ 増やしたり, $1$ 減らしたりする写像ということ。

```math
\inc(S) \coloneqq
\begin{cases}
    S \cup \Brace{\varnothing} & \text{($S \notni \varnothing$)} \\
    \shl \circ \inc \circ \shr(S) & \text{($S \ni \varnothing$)}
\end{cases}
```

だいぶスッキリした。 ~~ところでなんで`Set<T>#map`の返り値が`Array<T>`なんですか。~~ $\inc$ を定義したのは前に書いた[これ](https://qiita.com/BlueRayi/items/47ac5a7ace22a9ccbd24)の

```math
\bit(x) \coloneqq
\begin{cases}
    \varnothing & \text{($x = 0$)} \\
    \bit(\hat{x}) \cup \Brace{m} \setminus \Brace{n \in \mathbb{N} \mid n < m} \text{, where $m = \min(\bit(\hat{x})^c)$} & \text{($x = \hat{x}^+)$} 
\end{cases}
```

に出てくる $m$ を求めなくてもよくするため。 $\inc$ を使えば

```swift
extension N {
    static func bit(_ n: N) -> Set<N> {
        if n.val.isEmpty {
            return Set()
        } else {
            return inc(bit(n-))
        }
    }
}

```

```math
\bit(n) \coloneqq
\begin{cases}
    \varnothing & \text{($n = \varnothing$)} \\
    \inc \circ \bit(\hat{n}) & \text{($n = \hat{n}^+$)}
\end{cases}
```

と再帰的に定義できる。

つづいて $\bit$ の逆写像 $\bit^{-1}$ を定義する。

```swift
extension N {
    static func invBit(_ s: Set<N>) -> N {
        return s.reduce(N.zero) {$0 + (N.zero+)+.pow($1)}
    }
}

```

```math
\bit^{-1}(S) = \sum_{n \in S} 2^n
```

とくに難しいこともない。

ここまで用意できれば`Set`に最初から入っている集合演算を利用すればビット演算の実装は簡単である。

```swift
extension N {
    static func |(n: N, m: N) -> N {
        return invBit(bit(n).union(bit(m))) // 集合の合併
    }

    static func &(n: N, m: N) -> N {
        return invBit(bit(n).intersection(bit(m))) // 集合の交叉
    }

    static func ^(n: N, m: N) -> N {
        return invBit(bit(n).symmetricDifference(bit(m))) // 集合の対称差
    }
}

```

```swift
let a: N = 2
let b: N = 3

print("\(a + b)")
print("\(a * b)")
print("\(a ^ b)")

```

```
5
6
1

```

成し遂げたぜ。

## 最終的なコードの全体図

こちら 14 万 3000 円となっております。

```swift
import Foundation

postfix operator +
postfix operator -

struct N {
    private let val: [Any]
}

extension N {
    private init(_ val: [Any]) {
        self.val = val
    }

    static var zero: N {
        return N([])
    }

    static postfix func +(n: N) -> N {
        return N(n.val + [n.val])
    }
    
    static postfix func -(n: N) -> N {
        if n.val.isEmpty {
           assertionFailure("0- doesn't exist.")
        }
        return N(n.val.last as! [Any])
    }

    static func +(n: N, m: N) -> N {
        if m.val.isEmpty {
            return n
        } else {
            return (n + m-)+
        }
    }

    static func *(n: N, m: N) -> N {
        if m.val.isEmpty {
            return N.zero
        } else {
            return (n * m-) + n
        }
    }

    static func |(n: N, m: N) -> N {
        return invBit(bit(n).union(bit(m)))
    }

    static func &(n: N, m: N) -> N {
        return invBit(bit(n).intersection(bit(m)))
    }

    static func ^(n: N, m: N) -> N {
        return invBit(bit(n).symmetricDifference(bit(m)))
    }

    func pow(_ m: N) -> N {
        if m.val.isEmpty {
            return N.zero+
        } else {
            return self.pow(m-) * self
        }
    }
    
    static func inc(_ s: Set<N>) -> Set<N> {
        if s.contains(N.zero) {
            return Set(inc(Set(s.subtracting([N.zero]).map {$0-})).map {$0+})
        } else {
            return s.union([N.zero])
        }
    }

    static func bit(_ n: N) -> Set<N> {
        if n.val.isEmpty {
            return Set()
        } else {
            return inc(bit(n-))
        }
    }

    static func invBit(_ s: Set<N>) -> N {
        return s.reduce(N.zero) {$0 + (N.zero+)+.pow($1)}
    }
}

extension N: CustomStringConvertible {
    var description: String {
        return "\(val.count)"
    }
}

extension N: Equatable {
    static func ==(n: N, m: N) -> Bool {
        if (n.val.isEmpty && m.val.isEmpty) {
            return true
        } else if (n.val.isEmpty || m.val.isEmpty) {
            return false
        } else {
            return (n- == m-)
        }
    }
}

extension N: ExpressibleByIntegerLiteral {
    init(integerLiteral value: IntegerLiteralType) {
        var n = N.zero
        for i in 0..<value {
            n = n+
        }
        self.val = n.val
    }
}

extension N: Hashable {
    func hash(into hasher: inout Hasher) {
        hasher.combine(self.val.count)
    }
}

```