Combinations Part 5 – (wrapping it up)

The original problem as posed by Eric Lippert was to write a function to produce all the combinations of k elements from a collection of n elements. So far I’ve ported the code to product all the combinations of k true booleans in a collection of n booleans where k <= n. We can use the work we've done so far to solve the original problem. See Lippert Part 3 to follow along with his post.

My complete solution is stored as a gist here.

First I’ll create a zipWhere method like he did.

extension SequenceOf {
    func zipWhere<S:SequenceType where S.Generator.Element == Bool>(bools:S) -> SequenceOf<T> {

        return SequenceOf { () -> GeneratorOf<T> in
            var generator = Zip2(self, bools).generate();
            return GeneratorOf<T> {
                var next = generator.next();

                while (next != nil) {
                    let (v,b) = next!;
                    if (b) {
                        return v;
                    } else {
                        next = generator.next();
                    }
                }
                
                return nil;
            }
        }
    }
}

On the first line I use the Zip2 structure to create a sequence of tuples out the elements in self and the sequence of bools.

Then I return a new SequenceOf that only returns the elements from self that are paired up in a tuple with a true value from the booleans.

Now we can write the final function. It relies on my custom map function mentioned in last post. First we generate all the boolean combinations using the combinations function from last time. Then we use the map function to transform each boolean combination into a combination of the elements in s.

func combinations<S:SequenceType>(s:S,k:UInt) -> SequenceOf<SequenceOf<S.Generator.Element>> {
    let sArray = Array(s);
    let sseq = SequenceOf(s);

    return combinations(UInt(sArray.count), k).map { sseq.zipWhere($0) };
}

See all code

Posted in computer science | Tagged , , | Leave a comment

Combinations – Part 4 (combinations of booleans)

In this article we’ll implement the combinations function from Eric Lippert’s post. Here he implements a function that returns all the combinations of n booleans with k of them set to true. See part 3 of his series.

Let’s implement in parts like Eric did, starting with some preliminaries and the signature

typealias BoolStack = ImmutableStack<Bool>;
let singletonEmptyBoolStack = SequenceOf.singleton(BoolStack.emptyStack());
let emptySequenceOfBoolStack:SequenceOf<BoolStack> = SequenceOf.empty();

