Swiftで関数型のデータ構造を作ってみます。
関数型データの構造は永続的であるという特徴があります。なので更新する際には既存のデータを破壊するのではなく新しいオブジェクトを作ります。Enumを使ってこのリストを作ってみます。
consはリストの先頭、nilはリストの終端を表します。
enum List<T: Equatable> {
case `nil`
indirect case cons(T, List<T>)
}
またリストは比較できると便利なのでEquatableを満たすようにします。
extension List: Equatable {
static func ==(lhs: List, rhs: List) -> Bool {
switch (lhs, rhs) {
case (.`nil`, .`nil`):
return true
case (.cons(let h, let t), .cons(let h1, let t1)):
return h == h1 && t == t1
default:
return false
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
let list1 = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
let list2 = List<Int>.cons(1, .cons(2, .cons(3, .cons(4, .`nil`))))
list == list1
list == list2
CustomStringConvertible を満たすようにすると出力が見やすくなるのでやっておきましょう
extension List: CustomStringConvertible {
var description: String {
switch self {
case .`nil`:
return "nil"
case .cons(let head, let tail):
return "\(head),\(tail)"
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
print(list)
リストなら以下のような要素の数を取得できるようにしたいですね。やってみましょう。
extension List {
var isEmpty: Bool {
switch self {
case .`nil`:
return true
case .cons:
return false
}
}
var head: T? {
switch self {
case .`nil`:
return nil
case .cons(let head, _):
return head
}
}
var tail: List<T>? {
switch self {
case .`nil`:
return nil
case .cons(_, let tail):
return tail
}
}
var length: Int {
switch self {
case .`nil`:
return 0
case .cons(_, let tail):
return 1 + tail.length
}
}
var last: T? {
switch self {
case .`nil`:
return nil
case .cons(let head, .`nil`):
return head
case .cons(_, let tail):
return tail.last
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
list.isEmpty
list.head
list.tail
list.length
list.last
要素の追加、削除はできて当然ですね。これも実装していきます。
だいたいやっている事は同じです。リストの要素を辿っていき該当の要素に対して処理を行っています。
extension List {
func add(value: T) -> List<T> {
switch self {
case .`nil`:
return List<T>.cons(value, .`nil`)
case .cons(let head, let tail):
return .cons(head, tail.add(value: value))
}
}
func remove(index: Int) -> List<T> {
switch (self, index) {
case (.`nil`, _):
return self
case (.cons(_, let tail), 0):
return tail
case (.cons(let head, let tail), let index):
return .cons(head, tail.remove(index: index - 1))
}
}
func update(index: Int, value: T) -> List<T> {
switch (self, index) {
case (.`nil`, _):
return self
case (.cons(_, let tail), 0):
return .cons(value, tail)
case (.cons(let head, let tail), let index):
return .cons(head, tail.update(index: index - 1, value: value))
}
}
func append(list: List<T>) -> List<T> {
switch self {
case .`nil`:
return list
case .cons(let head, let tail):
return List.cons(head, tail.append(list: list))
}
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
list.add(value: 100)
list.remove(index: 1)
list.update(index: 0, value: 100)
list.append(list: list)
最後に高階関数を実装します。
extension List {
func foldr<R>(acc: R, f: (T,R) -> R) -> R {
switch self {
case .`nil`:
return acc
case .cons(let head, let tail):
return f(head, tail.foldr(acc: acc, f: f))
}
}
func foldl<R>(acc: R, f: (R,T) -> R) -> R {
switch self {
case .`nil`:
return acc
case .cons(let head, let tail):
return tail.foldl(acc: f(acc, head), f: f)
}
}
func map<R>(f: @escaping (T) -> R) -> List<R> {
return foldr(acc: List<R>.`nil`) { acc, list in
return List<R>.cons(f(acc), list)
}
}
func filter(f: @escaping (T) -> Bool) -> List<T> {
return foldr(acc: List<T>.`nil`, f: { acc, list in
if f(acc) {
return List<T>.cons(acc, list)
}
return list
})
}
func flatMap<R>(f: @escaping (T) -> List<R>) -> List<R> {
return foldr(acc: List<R>.`nil`, f: { acc, list in
return f(acc).append(list: list)
})
}
}
let list = List<Int>.cons(1, .cons(2, .cons(3, .`nil`)))
list.map { $0 * 10 }
list.filter { $0 % 2 == 0 }
list.flatMap { .cons($0, .cons($0, .`nil`)) }