list.swift

enum List<Element> {
  case Nil
  indirect case Cons(head: Element, tail: List<Element>)
}

struct ListGenerator<Element> : GeneratorType {
  private var list: List<Element>
  mutating func next() -> Element? {
    switch list {
    case .Nil: return nil
    case .Cons(let element, let rest):
      list = rest
      return element
    }
  }
}

extension ListGenerator : SequenceType {
  func generate() -> ListGenerator {
    return self
  }
}

extension List : SequenceType {
  func generate() -> ListGenerator<Element> {
    return ListGenerator(list: self)
  }
}

extension List {
	var isEmpty: Bool {
		switch self {
    case .Nil:  return true
    case .Cons: return false
    }
	}
}

extension EmptyCollection : ArrayLiteralConvertible {
  public init(arrayLiteral: Element...) {
    assert(arrayLiteral.isEmpty)
  }
}

func ~= <C : CollectionType>(lhs: EmptyCollection<C.Generator.Element>, rhs: C) -> Bool {
  return rhs.isEmpty
}

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

extension List : ArrayLiteralConvertible {
  init<G : GeneratorType where G.Element == Element>(var gen: G) {
    self = gen.next().map {.Cons(head: $0, tail: List(gen: gen))} ?? .Nil
  }
  init<S : SequenceType where S.Generator.Element == Element>(seq: S) {
    self = List(gen: seq.generate())
  }
  init(arrayLiteral: Element...) {
    self = List(gen: arrayLiteral.generate())
  }
}

infix operator |> {
  associativity right
}

func |> <T>(lhs: T, rhs: List<T>) -> List<T> {
  return List.Cons(head: lhs, tail: rhs)
}

extension List {
  func appended(with: Element) -> List<Element> {
    switch self {
    case .Nil: return [with]
    case .Cons(let head, let tail): return List.Cons(head: head, tail: tail.appended(with))
    }
  }
  func extended(with: List<Element>) -> List<Element> {
    switch self {
    case .Nil: return with
    case .Cons(let head, let tail): return List.Cons(head: head, tail: tail.extended(with))
    }
  }
  func extended<S : SequenceType where S.Generator.Element == Element>(with: S) -> List<Element> {
    return extended(List(seq: with))
  }
  func map<T>(@noescape transform: Element -> T) -> List<T> {
    switch self {
    case .Nil: return []
    case .Cons(let head, let rest): return transform(head) |> rest.map(transform)
    }
  }
}

extension List {
  func select() -> List<(Element, List<Element>)> {
    switch self {
    case .Nil: return []
    case .Cons(let head, let rest): return (head, rest) |> rest.select().map { ($0, head |> $1) }
    }
  }
}


let jo: List = [1, 2, 3, 4]

jo.select() // (1, [2, 3, 4]), (2, [1, 3, 4]), (3, [1, 2, 4]), (4, [1, 2, 3])