 	}
 }
 
+/// Takes a separator and a list and intersperses that element throughout the list.
+///
+///     intersperse(1)([1, 2, 3]) == [1, 1, 2, 1, 3, 1]
+public func intersperse<A>(sep : A) -> List<A> -> List<A> {
+	return { l in
+		switch l.match() {
+		case .Nil:
+			return List()
+		case .Cons(let x, let xs):
+			return x <| prependToAll(sep)(xs)
+		}
+	}
+}
+
+private func prependToAll<A>(sep : A) -> List<A> -> List<A> {
+	return { l in
+		switch l.match() {
+		case .Nil:
+			return List()
+		case .Cons(let x, let xs):
+			return sep <| x <| prependToAll(sep)(xs)
+		}
+	}
+}
+
 /// Inserts a list in between the elements of a 2-dimensional array and concatenates the result.
 public func intercalate<A>(xs : [A]) -> [[A]] -> [A] {
+	return { xss in concat(intersperse(xs)(xss)) }
+}
+
+/// Inserts a list in between the elements of a 2-dimensional array and concatenates the result.
+public func intercalate<A>(xs : List<A>) -> List<List<A>> -> List<A> {
 	return { xss in concat(intersperse(xs)(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)) } }
}


	return { l in l.map(f) }
}

/// Maps a function over a list and returns a new list containing the mapped values.
public func map<A, B>(f : A -> B) -> List<A> -> List<B> {
	return { l in l.map(f) }
}

/// Replace all occurrences of a value in a list by another value.
public func replace<A : Equatable>(x : A) -> A -> [A] -> [A] {
	return { y in { xs in xs.map({ z in z == x ? y : z }) } }
}

/// Replace all occurrences of a value in a list by another value.
public func replace<A : Equatable>(x : A) -> A -> List<A> -> List<A> {
	return { y in { xs in xs.map({ z in z == x ? y : z }) } }
}

