Bounded Polymorphic Functions

The following examples show the use of polymorphic functions.

The polymorphic function QuickSort has a type parameter X, which is the type of the elements of the list to be sorted. The value parameters are the list to be sorted and the ordering relation for the element of the list. The function is then applied to a list of integers, to sort them in ascending order.

The second example shows a bounded polymorphic function, QuickSortOnK, which is defined through the use of QuickSort. It orders lists of records of type X, which have (at least) an attribute k, of a generic type Y. Note the use of the subtype relation in specifying the generic types. The function is then applied to a list of records, with the field k of type integer. After this, the function is called to sort a set of records with the field k of type string, with the second parameter a lexicographical order relation.

Finally, the last example shows the interaction between polymorphism and views. The function QuickSortOnK is applied to the views of the elements of a class, with the sorting attribute renamed in order to match the type declaration of the function. From the result of the sorting, the elements are extracted again with the original type (so that the expression returns a list of persons).

let rec QuickSort :=
    fun [ElementType] (s: seq ElementType,
                       less:(ElementType # ElementType) -> bool): seq ElementType is
		if emptyseq(s)
		then s
       else use
             p := first(s) and
             r := rest(s)
            in QuickSort[ElementType](
                   (select x from x In r where less(x, p)),
                    less)
               append {p}
               append QuickSort[ElementType](
                         (select x from x In r where Not less(x, p)),
                          less);

let LessThan := fun(x:int, y :int):bool is x < y;
QuickSort [int] ({2;4;3;1;9;5}, LessThan);

let rec QuickSortOnK :=
    fun [FieldType<:any; RecordType<:[k:FieldType]]
          (s: seq RecordType,
             less:(FieldType#FieldType) -> bool): seq RecordType is
        QuickSort[RecordType](s, fun(x:RecordType, y:RecordType):bool is less(x.k,y.k)) ;

QuickSortOnK [int; [k:int; v:string]]
                 ({[k := 4; v := "a"];
                   [k := 2; v := "b"];
                   [k := 3; v := "c"]}, LessThan);

let rec StrLessThan:= fun(x:string, y:string):bool is
   use rec lessThanAscii:= fun(x:seq int, y:seq int):bool is
           if emptyseq(x) then true
           else if emptyseq(y) then false
           else if first(x) = first(y)
                then lessThanAscii(rest(x), rest(y))
                else if first(x) < first(y)
                     then true
                     else false
   in lessThanAscii(explodeascii(x), explodeascii(y));

QuickSortOnK [string; [v:int; k:string]]
                 ({[v := 4; k := "a"];
                   [v := 2; k := "b"];
                   [v := 3; k := "c"]}, StrLessThan);

let Persone class
  Persona <-> [Nome:string; Eta:int] key(Nome);

select x As Persona
  from x In (QuickSortOnK[int; <Persona> view [k:int]]
              (Persone rename* (Eta => k), LessThan));