swiftでmap、reduce、filter、flatMapを実装する

はじめに

Swiftでコードを書くのに便利な関数にmap、reduce、filterやflatMap等があります。
これらの使い方は2日目の記事( http://qiita.com/mo_to_44/items/cf83b22cb34921580a52 )で詳しく解説されているので説明しません。
map等の関数の中身はどのようになっているんだろう？というところに触れていきます。

Swiftを書いている大多数の人(自分も含め)は、あくまでもiOS開発をするためにSwiftを使っていて、関数型的な書き方が好きだからSwiftを選んでいるわけではないと思うので、こういうのも需要があるかなと思いました。

参考書

この記事で出てくるコードやその他の説明は「Scala関数型デザイン＆プログラミング」( http://www.amazon.co.jp/dp/4844337769 )という本の序盤で出てくるものをswiftに変換したり切り貼りしたものが主です。scalaがわからない自分でもある程度読めたので、興味がある方はscalaに臆せず読むことをおすすめします。

アフィリンクではありません。念のため

リスト

定義

まずはリストの定義から始めていきます。
indirect修飾子という修飾子がSwift2系から加わり、再帰的なenumを定義出来るようになりました。

indirect enum List<A> {
    case Cons(A, List<A>)
    case Nil
}

Nilはリストの終端を表します。

let list1: List<Double> = List.Nil
let list2 = List.Cons(1, .Nil)
let list3 = List.Cons("a", List.Cons("b" , .Nil))

上記の様にリストが作れます。
SwiftのArrayはもっと複雑になっていると思いますが、とりあえずこれで、単方向リストが作れました。

便利のために以下のような関数を宣言しておきます

func cons<A>(head: A, _ tail: List<A>) -> List<A> {
    return List.Cons(head, tail)
}

これで先ほどの記述を書き換えます。

let _list1: List<Double> = List.Nil
let _list2 = cons(1, .Nil)
let _list3 = cons("a", cons("b", .Nil))

以下ではList.Consではなく関数consを使っていきます。

Arrayと自作Listの比較

// array
[1, 2, 3]
// 自作List
cons(1, cons(2, cons(3, .Nil)))

パターンマッチ

自作したリストの中身を取り出すにはパターンマッチを使います。

let ints = cons(1, cons(2, cons(3, .Nil)))
switch ints {
case .Nil: break
case let .Cons(x, xs):
    print(x) // => "1\n"
    print(xs) // => "Cons(2, List<Swift.Int>.Cons(3, List<Swift.Int>.Nil))\n"
}

ListはConsかNilのどちらかです。
Nilの時はListの終端を表すので値がありません。
Consの時はListの途中であり、その中身をListの先頭の値と、残りのListの２つに分けて取り出すことができます。

map

早速ですがmapを作っていきます。

swiftのArrayではよくこんな感じに使われていると思います。

[1, 2, 3].map { $0 + 1 } // => [2, 3, 4]
[1, 2, 3].map { $0 * 2 } // => [2, 4, 6]

mapでは要素それぞれに引数で渡した変換をかけていきます。

目標は

map(cons(1, cons(2, cons(3, .Nil)))) { $0 + 1 } // => cons(2, cons(3, cons(4, .Nil)))
map(cons(1, cons(2, cons(3, .Nil)))) { $0 * 2 } // => cons(2, cons(4, cons(6, .Nil)))

のような自作リストに使えるmapという関数を作ることです。

まず、この

• それぞれに1を足す
• それぞれに2を掛ける

という2つの操作を先ほどのパターンマッチを使って実装してみます。

let ints = cons(1, cons(2, cons(3, .Nil)))
func addOne(l: List<Int>) -> List<Int> {
    switch l {
    case .Nil: return .Nil
    case let .Cons(x, xs): return cons(x + 1, addOne(xs))
    }
}
addOne(ints) // => cons(2, cons(3, cons(4, .Nil)))

func double(l: List<Int>) -> List<Int> {
    switch l {
    case .Nil: return .Nil
    case let .Cons(x, xs): return cons(x * 2, double(xs))
    }
}

double(ints) // => cons(2, cons(4, cons(6, .Nil)))

このaddOne関数とdouble関数はそれぞれ、Listの中身を先頭から1つづつ取っていって変換を行い、Listに詰め直すということを行っています。

変換の内容が+1か*2の違いしかありません。

この変換の内容を外から渡せるようにしたのがmapです。

func map<A, B>(l: List<A>, _ f: A -> B) -> List<B> {
    switch l {
    case .Nil: return .Nil
    case let .Cons(x, xs): return cons(f(x), map(xs, f))
    }
}

map(cons(1, cons(2, cons(3, .Nil)))) { $0 + 1 } // => cons(2, cons(3, cons(4, .Nil)))
map(cons(1, cons(2, cons(3, .Nil)))) { $0 * 2 } // => cons(2, cons(4, cons(6, .Nil)))

fを外から渡すことにより、要素それぞれにいろんな変換を掛けることができます。

reduce

Arrayのreduceはこのように使われます。

[1, 2, 3].reduce(0) { $0 + $1 } // => 6
[1, 2, 3].reduce(1) { $0 * $1 } // => 6

要素同士を順番に計算していき、一つの計算結果を返します。

上に書いた

• 要素同士を足しあわせて1つにする
• 要素同士を掛けあわせて1つにする

という2つの操作を先ほどのパターンマッチを使って実装してみます。

func sum(ints: List<Int>) -> Int {
    switch ints {
    case .Nil: return 0
    case let .Cons(x, xs): return x + sum(xs)
    }
}

func product(ints: List<Int>) -> Int {
    switch ints {
    case .Nil: return 1
    case let .Cons(x, xs): return x * product(xs)
    }
}

このsum関数とproduct関数とでは、Nilの時の値と要素同士の演算の2箇所以外が共通です。
なので、この2つを引数にして外から渡すようにしてあげるとreduce関数を作ることができます。

func reduce<A, B>(l: List<A>, _ z: B, _ f: (A,B) -> B) -> B {
    switch l {
    case .Nil: return z
    case let .Cons(x, xs): return f(x, reduce(xs, z, f))
    }
}
reduce(cons(1, cons(2, cons(3, .Nil))), 0){ $0 + $1 } // => 6
reduce(cons(1, cons(2, cons(3, .Nil))), 0){ $0 * $1 } // => 6

ちなみにmapもreduceを使って表現できます。

func map2<A, B>(l: List<A>, _ f: A -> B) -> List<B> {
    return reduce(l, List.Nil){ cons(f($0.0), $0.1) }
}

filter

swiftのArrayでの例です。

[1, 2, 3].filter { $0 > 1 } // => [2, 3]

引数で渡した関数がtrueを返す要素だけを残した新たなArrayを作ります。

Listにおいて、パターンマッチを使って書くと以下の様になります。

func filter<A>(l: List<A>, _ f: A -> Bool) -> List<A> {
    switch l {
    case .Nil: return .Nil
    case let .Cons(x, xs):
        return  f(x) ? cons(x, filter(xs, f)) : filter(xs, f)
    }
}
filter(cons(1, cons(2, cons(3, .Nil)))) { $0 > 1 } // => cons(2, cons(3, .Nil))

f(x)の結果によって、Listの先頭要素を残すか残さないか分岐しています。

flatMap

swiftのArrayの例です

[1, 2, 3].flatMap { [$0, $0] } // => [1, 1, 2, 2, 3, 3]

flatMapではArrayの要素それぞれに変換を行い、それらを一つのArrayに入れて返します。

mapと比べるとわかりやすいですね。

[1, 2, 3].map { [$0, $0] } // => [[1, 1], [2, 2], [3, 3]]
[1, 2, 3].flatMap { [$0, $0] } // => [1, 1, 2, 2, 3, 3]

flatMapでは要素それぞれを変換するmapの操作に加えて、2重のListを一つのListにまとめる操作が必要です。

2つのListを連結する関数appendは次のように書くことができます。

func append<A>(a1: List<A>, _ a2: List<A>) -> List<A> {
    switch a1 {
    case .Nil: return a2
    case let .Cons(x, xs): return cons(x, append(xs, a2))
    }
}

このappendを使って2重のListを1つのListにまとめる関数concatはこのように書けます。

func concat<A>(l: List<List<A>>) -> List<A> {
    return reduce(l, List.Nil){ append($0.0, $0.1) }
}

flatMapはmapとconcatを組み合わせて書くことができます。

func flatMap<A, B>(l: List<A>, _ f: A -> List<B>) -> List<B> {
    return concat(map(l){ f($0) })
}
flatMap(cons(1, cons(2, .Nil))) { cons($0, cons($0, List.Nil)) } // => cons(1, cons(1, cons(2, cons(2, .Nil))))

Optional

定義

optionalは以下のようにenumで定義できます。
値があればその値を持った.Some、値がなければ.Nilになります。

enum Optional<A> {
    case Some(A)
    case None
}

ちなみに先日公開されたswiftのコードでも実際にenumで定義されていました。
https://github.com/apple/swift/blob/master/stdlib/public/core/Optional.swift

map, filter, flatMap

Optionalのmap、filter、flatMapは以下のように定義できます。

extension Optional {
    func map<B>(f: A -> B) -> Optional<B> {
        switch self {
        case .None: return .None
        case let .Some(value): return .Some(f(value))
        }
    }
    
    func filter(f: A -> Bool) -> Optional<A> {
        switch self {
        case .None: return .None
        case let .Some(value): return f(value) ? .Some(value) : .None
        }
    }
    
    func flatMap<B>(f: A -> Optional<B>) -> Optional<B> {
        switch self {
        case .None: return .None
        case let .Some(value): return f(value)
        }
    }
}
let optionalInt = Optional.Some(2)
optionalInt.map { $0 + 1 } // => Some(3)
optionalInt.filter { $0 > 1 } // => Some(2)
optionalInt.filter { $0 > 2 } // => None
optionalInt.flatMap { Optional.Some($0 * 2) } // Some(4)

おわりに

ListとOptinalについて、型の定義から始めてmap,filter等の関数を定義していきました。
ただ使うだけではなく、実際に自分で書いていじってみるとより理解が深まると思います。