34
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

updated at

Organization

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の2つに分けて取り出すことができます。

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等の関数を定義していきました。
ただ使うだけではなく、実際に自分で書いていじってみるとより理解が深まると思います。 :wink:

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
34
Help us understand the problem. What are the problem?