Skip to content

Instantly share code, notes, and snippets.

@airspeedswift airspeedswift/list.swift
Last active Jun 18, 2018

Embed
What would you like to do?
indirect enum List as CollectionType
// A simple linked list using enums:
enum List<Element> {
case End
indirect case Node(Element, List<Element>)
func cons(x: Element) -> List<Element> {
return .Node(x, self)
}
}
extension List: ArrayLiteralConvertible {
init(arrayLiteral elements: Element...) {
self = elements.reverse().reduce(.End) {
$0.cons($1)
}
}
}
// conforming to SequenceType is easy
extension List: SequenceType {
func generate() -> AnyGenerator<Element> {
var current: List<Element> = self
return anyGenerator {
switch current {
case .End: return nil
case let .Node(x, next):
current = next
return x
}
}
}
}
// which gives plenty of useful extensions
let l: List = ["1","2","3"]
",".join(l)
l.contains("2")
l.flatMap { Int($0) }
// but not all, e.g. first, dropFirst
// so how can we make it a collection type?
// nodes ought to be useable as indices...
// successor is just the next node
extension List: ForwardIndexType {
func successor() -> List<Element> {
switch self {
case let .Node(_, next):
return next
case .End:
fatalError("cannot increment endIndex")
}
}
}
// here's the problem, ForwardIndex must be Equatable,
// so how to do this:
func ==<T>(lhs: List<T>, rhs: List<T>) -> Bool {
switch (lhs,rhs) {
case (.End,.End): return true
case (.End,.Node): return false
case (.Node,.End): return false
case (.Node,.Node):
// in the absence of indirect case identity,
// do something that probably deserves a ಠ_ಠ
return unsafeBitCast(lhs, UInt.self) == unsafeBitCast(rhs, UInt.self)
}
}
// this works _and_ is compatible with the value type aspects of enums,
// because you can't update enums in-place,
// so copying means the reference is the same:
let a = l
a == l // true (in the same sense a copied Array shortcuts == using the identity of its buffer)
// but changing the value changes the identity
var b = l
var c = l
a == b && b == c && c == a // true
b = l.cons("3")
c = ["1","2"]
a == b || b == c || c == a // false
// now, it's trivial to make List indexable, and thus a collection
extension List: CollectionType {
var startIndex: List<Element> { return self }
var endIndex: List<Element> { return .End }
subscript(idx: List<Element>)->Element {
switch idx {
case .End: fatalError("Subscript out of range")
case let .Node(x,_): return x
}
}
}
// and now you can use them as indices
l.first
",".join(dropFirst(l))
// list append
func +<T>(lhs: List<T>, rhs: List<T>) -> List<T> {
switch lhs {
case .End:
return rhs
case let .Node(x, xs):
return (xs + rhs).cons(x)
}
}
let ll = l + l // copies left-hand l
let lll = l + l
ll == lll // false, they are different lists even if they contain the same values
// I guess it's debatable whether the following is "correct" behaviour
advance(ll, 3) == l // true
advance(lll, 3) == l // true
// are there any cases where this collection can be used to get definitely incorrect behaviour?
@airspeedswift

This comment has been minimized.

Copy link
Owner Author

commented Jul 24, 2015

Alternatively you could implement == like this:

func ==<T>(lhs: List<T>, rhs: List<T>) -> Bool {
    switch (lhs,rhs) {
    case (.End,.End): return true
    default:
        return false
    }
}

Which works for traversal but breaks the rules for Equatable:

l.startIndex == l.startIndex  // false
@Sega-Zero

This comment has been minimized.

Copy link

commented Apr 30, 2016

Wouldn't setting an Equatable constraint for Element be better?
then we'll have

func ==<T>(lhs: List<T>, rhs: List<T>) -> Bool {
    switch (lhs,rhs) {
    case (.End,.End): return true
    case (.End,.Node): return false
    case (.Node,.End): return false
    case let (.Node(x),.Node(y)):
        return x == y
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.