kleene-star.swift

// The free monoid
protocol Free {
    class var ε: Self { get }
    func +(lhs: Self, rhs: Self) -> Self
}

extension String: Free {
    static var ε: String { return "" }
}

// Character is sketchy enough that it can hold arbitrary-length strings,
// but not enough to hold empty strings, so it can't be Free
func chars(s: String) -> [String] {
    return map(s) { String($0) }
}

// Get around optional-mutable limitation #becauseswift
// Can't be declared locally inside to a function #becauseswift
class M<T> { var contents: T; init(_ x: T) { contents = x } }

// x* -> ε | xx*
operator postfix * {}
@postfix func *<S: Sequence, E: Free where E == S.GeneratorType.Element>(s: S) -> SequenceOf<E> {
    return SequenceOf<E> { () -> GeneratorOf<E> in // #becauseswift
        var first: M<S.GeneratorType>!, f: E! // Least significant / fastest changing
        var rest: M<GeneratorOf<E>>!, r: E!   // Most significant / slowest changing
        return GeneratorOf<E> {
            if !first { // Initially return ε
                first = M(s.generate())
                return E.ε
            }
            if !rest {
                rest = M(s*.generate())
                r = rest.contents.next()
            }
            f = first.contents.next()
            if !f { // When first runs out, r steps forward and f resets
                r = rest.contents.next()
                first = M(s.generate())
                f = first.contents.next()
            }
            if !f || !r { return nil }
            return f! + r!
        }
    }
}

func takeWhile<S: Sequence, T where T == S.GeneratorType.Element>(s: S, pred: T -> Bool) -> GeneratorOf<T> {
    var g = s.generate()
    return GeneratorOf<T> {
        let e = g.next()
        return e && pred(e!) ? e : nil
    }
}

println(Array(takeWhile(chars("abc")*) { countElements($0) < 3 }))
// -> [, a, b, c, aa, ba, ca, ab, bb, cb, ac, bc, cc]