Last active
July 16, 2017 22:17
-
-
Save BenchR267/3cdd30145326f1fff55b4263f24995fd to your computer and use it in GitHub Desktop.
'Simple' implementation of a single linked list in Swift
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| indirect enum List<T>: CustomStringConvertible { | |
| case empty | |
| case cons(T, List<T>) | |
| init(_ values: T...) { | |
| self = List(values) | |
| } | |
| init<U: Sequence>(_ values: U) where U.Element == T { | |
| self = values.reversed().reduce(.empty) { $0.prepend($1) } | |
| } | |
| func prepend(_ element: T) -> List<T> { | |
| switch self { | |
| case .empty: return .cons(element, .empty) | |
| case let .cons(head, tail): return .cons(element, tail.prepend(head)) | |
| } | |
| } | |
| func append(_ element: T) -> List<T> { | |
| switch self { | |
| case .empty: return self.prepend(element) | |
| case let .cons(head, tail): return .cons(head, tail.append(element)) | |
| } | |
| } | |
| func prepend(_ elements: List<T>) -> List<T> { | |
| return elements.reduce(self) { $0.prepend($1) } | |
| } | |
| func append(_ elements: List<T>) -> List<T> { | |
| return elements.reduce(self) { $0.append($1) } | |
| } | |
| var isEmpty: Bool { | |
| guard case .empty = self else { | |
| return false | |
| } | |
| return true | |
| } | |
| var head: T? { | |
| guard case let .cons(head, _) = self else { | |
| return nil | |
| } | |
| return head | |
| } | |
| var tail: List<T> { | |
| guard case let .cons(_, tail) = self else { | |
| return .empty | |
| } | |
| return tail | |
| } | |
| var count: Int { | |
| switch self { | |
| case .empty: return 0 | |
| case let .cons(_, tail): return 1 + tail.count | |
| } | |
| } | |
| subscript(index: Int) -> T { | |
| assert(index >= 0) | |
| switch self { | |
| case .empty: fatalError("index out of bounds") | |
| case let .cons(head, tail): | |
| if index == 0 { | |
| return head | |
| } else { | |
| return tail[index - 1] | |
| } | |
| } | |
| } | |
| func map<U>(_ f: (T) throws -> U) rethrows -> List<U> { | |
| switch self { | |
| case .empty: return .empty | |
| case let .cons(head, tail): return .cons(try f(head), try tail.map(f)) | |
| } | |
| } | |
| func flatMap<U>(_ f: (T) throws -> List<U>) rethrows -> List<U> { | |
| switch self { | |
| case .empty: return .empty | |
| case let .cons(head, tail): | |
| return try f(head).append(tail.flatMap(f)) | |
| } | |
| } | |
| func filterMap<U>(_ f: @escaping (T) throws -> U?) rethrows -> List<U> { | |
| switch self { | |
| case .empty: return .empty | |
| default: return try foldRight(List<U>.empty) { c, s in | |
| guard let n = try f(c) else { | |
| return s | |
| } | |
| return s.prepend(n) | |
| } | |
| } | |
| } | |
| func reduce<U>(_ initial: U, f: (U, T) throws -> U) rethrows -> U { | |
| switch self { | |
| case .empty: return initial | |
| case let .cons(head, tail): return try tail.reduce(f(initial, head), f: f) | |
| } | |
| } | |
| func foldRight<U>(_ initial: U, f: (T, U) throws -> U) rethrows -> U { | |
| switch self { | |
| case .empty: return initial | |
| case let .cons(head, tail): return try f(head, tail.foldRight(initial, f: f)) | |
| } | |
| } | |
| func reversed() -> List<T> { | |
| return reduce(List.empty, f:{ $0.prepend($1)}) | |
| } | |
| func toArray() -> [T] { | |
| return reduce([T]()) { s, c in | |
| return s + [c] | |
| } | |
| } | |
| var description: String { | |
| return "List(" + map({String(describing: $0)}).joined(", ") + ")" | |
| } | |
| } | |
| extension List where T == String { | |
| func joined(_ separator: String) -> String { | |
| switch self { | |
| case .empty: return "" | |
| case let .cons(head, tail): | |
| if tail.isEmpty { | |
| return head | |
| } else { | |
| return head + separator + tail.joined(separator) | |
| } | |
| } | |
| } | |
| } | |
| extension List where T: Equatable { | |
| func equal(rhs: List<T>) -> Bool { | |
| switch (self, rhs) { | |
| case (.empty, .empty): return true | |
| case (.empty, .cons(_, _)), (.cons(_, _), .empty): return false | |
| case let (.cons(head1, tail1), .cons(head2, tail2)): | |
| return (head1 == head2) && tail1.equal(rhs: tail2) | |
| } | |
| } | |
| static func ==(lhs: List<T>, rhs: List<T>) -> Bool { | |
| return lhs.equal(rhs: rhs) | |
| } | |
| } | |
| infix operator >>= | |
| func >>=<T, U>(lhs: List<T>, rhs: (T) -> List<U>) -> List<U> { | |
| return lhs.flatMap(rhs) | |
| } | |
| infix operator >> | |
| func >><T>(lhs: List<T>, rhs: List<T>) -> List<T> { | |
| return lhs >>= {_ in rhs} | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment