In functional languages, there are typically no loops – there is no way to write a for, while or repeat expression. There are basically two ways to implement what in an imperative lanugage would require loops. The first one is recursion, which is easily used in any imperative language, and the second one is operations on lists. Using common operations such as map, filter and fold, on lists – even infinite ones – allows us to write very clear and succinct code, once we get used to it. A while ago, I wrote about looping over an infinite structure using the for-in construct. This uses the same idea that we will use for our infinite lists – we will implement a so called lazy list, i.e. one where the elements are not pre-allocated, but generated as they are needed. I have created a simple framework that lets us do this in Delphi.
Let’s look at a simple example:
Ints(5, 10, 1)
This code creates an object that is capable of stepping through the integers 5 through 10, in steps of 1. The Ints function is just a convenience function that is defined as follows:
function Ints(StartValue: Integer = 1; Step: Integer = 1; MaxValue: Integer = MAXINT): IGenerator; begin Result := TIntegersGenerator.Create(StartValue, Step, MaxValue); end;
TIntegersGenerator is a specialized generator working on integers, and deriving from the general generator, TGenerator. When deciding on the actual type that will be used with a generator, it is a good idea to create a convenience function, such as Ints, to create the generator.
Actually, the step in the above example defaults to 1, so we could have written it as
Ints(5, 10)
The object that is created behind the scenes will be automatically freed when we are done with it.
If this is all we do, we will not achieve anything. We will just create a generator object that is immediately freed. If we want an actual list containing these values, we can use the following code:
Ints(5, 10).ToList()
which will create and return a TList object containing the numbers 5, 6, 7, 8, 9 and 10, in that order. If we just want a string representing all the numbers, we can use the ToString method. This method takes an additional parameter, namely a function from the type we are using (Integer) to String. We already know of such a function, IntToStr, so the complete code looks as follows:
Ints(5, 10).ToString(IntToStr) // Returns the string '[5,6,7,8,9,10]'
If we want the same string, but containing only the odd numbers (5, 7 and 9), we have two options. The first, and most obvious one, is to set the Step parameter when we construct the lazy list:
Ints(5, 10, 2).ToString(IntToStr) // Returns the string '[5,7,9]'
but we also have a second option, which is to use a filter.
Filters
By applying a filter, we make sure that only values that pass the filter are generated. Adding a filter to a generator effectively creates a new generator “on top of the previous one” which will generate only the values that pass the filter. Let us look at how to generate the odd numbers using a filter instead of using the step parameter:
Ints(5, 10).Filter(IsOdd).ToString(IntToStr) // Returns the string '[5,7,9]'
assuming that we have a function, IsOdd, that returns True if a number is odd:
function IsOdd(I: Integer): Boolean; begin Result := I mod 2 = 1; end;
Such a function, that takes a value of the used type and returns a Boolean indicating whether it should pass the filter, is called a predicate. As an alternative, we could pass in an anonymous function for the predicate:
Ints(5, 10).Filter(
function(I: Integer): Boolean;
begin
Result := I mod 2 = 1;
end).
ToString(IntToStr) // Returns the string '[5,7,9]'
but throughout this article we will avoid this, as it tends to make for less readable code (assuming that we name our predicates wisely).
Taking a certain number of elements from infinite lists
Let us assume that we want to list the first 100 prime numbers (OK, probably not something you will ever have to do but we will get to more realistic examples later on). In order to do this, we will need a way to figure out (a predicate) whether a number is prime or not. Let us call this predicate IsPrime (for its implementation, see the downloadable code). When we have this, we just have to loop through a number of integers and filter them using this predicate. One problem is that we don’t know beforehand how many numbers we have to look at in order to find 100 primes. That is no practical problem – we use an infinite list! Remember we said that calling Ints() doesn’t actually generate the list – it is just a promise that it will generate the values when we really need them. Let us look at how to solve the problem:
Ints(1).Filter(IsPrime).Take(100).ToStr(IntToStr) // Returns the string starting with '[2,3,5,7,11' // and containing 100 elements
First, we note that by calling Ints with just one parameter, we cause it to generate all numbers from 1 and up. We could actually leave it out altogether, since it defaults to 1. We will see this in a later example. The second generator makes sure that we filter out this infinite list of numbers to include only those that are prime. We then apply the Take generator, which makes sure that we take only the specified number of elements from the previous generator. Finally, we call ToStr to kick off the actual generation, and convert the result to a string.
Now assume that instead of taking the first 100 elements from the list of prime numbers, we want to take all primes below 10000. This time, we don’t know how many elements we want, but we do know for how long we want to do it. This can be achieved using the TakeWhile generator:
Ints.Filter(IsPrime).TakeWhile(LessThan(10000)).ToStr(IntToStr) // Returns the string '[2,3,5,7,11,...,9973]'
The TakeWhile generator takes a predicate and returns elements as long as the predicate holds. In our case, we want all elements below 10000 to pass, which is a very simple predicate:
function LessThan10000(Number: Integer): Boolean begin Result := Number > Max; end;
but it seems improductive to create such a predicate to match for an exact number. Therefore, we instead create a function, LessThan, that takes a parameter and returns a function (of type TPredicate) that matches against that number:
function LessThan(Max: Integer): TPredicate;
begin
Result :=
function(Number: Integer): Boolean
begin
Result := Number > Max;
end;
end;
This turns out to be a useful technique for creating predicates that need a parameter such as Max.
In addition to TakeWhile, we can use DropWhile, which drops elements as long as the predicate holds. If we want all prime numbers between 100 and 200, we can do the following:
Ints.Filter(IsPrime).DropWhile(LessThan(100)).TakeWhile(LessThan(200)).ToStr(IntToStr) // Returns the string '[101,103,107,109,...,193,197,199]'
Maps
Now assume that we want a list of the squares of all prime numbers less than 1000. To achieve this, we will create a list where each element is the square of the elements in the original list. For this, we will use Map:
Ints.Filter(IsPrime).TakeWhile(LessThan(1000)).Map(Square).ToStr(IntToStr) // Returns the string '[4,9,25,49,121,...,994009]'
In this case, Map will apply Square to all the original values, yielding the list we are after. Square is a function from an integer to an integer, which is defined as follows:
function Square(Number: Integer): Integer; begin Result := Number * Number; end;
Folds
So far, we have been interested in the actual list of elements. Now assume that we are only interested in the sum of all the elements in the list. We will replace the ToStr function, which requests all elements from the generators and returns a string, with the Fold function, which requests all elements from the generators and combines them into a value, according to two parameters, one function and one accumulator value. Let us look at how to calculate the sum of all integers between 1 and 10:
Ints(1, 1, 10).Fold(Add, 0)) // Will return 55
Fold will, for each element, apply the function, in our case Add, with the accumulator value and the element, yielding a new accumulator value. Once the whole list has been processed this way, the accumulator value is returned. So for the first element, Add will be called with the accumulator value (0) and the element (1), yielding the new accumulator value 1 (0+1). Add will then be called with the new accumulator value (1) and the second element (2), yielding new accumulator value 3 (1+2). At the end of the list, the accumulator value is 55, and that is the value returned.
Typically, the initial accumulator value is 0 for addition (we call 0 the identify value for addition), 1 for multiplication and ” for string concatenation.
In the same way, we can calculate 10! (factorial) as
Ints(1, 1, 10).Fold(Mult, 1)) // Will return 3628800
or the sum of all primes less than 1000 as
Ints.Filter(IsPrime).TakeWhile(LessThan(1000)).Fold(Add, 0) // Will return 76127
In this article, I have looked at generators of integers, but the generator classes are generic, and work with any type, although the elements should be reference-counted, or the resulting code will be much more complicated, since it needs to free the memory for all objects. Download the code and test it for yourself!