func combinations(n:UInt, k:UInt) -> SequenceOf<BoolStack> {

I’m going to use a type alias to reduce slightly the amount of typing I need to do to get an ImmutableStack. Next I’m going to define some variables for sequences that will be used in base cases of our recursion. The first is a singleton sequence that contains one empty boolean stack. The second is a completely empty sequence.

I changed the signature slightly to take UInts rather than Ints. This just reduces one error case I need to check for. We are going to return a sequence of boolean stacks.

I’m going to follow the exact same algorithm, so I have the first two simple base cases.

if (k == 0 && n == 0) {
    return singletonEmptyBoolStack;
}

if (n < k) {
    return emptySequenceOfBoolStack;
}

Note that we don’t have a yield statement so we need to return a “full sequence”.

Now the base cases are done. Like Eric we have two cases left to handle. The first are the cases where we are going to enumerate the combinations(n-1,k-1) and push a true on to them.

    let seq1 = (k>0) 
        ? SequenceOf(lazy(combinations(n-1, k-1)).map({$0.push(true)})) 
        : emptySequenceOfBoolStack;

If k is greater than 0 then we can call combinations(n-1,k-1). If it isn’t then seq1 will be empty. Now for every combination returned by combinations(n-1,k-1) we want to push a true onto it. We can do this with a map function rather than iterating thru all of the combinations. Strangely map isn’t defined for regular SequenceOf instances. It is only defined for LazySequence instances. We can easily create a LazySequence from any SequenceType by calling the lazy method. However, then when we are done mapping we no longer have a SequenceOf. (map returns a LazySequence as well). But we can easily convert back to a SequenceOf as SequenceOf has a constructor that takes any other SequenceType.

So this highlights some of the strangeness of the library currently. Sequences are kind of clumsy to use and require lots of conversions like in this example. If you want to avoid the two conversions you can define your own map method for any SequenceType. I did it like this:

extension SequenceOf {
    func map<U>(transform:T -> U) -> SequenceOf<U> {

        return SequenceOf<U> { () -> GeneratorOf<U> in
            var g = self.generate();
            return GeneratorOf {
                return g.next().map(transform);
            }
        }
    }
}

This would the simplify our code above to look like this (which you have to admit looks much nicer, but I was trying to figure out how to use the built-in libraries so I tried both ways)

let seq1 = (k>0) ? combinations(n-1,k-1).map({$0.push(true)}) : emptySequenceOfBoolStack;

Next we need to generate the second sequence which is combinations(n-1,k) where we push a false onto each combination. And then we want to combine the two sequences:

return seq1.extend(
    SequenceOf(lazy(combinations(n-1, k)).map({$0.push(false)})));

// again this could be simplified with my custom map function to this
// return seq1.extend(combinations(n-1, k).map({$0.push(false)}));

Again, note that are code is a little more difficult because we can’t take advantage of yield, rather I’m creating complete sequences. But also note that the definition of my map method doesn’t really eagerly evaluate the sequences, nor does my extend method. So we are still returning lazy lists.

That’s it for this function.

Here is is with the built-in lazy functions

func combinations(n:UInt, k:UInt) -> SequenceOf<BoolStack> {
    if (k == 0 && n == 0) {
        return singletonEmptyBoolStack;
    }

    if (n < k) {
        return emptySequenceOfBoolStack;
    }

    let seq1 = (k>0) 
        ? SequenceOf(lazy(combinations(n-1, k-1)).map({$0.push(true)})) 
        : emptySequenceOfBoolStack;
    return seq1.extend(
        SequenceOf(lazy(combinations(n-1, k)).map({$0.push(false)})));
}

And here with my custom map function:

func combinations(n:UInt, k:UInt) -> SequenceOf<BoolStack> {
    if (k == 0 && n == 0) {
        return singletonEmptyBoolStack;
    }

    if (n < k) {
        return emptySequenceOfBoolStack;
    }

    let seq1 = (k>0) ? combinations(n-1,k-1).map({$0.push(true)}) : emptySequenceOfBoolStack;

    return seq1.extend(combinations(n-1, k).map({$0.push(false)}));
}
Posted in computer science | Tagged , , , | Leave a comment

Combinations – Part 3 (SequenceOf extensions)

I want to continue on with my implementation of Combinations. But first, when working on this problem I determined I really needed some helper methods on SequenceOf. Initially these were very complicated but as my comfort level increased I figured out how to simplify some of them so much that they hardly provide any value anymore. Let’s take a look.

First I wanted some way to create an empty sequence. This would play the same role as Enumerable.Empty() in .Net. I couldn’t find any such built in method. I did find something analogous for generators as there exists a GeneratorOfOne structure that can be used to create GeneratorTypes that yield 0 or 1 elements. However, generators are not what I want. I want sequences. The differences are subtle but basically the difference is that everytime you call generate on a Sequence you get a “fresh” generator starting from the beginning of your sequence. This is not necessarily true of generators which are not required to “reset” back to the beginning. Anyway see Airspeed Velocity for more info.

So here is the method:

extension SequenceOf {
    public static func empty() -> SequenceOf<T> {
        return SequenceOf([]);
    }
}

Next, I wanted an extensions method for creating a singleton sequence.

extension SequenceOf {
    public static func singleton(t:T) -> SequenceOf<T> {
        return SequenceOf([t]);
    }
}

As you can see this are rather simple one liners. However, I still think they are useful because they make it clear when I use them what I’m trying to do. The one liners themselves are a little more confusing. Indeed, the first one seems to say to me that I’m creating a sequence that contains one element that is an empty array. Of course, this isn’t true. Rather it’s a sequence over the elements in the array.

Both of these methods are static methods so here is how you would invoke them:

let emptySequence = SequenceOf<Int>.empty();
let singletonSequence = SequenceOf<String>.singleton("hello");

Finally, I could not find anyway to concatenate two sequences. I looked for concat, append, join, extend methods. While these exist for arrays, collections, strings, etc. I couldn’t find anything that applied to sequences; which seems very strange to me. So I created the method. It’s fairly simple but definitely provides value.

extension SequenceOf {
    public func extend<S1:SequenceType where S1.Generator.Element == T>(s1:S1) -> SequenceOf<T> {
        return SequenceOf{ () -> GeneratorOf<T> in
            var g0 = self.generate();
            var g1 = s1.generate();
            return GeneratorOf {
                g0.next() ?? g1.next();
            }
        }

    }
}

This might take a little explanation for beginners.

First, let’s examine the signature. It’s a generic method that takes one type parameter S1. Their are constraints placed on what S1 can be. First of all it must implement the SequenceType protocol. Next there is a where clause that states that the Element type of S1 must be identical to T. What is T? Well it helps to recall that SequenceOf is a generic struct. T is the type parameter for SequenceOf. So what the constraints on S1 are saying is that S1 can be any SequenceType that has the same type of elements as the sequence this method is being called on. So we could.

Next we see the arguments for this method. It takes one, s1 of type S1. Finally, the return type is SequenceOf. This makes sense because it’s the most fundamental SequenceType (except for maybe Array).

The rest of the method is a little complicated so I’m going to rewrite the method and be explicit:

func extend<S1:SequenceType where S1.Generator.Element == T>(s1:S1) -> SequenceOf<T> {

    return SequenceOf<T>({ () -> GeneratorOf<T> in
        var g0 = self.generate();
        var g1 = s1.generate();
        return GeneratorOf<T>({ () -> T? in
            g0.next() ?? g1.next();
        })
    })

}

I’m instantiating and returning a SequenceOf. It has a constructor that takes a closure. The closure it is expecting is one that takes no parameters and returns a GeneratorType. The implementation of this closure first calls generate on self and s1 and stores those generators in vars. (They must be vars since the next method that will be called on them is mutating.) Then I instantiate and return a GeneratorOf. Now GeneratorOf also has a constructor that takes a closure. This closure is basically the “next” method you want the GeneratorOf to have. Our next method is pretty simple. It calls next on the first generator and if the result is nil then it calls next on the second generator.

NB: It’s very important where I instantiated g0 and g1. If I would have instantiated them outside of the closure, (for example if they were the first two lines in the extend method); then the generate methods would only be called when the extend method was called. This means that the resulting sequence wouldn’t reset when it’s generate method is called.

If I would have called generate on g0 and g1 inside the nested closure then the sequence would reset overtime next is called and always returns the first element of g0. Let me illustrate what I’m saying by actually making these mistakes and then showing the results.

// Error #1. Sequence doesn't "reset" after it's been enumerated
extension SequenceOf {
    func extend3<S1:SequenceType where S1.Generator.Element == T>(s1:S1) -> SequenceOf<T> {

        var g0 = self.generate();
        var g1 = s1.generate();

        return SequenceOf<T>({ () -> GeneratorOf<T> in
            return GeneratorOf<T>({ () -> T? in
                return g0.next() ?? g1.next();
            })
        })
        
    }
}

var items = SequenceOf([1,2]).extend3([3]);
var gen = items.generate();
println(gen.next());
println(gen.next());
println(gen.next());
println(gen.next());
gen = items.generate();
println(gen.next());
println(gen.next());
println(gen.next());
println(gen.next());

If you copy/paste this into a playground you’ll see the output is

Optional(1)
Optional(2)
Optional(3)
nil
nil
nil
nil
nil

In other words you can see that once the sequence is exhausted it wasn’t reset even after calling generate method again to get a fresh generator.

Now let’s try the other mistake

// Error #2, we never make any progress
extension SequenceOf {
    func extend4<S1:SequenceType where S1.Generator.Element == T>(s1:S1) -> SequenceOf<T> {

        return SequenceOf<T>({ () -> GeneratorOf<T> in
            return GeneratorOf<T>({ () -> T? in
                var g0 = self.generate();
                var g1 = s1.generate();
                return g0.next() ?? g1.next();
            })
        })
        
    }
}

var items = SequenceOf([1,2]).extend4([3]);
var gen = items.generate();
println(gen.next());
println(gen.next());
println(gen.next());
println(gen.next());

You’ll see the output is

Optional(1)
Optional(1)
Optional(1)
Optional(1)

Of course this makes sense because we reset the generator on the first sequence every time next is called so we never make any progress.

Now let’s look at the original method:

Optional(1)
Optional(2)
Optional(3)
nil
Optional(1)
Optional(2)
Optional(3)
nil

Ok, this post got long enough. Let’s quit here.

Posted in Apple, computer science | Tagged , , | Leave a comment

Combinations – Part 2

Last time I started working on the combinations problem that Eric Lippert wrote about:

We’ll be working a lot with SequenceType, SequenceOf, GeneratorType and GeneratorOf. I’m more familiar with the enumerating type of C# (IEnumerable and IEnumerator). Together SequenceType and SequenceOf play the role of IEnumerable. The other two types play the role of IEnumerator. I found these types initially very confusing. SequenceType and GeneratorType are protocols which are a little like interfaces, but you can’t specify a generic type parameter when using them. For example you can’t declare our ImmutableStack to implement SequenceType(T) (Note, I’m using parentheses rather than angle brackets because I can’t figure out how to get them to render). We can only say it implements SequenceType.

Let’s look at the code from last time again:

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;
            }
        };
    }
}

