Skip to content

Instantly share code, notes, and snippets.

@BenchR267

BenchR267/List.swift

Last active July 16, 2017 22:17
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save BenchR267/3cdd30145326f1fff55b4263f24995fd to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save BenchR267/3cdd30145326f1fff55b4263f24995fd to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. BenchR267 revised this gist Jul 16, 2017. 1 changed file with 11 additions and 1 deletion.
    12 changes: 11 additions & 1 deletion List.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -100,6 +100,16 @@ indirect enum List<T>: CustomStringConvertible {
    }
    }

    func filter(_ predicate: @escaping (T) -> Bool) -> List<T> {
    return reduce(List<T>.empty) { s, c in
    if predicate(c) {
    return s.prepend(c)
    } else {
    return s
    }
    }.reversed()
    }

    func reduce<U>(_ initial: U, f: (U, T) throws -> U) rethrows -> U {
    switch self {
    case .empty: return initial
    @@ -115,7 +125,7 @@ indirect enum List<T>: CustomStringConvertible {
    }

    func reversed() -> List<T> {
    return reduce(List.empty, f:{ $0.prepend($1)})
    return reduce(List.empty, f:{ $0.prepend($1) })
    }

    func toArray() -> [T] {
  2. BenchR267 revised this gist Jul 16, 2017. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions List.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -91,12 +91,12 @@ indirect enum List<T>: CustomStringConvertible {
    func filterMap<U>(_ f: @escaping (T) throws -> U?) rethrows -> List<U> {
    switch self {
    case .empty: return .empty
    default: return try reduce(List<U>.empty) { s, c in
    default: return try foldRight(List<U>.empty) { c, s in
    guard let n = try f(c) else {
    return s
    }
    return s.prepend(n)
    }.reversed()
    }
    }
    }

    @@ -107,10 +107,10 @@ indirect enum List<T>: CustomStringConvertible {
    }
    }

    func foldRight<U>(_ initial: U, f: (T, U) -> U) -> U {
    func foldRight<U>(_ initial: U, f: (T, U) throws -> U) rethrows -> U {
    switch self {
    case .empty: return initial
    case let .cons(head, tail): return f(head, tail.foldRight(initial, f: f))
    case let .cons(head, tail): return try f(head, tail.foldRight(initial, f: f))
    }
    }

  3. BenchR267 revised this gist Jul 16, 2017. 1 changed file with 5 additions and 0 deletions.
    5 changes: 5 additions & 0 deletions List.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -165,3 +165,8 @@ 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}
    }
  4. BenchR267 revised this gist Jul 16, 2017. 1 changed file with 14 additions and 2 deletions.
    16 changes: 14 additions & 2 deletions List.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -88,10 +88,22 @@ indirect enum List<T>: CustomStringConvertible {
    }
    }

    func reduce<U>(_ initial: U, f: (U, T) -> U) -> U {
    func filterMap<U>(_ f: @escaping (T) throws -> U?) rethrows -> List<U> {
    switch self {
    case .empty: return .empty
    default: return try reduce(List<U>.empty) { s, c in
    guard let n = try f(c) else {
    return s
    }
    return s.prepend(n)
    }.reversed()
    }
    }

    func reduce<U>(_ initial: U, f: (U, T) throws -> U) rethrows -> U {
    switch self {
    case .empty: return initial
    case let .cons(head, tail): return tail.reduce(f(initial, head), f: f)
    case let .cons(head, tail): return try tail.reduce(f(initial, head), f: f)
    }
    }

  5. BenchR267 revised this gist Jul 16, 2017. No changes.
  6. BenchR267 created this gist Jul 16, 2017.
    155 changes: 155 additions & 0 deletions List.swift
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,155 @@
    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 reduce<U>(_ initial: U, f: (U, T) -> U) -> U {
    switch self {
    case .empty: return initial
    case let .cons(head, tail): return tail.reduce(f(initial, head), f: f)
    }
    }

    func foldRight<U>(_ initial: U, f: (T, U) -> U) -> U {
    switch self {
    case .empty: return initial
    case let .cons(head, tail): return 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)
    }