logo
The Falcon Programming Language
A fast, easy and powerful programming language
Location: Home page >> Falcon wiki
User ID:
Password:
 

Falcon Wiki - Survival:ListComp


List Comprehension

In a realm halfway between the functional and the procedural language paradigms, there's an hybrid region made of lists, and built up on the way you can process them. The king of that reign is the "list comprehension", that is, a formal definition of the contents of a list.

More technically, according to wikipedia:

A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as distinct from the use of map and filter functions.

And more practically, a list comprehension is a compact construct that can be used to create a set starting from another set. In this, it is similar to the map functional operator, but it has two practical advantages: first, the target set needs not to be of the same nature of the original set, and second, it is possible to explicitly specify a source that is not exactly a set, but that can generate items.

Falcon model of list comprehension is a bit more advanced with respect to the base definition, and allows to specify also the nature of the target set. Actually, comprehension in Falcon is performed through the comp() method of sequence classes and items.

Items offering the sequence interface are currently:

  • Arrays
  • Dictionaries
  • Lists
  • Sets

Comprehension components

In Falcon, a comprehension is composed of three elements:

   target_set.comp( generator, filter )

The target_set is the sequence that will receive the elements of the comprehension. It may be empty, but needs not to be. It may be an unordered list (an array, or a List class instance), or constraints its member somehow (as a Set instance, or as a Dictionary).

The generator is a sequence, a range or a generator function returning one item at a time. As a sequence, it can be anything that can be accessed through an iterator.

The filter is an optional element that can provide:

  • A predicate stating which elements can and cannot be part of the target set
  • A modified copy of the items provided by the generator.

In short, the filter is a function (or in general any callable item) that receives two parameters: the item being currently extracted from the generator and the forming set (that is, the target_set itself). If present, its return values will be added to the target set, unless it returns an Out of Band "1", in which case, the elements will be discarded. The filter may also terminate the comprehension returning an out of band 0 integer value.

The comp() method returns the sequence itself, so it is possible to assign the result of a comprehension to a target variable directly as it is formed.

Basic examples

Array of pair values from 2 to 10 (included):

pairs_in_10 = [].comp( [2:11:2] )

Same, as a list:

pairs_in_10 = List().comp( [2:11:2] )

Sorting an unordered list of elements:

sorted = Set().comp( ["oranges", "apples", "peaches", "bananas", "grapes" ] )
for item in sorted: > item 

Lowercase version of an uppercase list:

lcase = [].comp( .[ "A" "b" "Cc" "DDD" ], { v => v.lower() } )

Accepting values below 10:

less_than_10 = [].comp( .[ 1 5 18 3 9 12 15], { v => v < 10 ? v : oob(1)} )

Here, oob(1) asks comp() list to discard this entry.

Warning about duplicate entries (notice that we receive the set as the second parameter of the filter function):

ordered = Set().comp( .[ "N" "C" "N" "D" ], { v, set => 
   if set.contains(v)
      > "Duplicated: ", v
      return oob(1)
   end
   return v 
   } )

for item in ordered: > item

Accepting the first 10 random values (and ordering them):

randomSet = Set().comp( random, { v, set => set.len() == 10 ? oob(0): int(v*100)} )
for item in randomSet: > item

Dictionary comprehension

To form a dictionary comprehension, each item received must be a "pair", that is, a two elements array. For example:

dict = [=>].comp( .[ .[ 'a' 1] .['d' 2] .['c' 3] .['b' 4] ] )
for k,v in dict: > @"$k = $v"

The filter function can be used to turn a sequence with one element in a dictionary. The following example creats a dictionary where each uppercase letter is associated with its UNICODE value.

dict = [=>].comp( [0:26], {v=> ['A'/v, ord('A')+v]} )

Generators

A useful extension of the comprehension system is provided by the generators. A generator is simply a function returning an item at a time (or a pair of item in case the comprehension is dictionary-wise). When the generator declares it has terminated by returning an out of band 0 integer.

For example, the following generator returns a random count of random numbers:

function randrand()
   // terminate 1/10th of times
   if random() > 0.9: return oob(0)
   // otherwise, return a random number
   return random( 1, 10 )
end

rvals = [].comp( randrand )
inspect( rvals )

Using a closure may be more interesting; this creates a lowercase alphabet:

function makeAlphabet()
   m = 'a'
   return function()
      if m > 'z': return ^+ 0
      k = m
      m /= 1
      return k
   end
end

abet = [].comp( makeAlphabet() )

Notice that we used the ^+ mark out of band operator, which is faster and more compact than oob(0), and notice also the UNICODE string increment /=. Finally, notice that makeAlphabet must be called to provide comp() with the new closure it returns.

Another interesting usage of generators involves callable objects, or functors. We can write the above example as:

object doAlpha
  m = 'a'

  function __call()
      if self.m > 'z': return ^+ 0
      k = self.m
      self.m /= 1
      return k
   end
end

abet = [].comp( doAlpha )

Closures are generally more compact and efficient than functors, but functors are more flexible and they may even alter their behavior in during the comprehension. In fact, we may provide a functor method as the filter, so that...

class randgen( count )
  count = count
  
  function __call()
     return random(1,10)    
  end

  function filter( elem, set )
     if set.len() >= self.count: return ^+ 0
     return elem
  end
end

r = randgen(10)   // max 10 elements

rlist = [].comp( r, r.filter )

In the above example, the instance r is used both as a functor to generate the items, and as a filter to determine when the sequence should be considered complete.

Completion comprehensions

As said in the introduction, a comprehension needs not to be performed on an empty sequence. Actually, the items created in the comprehension are added (appended) to the target sequence; for example:

tgt = [1,2,3]
tgt.comp( [0:4], {v=> 'A'/v} )
inspect( tgt )

As seen, the tgt array is modified on place, receiving the items generated by the comprehension.

Custom comprehensions

The comp method can also be applied as an FBOM method to objects and blessed dictionaries exposing a method named append. The method will be called (atomically) for each item generated by the comprehension (after it has been accepted by the filter).

For example, the following code fills an array in an object property:

class MetaArray
  _array = []
  
  function append( data )
     > "Appending: ", data
     self._array.add( data )
  end

  function display()
     > self._array.describe()
  end
end

ma = MetaArray()
ma.comp( [0:3], {x=> x*2} )
ma.display()

The same code can be expressed as a blessed dictionary:

d = bless([
  "array" => [],
  "append" => function( data )
     > "Appending: ", data
     self.array.add( data )
  end
])

d.comp( [0:3], {x=> x*2} )
inspect( d.array )

In this case, the "append" method will take ownership of the comprehension process. In fact, blessed dictionaries cannot normally receive comprehension items as normal dictionaries, unless filtered through an append method.

For/in generators

The for/in loop provides a procedural version of the list comprehension construct. Generators can be used as the source element of the for/in loop, as in the following example:

function makeAlphabet()
   m = 'a'
   return function()
      if m > 'z': return ^+ 0
      k = m
      m /= 1
      return k
   end
end
 
f = makeAlphabet()

for i in f
   forfirst: >> "Alphabeth: "
   >> i
   formiddle: >> ", "
   forlast: > "."
end

Navigation
Go To Page...

Loading

Elapsed time: 0.048 secs. (VM time 0.043 secs.)