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



※ 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)](https://www.amazon.co.jp/%E9%96%A2%E6%95%B0%E5%9E%8B%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E5%9F%BA%E7%A4%8E-JavaScript%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E5%AD%A6%E3%81%B6-%E7%AB%8B%E5%B7%9D%E5%AF%9F%E7%90%86/dp/4865940596)」から

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


# 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] (https://gist.github.com/ysn551/b02d8568191cbb6de001490aebc9e4ea#file-class_list-swift)

```
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](https://gist.github.com/ysn551/b02d8568191cbb6de001490aebc9e4ea#file-enum_list-swift)

```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](https://www.amazon.co.jp/%E9%96%A2%E6%95%B0%E5%9E%8B%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E5%9F%BA%E7%A4%8E-JavaScript%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E5%AD%A6%E3%81%B6-%E7%AB%8B%E5%B7%9D%E5%AF%9F%E7%90%86/dp/4865940596)
学術的な支点からも解説されているので、とても勉教になりました。
  
**単方向リストの実装について:**

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