The other day I was trying to find a way to find all possible combination of 2-4 particular letters of the alphabet (A, C, G, N, T), with repetition. The objective was to try to build an associative array of letter combinations and the corresponding ordered string. (See Sorting characters within a string).

Generating all combinations would usually takes a cartesian cross-product to be efficient (see japhy's post about that).

I came up with a simple but (very) inefficient method of doing the same thing:

my @strings = (grep /[acgmt]{2}/, ('aa' .. 'tt'), 
               grep /[acgmt]{3}/, ('aaa' .. 'ttt'), 
               grep /[acgmt]{4}/, ('aaaa' .. 'tttt'));
[download]

This yields exactly what I want, but to the price of a high cost in memory and processing. The problem is with the .. operator. The number of elements generated before the grep by the .. operator is 361,173. After the grep you are left with only 774 "useful" strings. And if you wanted to get all strings up to 5 letters you would then have to deal with nearly 10,000,000 elements. And things only get worse.

I then began to wonder about the availability of a lazy form of evaluation for expression. For the uninitiated, lazy evaluation of an expression is delaying evaluation until the last moment, at which point you may realize that you only need to compute a part of the expression. The aim here would be to avoid storing the intermediary result of the .. operator in memory by applying the grep directly, as a filter function.

Well, programmers of Perl, rejoice. It seems Perl6 might have a lazy operator (see rfc123) that will allow to do exactly this. With the lazy operator, we could rewrite the previous piece of code like this:

my @strings = (grep /[acgmt]{2}/, lazy ('aa' .. 'tt'), 
               grep /[acgmt]{3}/, lazy ('aaa' .. 'ttt'), 
               grep /[acgmt]{4}/, lazy ('aaaa' .. 'tttt'));
[download]

This would causes a lazy list to be passed to the filter function grep, saving us from allocating the entire letter combinations array in memory. While this might not be the greatest example ever, I think it's simple enough to illustrate the possibilities.

Lazy evaluation is (to the best of my knowledge) mostly available in functionnal programming language. It is a powerful concept that can only reinforce the variety of Perl idioms you can use to easily solve complex problems.

So everything is good, Perl6 will allow us to be lazy and use lazy. I can't wait to see the impatience and hubris functions ;-)

Guillaume

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.