# 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));

``````