How does a user of this stack know that it enumerates T values? Well, in addition to the generate method, a SequenceType defines an associated type as well via a type alias. Here is the signature of SequenceType

protocol SequenceType : _Sequence_Type {
    typealias Generator : GeneratorType
    func generate() -> Generator
}

It says that I need to define a type alias for a type that implements GeneratorType; and I must use this type as the return type of my generate method. However, I still don’t see any element type mentioned. Let’s look at GeneratorType:

protocol GeneratorType {
    typealias Element
    mutating func next() -> Element?
}

Finally we see an “element” type mentioned. The GeneratorType protocol defines an associated type for elements and we can see that this type is used as the return type of the next method.

Now I didn’t define any type aliases, so what is going on? Using inference the compiler can often figure out what the associated type is, even if the developer doesn’t specify it. In my case the return type of my generate method is GeneratorOf(T), and therefore the compiler knows that the associated type for my stack is GeneratorOf(T). If you then look at the signature for GeneratorOf(T) you’ll see that it has a next method that returns a T?.

struct GeneratorOf<T> : GeneratorType, SequenceType {
    init(_ nextElement: () -> T?)
    init<G : GeneratorType where T == T>(_ base: G)
    mutating func next() -> T?
    func generate() -> GeneratorOf<T>
}

I’m allowed to use GeneratorOf(T) as my associated type in my ImmutableStack because it implements GeneratorType. Also the compiler infers that the Element associated type for GeneratorType is T.

