In Progress
Unit 1, Lesson 1
In Progress

Sort Check

Video transcript & code

Today's episode is about the Enumerable#each_cons method. We've looked at the #each_cons method before, in episode #316. In that episode, we used it to generate values. But #each_cons has some interesting applications for checking properties of collections as well.

It's easy enough to sort a collection in Ruby.

Here's a collection of words.

We can send it the sort message to get back a new, sorted list.

words = %w[apple banana carrot durian pear orange]
words.sort
# => ["apple", "banana", "carrot", "durian", "orange", "pear"]

But what if we want to just verify that the list is already sorted?

The algorithm for this is conceptually straightforward. We just need to check that apple compares as "less" than banana, banana is "less" than carrot, and so on down the line.

But how do we code this? In order to compare items, we have to do it two at a time.

One way to do this is to take all but the last item in the list and zip it together with all but the first item in the list. This gives us a list of pairs of items: apple and banana, banana and carrot, and on down the line.

words = %w[apple banana carrot durian pear orange]
zipped = words[0..-2].zip(words[1..-1])
# => [["apple", "banana"], ["banana", "carrot"], ["carrot", "durian"], ["duri...

We can then check to make sure that for every pair, the left-hand item sorts lower than the right-hand item.

words = %w[apple banana carrot durian pear orange]
zipped = words[0..-2].zip(words[1..-1]).all?{
  |left, right|
  left <= right
}
# => false

But there's a shorter way to do this in Ruby. As we saw in episode #316, there's an easy way to get a "sliding window" over the elements of a list.

We just have to send the #each_cons message. Examining the objects yielded to the block, we see we get the same list of left/right pairs.

words = %w[apple banana carrot durian pear orange]
zipped = words.each_cons(2) do
  |pair|
  pair # => ["apple", "banana"], ["banana", "carrot"], ["carrot", "durian"], ...
end

Conveniently, when we don't pass it a block, #each_cons returns an enumerator object.

words = %w[apple banana carrot durian pear orange]
zipped = words.each_cons(2)
# => #<Enumerator: ["apple", "banana", "carrot", "durian", "pear", "orange"]:...

We can then send any Enumerable message we want to this object. Such as #all?.

words = %w[apple banana carrot durian pear orange]
zipped = words.each_cons(2).all?{|left, right| left <= right}
# => false

What if we want to see which words failed the sort test? We can just switch our #all? to a #reject.

words = %w[apple banana carrot durian pear orange]
zipped = words.each_cons(2).reject{|left, right| left <= right}
# => [["pear", "orange"]]

And there are our culprits: orange falls after pear in the list.

I hope you've enjoyed this little exploration. It's all stuff you could have worked out for yourself, but I find that demonstrations like this sometimes open my mind to new applications of methods I already know about.

Before I go, I want to thank Michael Feathers, who unwittingly gave me the idea for this episode. Happy hacking!

Responses