SwiftでHigher Kinded Polymorphismを実現する

はじめに

Java で higher kinded polymorphism を実現するを読み、これをSwiftに移植すれば何かの役に立つかもしれないと考えた。この記事の完全なソースコードはGitHubの次のリポジトリから入手できる。

この記事を読んで疑問や改善点がある場合には、気軽にコメントなどで教えて欲しい。

Higher Kinded Polymorphismとは？

Higher Kinded Polymorphismは日本語で高階多相などと呼ばれるもので、例えばSwiftで次のようなプロトコルFunctor1を作成したいとする。

protocol Functor {
    associatedtype F
    associatedtype E
    
    func mapF<B>(_ f: (E) -> B) -> F<B>
}

型パラメータFには、たとえばArrayやSetなど何か型パラメータを取るような型パラメータを用いる。しかしSwiftはこのような何か型パラメータを取るような型パラメータを書くことができず、次のようにコンパイルエラーとなる。

Cannot specialize non-generic type 'Self.F'

たとえばプログラム言語Scalaではこれをこのように書くことができる。

trait Functor {
  type F[_]
  type E
  
  def mapF[B](f: E => B): F[B]
}

このように、型パラメータが何かの型パラメータを取ることで、型パラメータFがArrayやSetなど何であっても動作するような抽象的な関数を定義できるようになる。このような多相性のことをHigher Kinded Polymorphismと呼ぶ。

SwiftでHigher Kinded Polymorphism

まず、次のようなクラスAppとプロトコルNewtype1を作る。

class App<T, A> {
    var underlying: Any
    
    init(_ a: Any) {
        underlying = a
    }
}
protocol Newtype1 {
    associatedtype T
    associatedtype A
    
    func inj() -> App<T, A>
}

extension Newtype1 {
    func inj() -> App<T, A> {
        return App(self)
    }
}

クラスAppは2つの型パラメータを取り、コンストラクターに渡された引数をメンバ変数underlyingに格納しておく。また、プロトコルNewtype1は関数injを提供し、これはApp<T, A>への変換を表す。 これらを利用してたとえばArrayを高階に扱いたいときは次のようにする。

class ArrayConstructor { }

extension Array: Newtype1 {
    typealias T = ArrayConstructor
    typealias A = Element
}

extension App where T: ArrayConstructor {
    func prj() -> Array<A> {
        return (self.underlying as! Array<A>)
    }
}

このようにすることで、次の2つの操作が可能となる。

  • 任意の型Aについて、Array<A>から関数injでApp<ArrayConstructor, A>へ変換する
  • 任意の型Aについて、App<ArrayConstructor, A>から関数prjでArray<A>へ変換する

このようにすることで、今まで具体的になっていない型Arrayを型パラメータとして渡すことはできなかったが、クラスAppとArrayConstructorを利用してApp<ArrayConstructor, A>という形で渡せるようになった。 同様に二分木を表すTreeについても次のように作ることができる。まずはTreeを次のように定義する。

indirect enum Tree<Element> {
    case Leaf
    case Node(l: Tree<Element>, a: Element, r: Tree<Element>)
    
    func toString() -> String {
        switch self {
        case .Leaf:
            return "L"
        case let .Node(l, a, r):
            return "N(\(l.toString()), \(a), \(r.toString()))"
        }
    }
}

そして次のようにエクステンションを定義する。

class TreeConstructor { }

extension Tree: Newtype1 {
    typealias T = TreeConstructor
    typealias A = Element
}

extension App where T: TreeConstructor {
    func prj() -> Tree<A> {
        return (self.underlying as! Tree<A>)
    }
}

これらを利用して最初に例として挙げたプロトコルFunctorを作成する。まずプロトコルFunctorを次のように定義する。

protocol Functor {
    associatedtype F
    associatedtype E
    
    func mapF<B>(_ f: (E) -> B) -> App<F, B>
}

最初の例と異なり、Functorは最後の結果をApp<F, B>という型で返すようしている。 型Arrayの値がプロトコルFunctorの関数mapFが利用できるように、次のようなコードを実装する。

extension Array: Functor {
    typealias F = ArrayConstructor
    typealias E = Element
    
    func mapF<B>(_ f: (E) -> B) -> App<F, B> {
        return self.map(f).inj()
    }
}

Treeの場合はやや複雑だが次のようになる。

extension Tree: Functor {
    typealias F = TreeConstructor
    typealias E = Element
    
    private func loop<B>(_ x: Tree<E>, _ f: (E) -> B) -> Tree<B> {
        switch x {
        case .Leaf:
            return .Leaf
        case let .Node(l, a, r):
            return Tree<B>.Node(l: loop(l, f), a: f(a), r: loop(r, f))
        }
    }
    
    func mapF<B>(_ f: (E) -> B) -> App<F, B> {
        return loop(self, f).inj()
    }
}

最後に、本当にArrayやTreeから関数mapFが呼び出せるのかを確認する。

print( [1, 2, 3, 4, 5].mapF({ (x: Int) -> Int in return x + 1 }).prj() )

let tree: Tree<Int> =
    .Node(
        l: .Node(l: .Leaf, a: 1, r: .Leaf),
        a: 2,
        r: .Node(l: .Leaf, a: 3, r: .Leaf)
    )

print( tree.mapF({ (x: Int) -> Int in return x + 1 }).prj().toString() )

これは次の2つの結果を求める。

  • Intの配列の全ての要素を$+1$した配列を表示する
  • Intの二分木の全ての要素を$+1$した二分木を表示する

結果は次のようになる。

[2, 3, 4, 5, 6]
N(N(L, 2, L), 3, N(L, 4, L))

このように、正しく関数mapFが実行できていることが分かる。

まとめ

このようにしてSwiftでもHigher Kinded Polymorphismを実現することができた。今回はArrayやTreeのような型パラメータを1つ取るような型のみを例に挙げたが、たとえばEitherのような2つの型パラメータを取る型もクラスAppを入れ子にしてNewtype2を作ることで同様に実装できると考えられる。これらによってより高度なプログラムを書くことができればいいと思う。

参考文献

  1. Functorは関数型界隈で意味のある言葉だが、この記事ではFunctorが何を意味するのかを知っていなくてもよい。↩

コメント

コメントを投稿