So putting it all together, it is now clear that my ImmutableStack enumerates T values.

Posted in computer science | Tagged , , | Leave a comment

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;
            }
        };
    }
}

Posted in computer science | Tagged , , | Leave a comment

Math from scratch in Haskell: addition

Last time I developed a representation of Natural numbers following Eric Lippert’s lead. In this post I’ll continue to follow him and implement addition.

Continue reading

Posted in Uncategorized | Leave a comment

Math from scratch in Haskell: zero and one

I’ve been following a set of posts written by Eric Lippert where he is implementing arbitrary size Naturals and the corresponding arithmetic in C#. As I follow along I’m writing an implementation in Haskell (one that I hope is idiomatic to Haskell).
Continue reading

Posted in Uncategorized | Tagged , , | 1 Comment

Importing Subversion Into Git

Over the years I’ve accumulated some Subversion repositories. I used Subversion to control the source code I wrote for my masters courses. These repositories are sprinkled around a couple of computers I own. Now that I have accounts on GitHub and Bitbucket I decided it was time to import the old code into git and push it to the cloud. This allows me to clean up all the old repositories and easily access it from any computer.

Continue reading

Posted in software development | Tagged , | Leave a comment

Using git instaweb on a Mac

Today I discovered git instaweb. This is a very cool feature that allows you to instantly view your local repository (the one in your current working directory) in a web browser. It was incredibly easy to setup on my Mac. I did some googling and found out not everyone thinks it is so easy to setup. This is because they either don’t have a web server installed or the web server that is installed (apache2) isn’t installed on a Mac the way git instaweb expects.
Continue reading

Posted in Mac, software development | Tagged , | Leave a comment

Doing Code Reviews with GitHub

For many reasons, I really enjoy using git and GitHub for my current project. Today I’ll highlight one reason: code reviews.

Continue reading

Posted in software development | Tagged | 3 Comments