Skip to content

Instantly share code, notes, and snippets.

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

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) {
// 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"]
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
// 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?

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
        return false

Which works for traversal but breaks the rules for Equatable:

l.startIndex == l.startIndex  // false

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.