 		case .Nil:
 			return []
 		case .Cons(let x, let xs):
-			return [x] <| foldr({ (let ys : [A]) in
-				return { r in
-					return ys <| (x <| ys) <| r
-				}
+			return [x] <| foldr({ ys, r in
+				return ys <| (x <| ys) <| r
 			})([])(nonEmptySubsequences(xs))
 	}
 }
 
+/// Returns a list of all subsequences of a list.
+///
+///     subsequences([1, 2, 3]) == [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
+public func subsequences<A>(xs : List<A>) -> List<List<A>> {
+	return List() <| nonEmptySubsequences(xs)
+}
 
+public func nonEmptySubsequences<A>(xs : List<A>) -> List<List<A>> {
+	switch xs.match() {
+	case .Nil:
+		return List()
+	case .Cons(let x, let xs):
+		return List(x) <| foldr({ ys, r in
+			return ys <| (x <| ys) <| r
+		})(List())(nonEmptySubsequences(xs))
+	}
+}
+
+

				case .Nil:
					return transpose(xss)
				case .Cons(let x, let xs):
					return (x <| concatMap({ [head($0)] })(xss)) <| transpose(xs <| concatMap({ [tail($0)]} )(xss))
			}
	}
}


}

private func select<A>(p : A -> Bool) -> A -> ([A], [A]) -> ([A], [A]) {
	return { x in { t in p(x) ? (x <| fst(t), snd(t)) : (fst(t), x <| snd(t)) } }
}

/// Partitions the elements of a list according to a predicate.
///
/// partition({ $0 < 3 })([1, 2, 3, 4, 5]) == ([1, 2],[3, 4, 5])
public func partition<A>(p : A -> Bool) -> List<A> -> (List<A>, List<A>) {
	let e = (List<A>(), List<A>())
	return { l in foldr(select(p))(e)(l) }
}

private func select<A>(p : A -> Bool) -> A -> (List<A>, List<A>) -> (List<A>, List<A>) {
	return { x in { t in p(x) ? (x <| fst(t), snd(t)) : (fst(t), x <| snd(t)) } }
}

