Tuesday, June 05, 2007


More Flan iteration

Perhaps the simplest kind of iteration is "print the numbers from 1 to 10". Flan's syntax for this (which even beats Ruby in terms of consciseness and clarity, if I do say so myself) is:

#print(each 1..10);

As requested, this produces 12345678910.

Let's examine it piece by piece.

The .. operator produces a type. (Earlier I said it produced a list fragment; change of plan. It's less comon to need a list fragment, and you can quite trivially generate one from the type.)

The type produced by a..b is "any integer from a to b, inclusive". In case you're wondering, there's also a range of companion operators such as a<..b: "integers from a+1 to b", and a..<b: "integers from a to b-1". The latter is probably useful more often than the straightforward .. operator.

As we saw last time, the "each" keyword can be used to iterate over a list; however, it can also iterate over an enumerable type. (In fact the list iteration system is based on this.)

An enumerable type is one that's finite, and has some kind of order to it. For example:

@SingleDigitNumber = 0..9;
@Vowel = 'a'¦'e'¦'i'¦'o'¦'u';
@ListItem = thelist.Element;
@ListIndex = thelist.Index;
@ThreeVowelString = [Vowel, Vowel, Vowel];

This can be very useful. It's a convenient way of declaring "the solution must look something like this", and then searching for a valid solution among the things that look like that.

For example, in a recent discussion on Reddit, I gave the following (slightly reformatted, but otherwise the same) Flan solution to this knapsack problem:

@prices = [215, 275, 335, 355, 420, 580];
@Solution = [0..7:6]; // a Solution is a list of 6 numbers between 0 and 7

int Solution.@totalPrice
return sum(# this[each @i] * prices[i] );

@result = #first Solution:totalPrice.is 1505;

Let's step through this to make sure it's clear -

prices is just a list of the 6 appetizer prices. Nothing much to say here.
Solution is our enumerable type. It's a list of 6 integers, representing the number of times to order each of the 6 appetizers.
Solution.totalPrice declares a method belonging to the type Solution, to represent the total price of the order. I haven't shown a method declaration before, but it's more or less the same as a C++ one - including the use of this to refer to the Solution it's acting on. The price is calculated using an iteration, much like the dot_ab example I showed last time.

There's only one really new feature here, and that's the construct
#first Solution:totalPrice.is 1505

This iterates through all the possible Solutions, looking for the first one whose totalPrice is 1505.
(I've used the iteration controller first, so that it stops after the first solution is found. To generate a list of all solutions I could have used each.)

The colon operator is filtering the iteration, similar to the ~ operator I introduced last time. In fact, I could equally well have written -

@prices = [215, 275, 335, 355, 420, 580];
@Solution = [0..7:6]; // a Solution is a list of 6 numbers between 0 and 7

is Solution.@CorrectPrice
return sum(# this[each @i] * prices[i] ).is 1505;
@result = #first Solution ~CorrectPrice;

More to come soon.

This page is powered by Blogger. Isn't yours?