Combinations – Part 1

I’ve had a difficult time trying to understand the collections in the Swift programming language from Apple. In particular, I’ve been trying to identify the analog of the IEnumerable type from C#. I don’t think there is one. As an exercise, I thought I’d try to port the C# code Eric Lippert wrote about Combinations. Here’s a link to the start of his series: Eric Lippert on Combinations

I’m going to start with defining Stacks like he does.

Right off the bat we run into problems. Swift doesn’t have abstract classes, nor does it support nested generic classes. So I did away with the abstract class and made the parent class ImmutableStack play the role of EmptyStack.

It’s not that big of a deal that nested classes aren’t supported. I can mark the subclass private or leave it module scope. It accomplishes the same thing as consumers of this stack will not know of its existence.

UPDATE 11/17/2014
I just was reminded that I don’t need semicolons everywhere.

import Foundation


public class ImmutableStack<T> {

    let top:T? = nil;

    private init(top:T? = nil) {
        self.top = top;
    }

    public func push(t:T) -> ImmutableStack<T> {
        return NonEmptyStack(top: t, tail: self);
    }

    public func pop() -> ImmutableStack<T>? {
        return nil;
    }

    public func isEmpty() -> Bool {
        return true;
    }

    public class func emptyStack() -> ImmutableStack<T> {
        return ImmutableStack();
    }

}

private class NonEmptyStack<T> : ImmutableStack<T> {
    let tail:ImmutableStack<T>;

    init(top:T, tail:ImmutableStack<T>) {
        self.tail = tail;
        super.init(top: top);
    }

    override func push(t: T) -> ImmutableStack<T> {
        return NonEmptyStack(top: t, tail: self);
    }

    override func pop() -> ImmutableStack<T> {
        return tail;
    }

    override func isEmpty() -> Bool {
        return false;
    }

}

To make our stack “enumerable” we need to make it implement SequenceType. I’ve chosen to do this in the same file but took advantage of Swift extensions. I need to implement the generate method. Since Swift doesn’t yet have a yield keyword, we need to manually write our generation code. There is a helper structure named GeneratorOf. It has a constructor that takes a closure. This closure is used to return the “next” element.

extension ImmutableStack : SequenceType {
    public func generate() -> GeneratorOf<T> {
        var stack = self;

        return GeneratorOf {
            if (stack.isEmpty()) {
                return nil;
            } else {
                let result = stack.top;
                stack = stack.pop()!;
                return result;
            }
        };
    }
}

About Michael

I am a software developer and part-time professor. I enjoy studying and discussing mathematics, computer science and software development.
This entry was posted in computer science and tagged , , . Bookmark the permalink.

Leave a Reply