Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
3
Help us understand the problem. What are the problem?

More than 3 years have passed since last update.

命令型プログラミングと関数型プログラミングによる単方向リスト

※ Swiftバージョン

swift-version.txt
Apple Swift version 4.0.2 (swiftlang-900.0.69.2 clang-900.0.38)
Target: x86_64-apple-macosx10.9

書いたこと

swiftは命令型プログラミングと関数型プログラミングの両方のパラダイムを持ち合わせるマルチパラダイム言語です。
上記はそれぞれクラス(or 構造体)と代数的データ型(enumのこと)を用いて各種のデータ構造を表すことが出来ることで見出すことも出来ます。
そこで単方向リストでそれぞれを実装し、そのメリット、デメリットを比較してみました。

命令型プログラミングと関数型プログラミングの違い

関数型プログラミングの基礎 JavaScriptを使って学ぶ (amazon)」から

  • 土台となっている数学モデルが異なる
    • 命令型プログラミング = チューリング・マシン
    • 関数型プログラミング = ラムダ計算
  • それぞれにおける計算の意味が異なる
    • 命令型プログラミング = 命令(状態の変更)を実行すること
    • 関数型プログラミング = 関数を呼び出して値を得ること

classとenumによる単方向リストの定義

※ Swiftのstructは再帰的な型の宣言が出来ないため、命令型プログラミングでの例としてclassを用いています。

class

class_list.swift
class List<T> {
    var head: Node<T>?
    var last: Node<T>?
    class Node<T> {
        let value: T
        var next: Node<T>? = nil
        init(_ value: T) {
            self.value = value
        }
    }
}

enum

enum_list.swift
enum List<T> {
    case empty
    indirect case node(T, List<T>)
}

classによる実装

gist

extension List {

   func append(_ newValue: T) {
        let newNode = Node(newValue)
        if self.head == nil {
            self.head = newNode
            self.last = self.head
        } else {
            self.last!.next = newNode
            self.last = self.last!.next
        }

    }

    func insert(_ newValue: T, at index: Int) {
        let newNode = Node(newValue)
        if index == 0 {
            let oldHead = self.head
            self.head = newNode
            newNode.next = oldHead
            if self.last == nil {
                self.last = self.head
            }
        } else {
            var node = self.head
            for _ in 1..<index {
                node = node?.next
                if node == nil {
                    break
                }
            }

            let temp = node?.next
            node?.next = newNode
            newNode.next = temp

            if self.last === node {
                self.last = newNode
            }
        }
    }

    func remove(at idx: Int) {
        if self.head == nil {
            return
        } else if idx == 0 {
            let prevHead = self.head
            let next = self.head!.next
            self.head = next
            if self.last === prevHead {
                self.last = self.head
            }
        } else {
            var prev = self.head
            var node = self.head?.next
            for _ in stride(from: 1, to: idx, by: 1) {
                if node == nil || node?.next == nil {
                    prev = nil
                    node = nil
                    break
                }
                prev = node!
                node = node!.next
            }

            // delete node
            prev?.next = node?.next
            if self.last === node {
                self.last = node?.next
            }
        }
   }
}

enumによる実装

gist

List.swift
extension List {
   func appending(_ newElement: T) -> List<T> {
        switch self {
        case .empty:
            return .node(newElement, .empty)
        case .node(let value, let tail):
            return .node(value, tail.appending(newElement))
        }

    }

    func inserting(_ newElement: T, at index: Int) -> List<T> {
        switch self {
        case .empty:
            return .node(newElement, .empty)
        case .node(let value, let tail):
            if index == 0 {
                return .node(newElement, .node(value, tail))
            } else {
                return .node(value, tail.inserting(newElement, at: index-1))
            }
        }
    }


    func removing(at idx: Int) -> List<T> {
        switch self {
        case .empty:
            return .empty
        case .node(let value, let tail):
            if idx == 0 {
                return tail
            } else {
                return .node(value, tail.removing(at: idx-1))
            }
        }
    }

}

それぞれのメリットとデメリット

コード

  • enumの方がシンプル
  • classは状態の管理が大変だった(headとlast)

実行速度

  • classの方が圧倒的に速い

まとめ

classによる実装は、状態の管理(とくにlastを追随させること)が大変でしたが、実行速度は圧倒的にclassの方が早くなります。
また実装もメモリの状態をステップバイステップで変更していく感じで実装できるため、イメージしながら実装できました。
しかしながらenumによる実装は、状態を変更させていくのではなく、関数を呼び出していく感じになるため、状態の変更がイメージし辛く、そこが難しいと思いました。
また実行速度も大変遅くなるため、メモ化も合わせて行う必要があると思われます。

参考書籍 & サイト

命令型プログラミングと関数型プログラミングの違いについて:

関数型プログラミングの基礎 JavaScriptを使って学ぶ amazon
学術的な支点からも解説されているので、とても勉教になりました。

単方向リストの実装について:

swift-algorithm-club/LinkedList
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Linked%20List

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
3
Help us understand the problem. What are the problem?