19
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

SwiftでHigher Kinded Polymorphismを実現する

Last updated at Posted at 2017-08-09

はじめに

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には、たとえばArraySetなど何か型パラメータを取るような型パラメータを用いる。しかしSwiftはこのような何か型パラメータを取るような型パラメータを書くことができず、次のようにコンパイルエラーとなる。

Cannot specialize non-generic type 'Self.F'

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

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

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

SwiftでHigher Kinded Polymorphism

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

App.swift
class App<T, A> {
    var underlying: Any
    
    init(_ a: Any) {
        underlying = a
    }
}
Newtype.swift
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を高階に扱いたいときは次のようにする。

Array.swift
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>から関数injApp<ArrayConstructor, A>へ変換する
  • 任意の型Aについて、App<ArrayConstructor, A>から関数prjArray<A>へ変換する

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

Tree.swift
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()))"
        }
    }
}

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

Tree.swift
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を次のように定義する。

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

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

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

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

Functor.swift
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()
    }
}

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

main.swift
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を実現することができた。今回はArrayTreeのような型パラメータを1つ取るような型のみを例に挙げたが、たとえばEitherのような2つの型パラメータを取る型もクラスAppを入れ子にしてNewtype2を作ることで同様に実装できると考えられる。これらによってより高度なプログラムを書くことができればいいと思う。

参考文献

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

19
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
19
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?