# Parametric Polymorphism

This chapter will introduce you to the concept of parametric polymorphism and show you how to parameterize your functions using type arguments, and your types using type parameters.

## The Need for Polymorphism

Thus far, none of the functions you have written so far have been parameterized by type. Here is an example implementation of a function that reverses a list of integers.

``defn reverse-list (xs:List<Int>) -> List<Int> :   if empty?(xs) :      xs   else :      append(         reverse-list(tail(xs))         List(head(xs)))``

But notice that it only works on integers. Thus the following does not compile.

``reverse-list(List("Timon", "and", "Pumbaa"))``

It gives this error.

``Cannot call function reverse-list of type List<Int> -> List<Int> with arguments of type (FullList<String>).``

To handle this, we can write an overloaded version of `reverse-list` that accepts a list of strings.

``defn reverse-list (xs:List<String>) -> List<String> :   if empty?(xs) :      xs   else :      append(         reverse-list(tail(xs))         List(head(xs)))``

Now `reverse-list` will work on both integers and strings. So the following

``println(reverse-list(List(1, 2, 3)))println(reverse-list(List("Timon", "and", "Pumbaa")))``

compiles and prints out

``(3 2 1)("Pumbaa" "and" "Timon")``

However, the code for the string version of `reverse-list` is identical to the integer version, save for its type signature. This is an obvious duplication of effort. Also, this is clearly a subpar solution. What if we next want to reverse a list of characters? It is not practical to define an overloaded version of `reverse-list` for every type of list we wish to reverse.

### The Limitations of the ? Type

What we need is the ability to call `reverse-list` on lists of any type. Well, we've already learned about one mechanism that will allow us to do this: the `?` type. So let's replace our two overloaded `reverse-list` functions with a single one that accepts a `List<?>` as its argument.

``defn reverse-list (xs:List) -> List :   if empty?(xs) :      xs   else :      append(         reverse-list(tail(xs))         List(head(xs)))``

Recall that the default type parameter is `?` for a type without explicit type parameters. Thus `List` is equivalent to `List<?>`. The above definition of `reverse-list` will allow us to call both lists of integers and strings. Try out the following code again

``println(reverse-list(List(1, 2, 3)))println(reverse-list(List("Timon", "and", "Pumbaa")))``

and verify that it still prints out

``(3 2 1)("Pumbaa" "and" "Timon")``

It seems to work fine now on these cases. What is the problem?

The problem is in the type of the result of the `reverse-list` function. `reverse-list` is annotated to return a `List<?>`. Thus the following obviously incorrect code will still compile.

``val xs = reverse-list(List("Timon", "and", "Pumbaa"))println(head(xs) + 1)``

When the compiled program is ran, it crashes with this error.

``FATAL ERROR: Cannot cast value to type.   at core/core.stanza:2619.12   at test.stanza:15.8``

This is disappointing. The reverse of a list of strings is obviously still a list of strings. So `head(xs)` should be a `String`, and Stanza should have stopped us from trying to add an integer to it. More precisely, what we need is the ability for `reverse-list` to accept lists of any type, but have it also return lists of the same type.

In place of `reverse-list`, we'll instead call the `reverse` function included in Stanza's core library, and see that it does not suffer from these problems.

``val xs = reverse(List("Timon", "and", "Pumbaa"))println(head(xs) + 1)``

Attempting to compile the above gives this error.

``No appropriate function plus for arguments of type (String, Int). Possibilities are:   plus: (Byte, Byte) -> Byte at core/core.stanza:2488.21   plus: (Int, Int) -> Int at core/core.stanza:2619.12   plus: (Long, Long) -> Long at core/core.stanza:2688.21   plus: (Float, Float) -> Float at core/core.stanza:2742.21   plus: (Double, Double) -> Double at core/core.stanza:2792.21``

which is much more reassuring. We'll now see how we can write such functions ourselves.

## Explicit Type Arguments

Here is how to write a polymorphic `reverse-list` function that takes an explicit type argument.

``defn reverse-list<ElementType> (xs:List<ElementType>) -> List<ElementType> :   if empty?(xs) :      xs   else :      append(         reverse-list<ElementType>(tail(xs))         List(head(xs)))``

`reverse-list` takes a single type argument called `ElementType` that represents the type of the elements inside the `xs` list. Now we need to provide a type argument to `reverse-list` when we call it.

``reverse-list<Int>(List(1, 2, 3))``

What that does is instantiate a version of `reverse-list` by replacing `ElementType` with `Int` in its type signature. Thus the instantiated function has type

``List<Int> -> List<Int>``

and we then call it with `List(1, 2, 3)`.

Let's use our polymorphic function to reverse lists of integers and strings.

``val xs = reverse-list<Int>(List(1, 2, 3))val ys = reverse-list<String>(List("Timon", "and", "Pumbaa"))println(xs)println(ys)``

Compiling and running the above prints out the same message as before.

``(3 2 1)("Pumbaa" "and" "Timon")``

Let's also verify that the return type of `reverse-list` is of the proper type.

``val xs = reverse-list<String>(List("Timon", "and", "Pumbaa"))println(head(xs) + 1)``

Attempting to compile the above gives this error.

``No appropriate function plus for arguments of type (String, Int). Possibilities are:   plus: (Byte, Byte) -> Byte at core/core.stanza:2488.21   plus: (Int, Int) -> Int at core/core.stanza:2619.12   plus: (Long, Long) -> Long at core/core.stanza:2688.21   plus: (Float, Float) -> Float at core/core.stanza:2742.21   plus: (Double, Double) -> Double at core/core.stanza:2792.21``

So the return type is correct, and Stanza properly catches our mistakes.

Note that we are responsible for instantiating a correct version of `reverse-list` to call. If we pass in the wrong type arguments,

``reverse-list<String>(List(1, 2, 3))``

then the program will fail to compile. The above gives this error when we attempt to compile it.

``Cannot call function reverse-list of type List<String> -> List<String> with arguments of type (FullList<Int>).``

As a comment on programming style, the purpose of each type argument in a polymorphic function is typically quite obvious. Thus programmers do not feel the need to give them descriptive names. Here is how `reverse-list` would commonly be written.

``defn reverse-list<T> (xs:List<T>) -> List<T> :   if empty?(xs) :      xs   else :      append(         reverse-list<T>(tail(xs))         List(head(xs)))``

The vast majority of type arguments are simply named `T` (short for `Type`), or `S` (because it's a letter close to `T`).

## Captured Type Arguments

Our polymorphic `reverse-list` function can now reverse lists of any type and also correctly returns a list of the same type. It's just a little cumbersome to use because we have to pass in the element type of the list we're reversing each time. This is because `T` is declared as an explicit type argument. We'll see now how to have Stanza automatically infer the type argument by declaring it as a captured type argument.

Here is a polymorphic `reverse-list` written using a captured type argument.

``defn reverse-list<?T> (xs:List<?T>) -> List<T> :   if empty?(xs) :      xs   else :      append(         reverse-list(tail(xs))         List(head(xs)))``

A captured type argument is declared with a `?` prefix, which indicates that it is not passed in explicitly. Instead, it is captured from the types of the arguments it is called with. The type signature above says that `reverse-list` requires a list to be passed in for `xs`. Capture `T` from the element type of `xs`.

Now we can call `reverse-list` without passing in an explicit type argument.

``reverse-list(List(1, 2, 3))``

The argument `List(1, 2, 3)` has type `List<Int>`, and thus the type argument `T` captures the element type `Int`.

In the following call,

``reverse-list(List("Timon", "and", "Pumbaa"))``

the argument `List("Timon", "and", "Pumbaa")` has a type `List<String>`, and thus the type argument `T` captures the element type `String`.

Let's try our example of reversing both integer lists and string lists again.

``val xs = reverse-list(List(1, 2, 3))val ys = reverse-list(List("Timon", "and", "Pumbaa"))println(xs)println(ys)``

Notice that we no longer need to pass in type arguments. Compiling and running the above prints out

``(3 2 1)("Pumbaa" "and" "Timon")``

We can also verify that the return type is correct.

``val xs = reverse-list(List("Timon", "and", "Pumbaa"))println(head(xs) + 1)``

Attempting to compile the above gives this error.

``No appropriate function plus for arguments of type (String, Int). Possibilities are:   plus: (Byte, Byte) -> Byte at core/core.stanza:2488.21   plus: (Int, Int) -> Int at core/core.stanza:2619.12   plus: (Long, Long) -> Long at core/core.stanza:2688.21   plus: (Float, Float) -> Float at core/core.stanza:2742.21   plus: (Double, Double) -> Double at core/core.stanza:2792.21``

Thus the `reverse-list` function is now polymorphic and it does not require any explicit type arguments. We've finished generalizing `reverse-list` at this point, and it actually now has the same type signature as the `reverse` function in the core library.

### Capture Locations

Here's another example polymorphic function.

``defn store-in-odd-slots<?T> (xs:Array<?T>, v:T) -> False :   for i in 1 to length(xs) by 2 do :      xs[i] = v``

`store-in-odd-slots` is a polymorphic function that accepts an array, `xs`, and an item, `v`, and stores `v` at every odd index in `xs`. Let's try it out.

``val xs = to-array<String>(["Patrick", "Sunny", "Luca", "Whiskey", "Emmy", "Rummy"])store-in-odd-slots(xs, "and")println(xs)``

prints out

``["Patrick" "and" "Luca" "and" "Emmy" "and"]``

Let's now take a closer look at the type signature of `store-in-odd-slots`.

``defn store-in-odd-slots<?T> (xs:Array<?T>, v:T) -> False``

The `?T` following the function name

``store-in-odd-slots<?T>``

means that the function is polymorphic and accepts a single captured type argument. The argument list

``(xs:Array<?T>, v:T)``

contains two references to `T`, but only one of them is prefixed with a `?`. This means that `T` is captured only from the element type of `xs`.

The capture location for `T` was chosen carefully. Consider the following type definitions.

``deftype Shapedeftype Circle <: Shape``

where all circles are also shapes, but not all shapes are circles.

The following usage of `store-in-odd-slots`

``val shapes = Array<Shape>(10)store-in-odd-slots(shapes, new Circle)``

compiles correctly. `T` is captured from the element type of `Array<Shape>`, and is thus `Shape`. The instantiated `store-in-odd-slots` therefore has type

``(Array<Shape>, Shape) -> False``

and can be suitably called with `shapes` and `new Circle`.

But this next usage

``val circles = Array<Circle>(10)store-in-odd-slots(circles, new Shape)``

fails with this error

``Cannot call function store-in-odd-slots of type (Array<Circle>, Circle) -> Falsewith arguments of type (Array<Circle>, Shape).``

This is consistent with our intuition. You cannot store an arbitrary shape into an array that can only hold circles. As an exercise, think about what would happen if `store-in-odd-slots` was instead declared the following way.

``defn store-in-odd-slots<?T> (xs:Array<T>, v:?T) -> False``

As a general rule of thumb, the majority of polymorphic functions operate on a collection of some sort. The type argument is almost always captured from the element type of the collection.

### Multiple Capture Locations

After reading the previous section, you might be naturally wondering what happens when there are multiple capture locations. If there are multiple capture locations, then the final captured type is the union of all the types captured from each location.

Here is an example of a function that makes use of two capture locations.

``defn append-lists<?T> (xs:List<?T>, ys:List<?T>) -> List<T> :   if empty?(xs) : ys   else : cons(head(xs), append-lists(tail(xs), ys))``

The type argument `T` is captured from both the element type of `xs` and the element of type `ys`. Thus if we call `append-lists` on a list of integers and a list of strings,

``val xs = List(1, 2, 3)val ys = List("Timon", "and", "Pumbaa")val zs = append-lists(xs, ys)``

then the resulting type of `zs` is `List<Int|String>`.

### Example: map-list

Let's try writing our own polymorphic `map` function on lists. We'll call ours `map-list`. `map-list` accepts a function, `f`, and a list, `xs`, and returns a new list containing the results of calling `f` on each item in `xs`. To start off, here's the function definition without any type annotations.

``defn map-list (f, xs) :   if empty?(xs) :      List()   else :      val y = f(head(xs))      val ys = map-list(f, tail(xs))      cons(y, ys)``

Let's verify that it works as intended.

``val xs = to-list(["Timon", "and", "Pumbaa" "are", "good", "friends"])val lengths = map-list(length, xs)println(lengths)``

Compiling and running the above prints out

``(5 3 6 3 4 7)``

Let's start off with figuring out the type of `xs`, because it seems easier. It's a list for sure, and `map-list` should be able to work on lists of any type. So `xs` is therefore of type

``xs:List<?T>``

and `T` is a captured type argument for `map-list`.

Next, let's figure out the type of `f`. It's a function for sure, and it's called with only a single argument. So it's at least

``f:? -> ?``

Next we know that `f` is called with items from `xs`, which is a list of `T`'s, so `f` has to accept `T`'s. Now we know it's at least

``f:T -> ?``

Finally, what is `f` allowed to return? Well, `f` is allowed to return anything actually. So let's introduce another captured type argument. The final type of `f` is

``f:T -> ?S``

Now that we know the types of its arguments, the last step is to figure out what `map-list` returns. We know that it returns a list, and we also know that the list contains the results of calling `f`. Since we now know that `f` returns `S`'s, therefore `map-list` returns a list of `S`'s. Here is the complete type signature for `map-list`.

``defn map-list<?T,?S> (f:T -> ?S, xs:List<?T>) -> List<S>``

Let's try our test code again with our typed `map-list` function and ensure it works as expected.

``val xs = to-list(["Timon", "and", "Pumbaa" "are", "good", "friends"])val lengths = map-list(length, xs)println(lengths)``

Running the above prints out

``(5 3 6 3 4 7)``

as before.

To double check the inferred return type of `map-list`, let's cast `lengths` to an obviously incorrect type, and read what Stanza says about its type.

``lengths as False``

Compiling the above gives us the error

``Cannot cast expression of type List<Int> to type False.``

So Stanza says that `lengths` is a list of integers, which is correct.

### Example: map-both

Here's some more practice on using captured type arguments. Here is the un-annotated definition for the `map-both` function.

``defn map-both (f, g, xs) :   for x in xs map :      [f(x), g(x)]``

`map-both` accepts two functions, `f` and `g`, and a list, `xs`, and returns a list containing two-element tuples. The first elements in all the tuples are the results of calling `f` on each item in `xs`, and the second elements in all the tuples are the results of calling `g` on each item in `xs`.

Similar to before, the list, `xs`, is the easiest argument to figure out the type signature for.

``xs:List<?T>``

`f` needs to be a function that can be called with items from `xs`, and can return anything.

``f:T -> ?S``

`g` also needs to be a function that can called with items from `xs`, and can also return anything.

``g:T -> ?R``

`map-both` returns a list of tuples. The first elements in the tuples are results of calling `f`, and the second elements are results of calling `g`.

``List<[S, R]>``

Thus the complete definition for `map-both` is

``defn map-both<?T,?S,?R> (f:T -> ?S, g:T -> ?R, xs:List<?T>) -> List<[S, R]> :   for x in xs map :      [f(x), g(x)]``

Let's try it out on a list of strings.

``val xs = to-list(["Timon", "and", "Pumbaa", "are", "good", "friends"])val zs = map-both(   xs,   fn (x) : x[2]   fn (y) : length(y) * 2)println(zs)``

which prints out

``(['m' 10] ['d' 6] ['m' 12] ['e' 6] ['o' 8] ['i' 14])``

Let's cast `zs` to something silly to see what Stanza says about its type. Attempting to compile the following

``zs as False``

gives us this error.

``Cannot cast expression of type List<[Char, Int]> to type False.``

So `zs` has type `List<[Char, Int]>`, which is what we expect.

## Parametric Types

You have been shown how to define your own types using `deftype` and also the shorthand `defstruct`. But none of the types you've defined thus far accept type parameters. This stood out the most in our definition of the `Stack` type which was only able to store String objects. We'll now learn how to declare our own parametric types.

### Declaring a Parametric Type

Here is an example of a simple type that takes two type parameters.

``deftype Either<L,R>``

`Either` contains two wrapped objects, a left object of type `L`, and a right object of type `R`.

This is all there is to defining a parametric type! The rest of this section covers mechanisms that have already been introduced, but we'll go through them in the context of the `Either` type for practice.

### Declaring Multis

Let's define the fundamental operations for an `Either` object, which are simply getter functions for retrieving the two wrapped objects.

``defmulti left<?L> (e:Either<?L,?>) -> Ldefmulti right<?R> (e:Either<?,?R>) -> R``

Notice that the `left` and `right` functions each take only a single type argument. The other type parameter for the `Either` object is left as `?` to indicate that it is free to be anything.

### Creating Either Objects

Now let's write a constructor function for creating `Either` objects. We'll start with a function that can only create `Either<Int,String>` objects.

``defn Either (l:Int, r:String) :   new Either<Int,String> :      defmethod left (this) : l      defmethod right (this) : r``

Let's try it out.

``val e = Either(42, "Timon")println("The left object is %_." % [left(e)])println("The right object is %_." % [right(e)])``

prints out

``The left object is 42.The right object is Timon.``

### Polymorphic Constructor Function

Now that we can successfully create specific `Either` objects, let's generalize our constructor function by making it polymorphic using type arguments. The following declares `Either` as taking two explicit type arguments, one for each wrapped object.

``defn Either<L,R> (l:L, r:R) :   new Either<L,R> :      defmethod left (this) : l      defmethod right (this) : r``

Now `Either` objects are created in the following way.

``val e = Either<Int,String>(42, "Timon")``

The way in which `Either` objects are created now resembles how we've been creating many of the other types included in the core library, such as arrays and vectors. This is not a coincidence. The construction function for arrays and vectors are also just regular functions that take explicit type arguments and return instances of parametric types.

### Parametric Structs

The `defstruct` expression also accepts type parameters for creating parametric structs. As mentioned previously, the `defstruct` expression is simply a syntactic shorthand for declaring a new type, getter functions for its fields, and a default construction function. Thus all the code we've written previously to define the `Either` type can be neatly expressed as

``defstruct Either<L,R> :   left: L   right: R``

### Constructor Function with Captured Arguments

Specifically for creating `Either` objects, it is also not necessary to have the user explicitly specify the types of the left and right objects. Let's make the constructor function more convenient to call by using captured type arguments.

``defn Either<?L,?R> (l:?L, r:?R) :   new Either<L,R> :      defmethod left (this) : l      defmethod right (this) : r``

Now we can create an `Either` object like this

``val e = Either(42, "Timon")``

and have Stanza automatically infer that `e` is an `Either<Int,String>` based on the types of `42` and `"Timon"`.

### When not to Use Captured Arguments

We showed above how to write a constructor function using captured arguments that did not require the left and right object types to be passed in explicitly to `Either`. This makes the constructor function for `Either` objects very similar to the constructor function for `List` objects, which also does not require any explicit type arguments. This is not always an appropriate thing to do.

Let us suppose that `Either` is a mutable datastructure; that we can change the left and right objects after the object has been created. The type definition for `Either` would stay the same, but it would gain two more fundamental operations.

``defmulti left<?L> (e:Either<?L,?>) -> Ldefmulti right<?R> (e:Either<?,?R>) -> Rdefmulti set-left<?L> (e:Either<?L,?>, v:L) -> Falsedefmulti set-right<?R> (e:Either<?,?R>, v:R) -> False``

Notice, especially, the capture locations of the type arguments in the setter functions.

The constructor function would be changed to now accept not the left and right objects, but the initial left and right objects, since they may change later on.

``defn Either<?L,?R> (l0:?L, r0:?R) :   var l = l0   var r = r0   new Either<L,R> :      defmethod left (this) : l      defmethod right (this) : r      defmethod set-left (this, v:L) : l = v      defmethod set-right (this, v:R) : r = v``

For the next part, let us again assume that we have definitions for some basic shapes.

``deftype Shapedeftype Circle <: Shapedeftype Rectangle <: Shapedefmethod print (o:OutputStream, c:Circle) : print(o, "Circle")defmethod print (o:OutputStream, r:Rectangle) : print(o, "Rectangle")``

Let's try creating a mutable `Either` object now.

``defn my-favorite-shape () -> Shape :   new Circleval e = Either(42, my-favorite-shape())println("After creation:")println("The left object is %_" % [left(e)])println("The right object is %_" % [right(e)])set-left(e, 256)set-right(e, new Rectangle)println("\nAfter mutation:")println("The left object is %_" % [left(e)])println("The right object is %_" % [right(e)])``

Compiling and running the above prints out

``After creation:The left object is 42The right object is CircleAfter mutation:The left object is 256The right object is Rectangle``

Everything seems to be working, but pay attention to what happens next.

The type signature for `my-favorite-shape` is not as precise as it could be. It's annotated to return `Shape`, but it's more precise to say that it returns `Circle`. So let's improve `my-favorite-shape`'s type signature.

``defn my-favorite-shape () -> Circle :   new Circle``

Now try compiling and running the program again. It will now give this error.

``Cannot call function set-right of type (Either<?, Circle>, Circle) -> False with arguments of type (Either<Int, Circle>, Rectangle).``

What is going on? Why would changing (actually improving) the type signature for `my-favorite-shape` affect the later call to `set-right`?

The problem, as is evident in the error message, is that the inferred type for `e` is `Either<Int, Circle>`. This is not right. Even though the initial right object was a `Circle`, that doesn't mean we want `e` to only ever hold `Circle` objects as its right object.

This is one of those cases where using a captured type argument is inappropriate. For a mutable `Either` object, the types of the left and right objects should be passed in explicitly.

Here is the constructor function rewritten to use explicit type arguments.

``defn Either<L,R> (l0:L, r0:R) :   var l = l0   var r = r0   new Either<L,R> :      defmethod left (this) : l      defmethod right (this) : r      defmethod set-left (this, v:L) : l = v      defmethod set-right (this, v:R) : r = v``

And here is our original test code rewritten to pass in explicit type arguments.

``defn my-favorite-shape () -> Shape :   new Circleval e = Either<Int, Shape>(42, my-favorite-shape())println("After creation:")println("The left object is %_" % [left(e)])println("The right object is %_" % [right(e)])set-left(e, 256)set-right(e, new Rectangle)println("\nAfter mutation:")println("The left object is %_" % [left(e)])println("The right object is %_" % [right(e)])``

Verify that it still compiles and runs correctly.

At this point, we can try making the same change to `my-favorite-shape`'s type signature.

``defn my-favorite-shape () -> Circle :   new Circle``

This time, however, the program still compiles and continues to run as before.

Here are the basic rules of thumb for choosing between using explicit or captured type arguments. If you're creating an immutable object then feel free to use captured type arguments. If you're creating a mutable object, then use explicit type arguments.

These issues surrounding captured type arguments and mutable objects is also why `to-array` and `to-vector` require explicit type arguments and why `to-list` does not.

## Match Expressions and Type Erasure

One subtlety concerning Stanza's parametric type system is a concept called type erasure. It roughly means that, given a program, if we replace every type argument with the `?` type, it should still run and compute the same result (providing that the original program doesn't fail). Said another way, the setting of a type argument can never change what is computed by a program.

Here is an example of incorrectly attempting to use a type argument to affect which branch is taken in a match expression.

``defn check-if<T> (x) :   match(x) :      (x:T) : true      (x) : false``

Let's try it out on a `String` object.

``println(check-if<Int>("Timon"))``

Compiling and running the above prints out

``FATAL ERROR: Cannot cast value to type.   at test.stanza:15.8   at test.stanza:18.8``

Here is what is happening underneath. The dispatch type in a match branch has all of its type arguments and parametric types erased. Thus the code above is equivalent to the following

``defn check-if<T> (x) :   match(x) :      (y:?) :         val x = y as T         true      (y:?) :         false``

and the error message arises because `y` cannot be cast to a `T` object. We intentionally designed Stanza so that there is no possible way to write a function such as `check-if`.

## Revisiting Stack

At this point, we have all the requisite knowledge for writing a parametric version of our `Stack` class from chapter 6. Here are our old definitions for the `Stack` type and its fundamental operations.

``deftype Stack <: Collection<String>defmulti push (s:Stack, x:String) -> Falsedefmulti pop (s:Stack) -> Stringdefmulti empty? (s:Stack) -> True|False``

A `Stack` is declared to be a collection of strings, and its fundamental operations allow us to push and pop strings from it.

Here is the original constructor function.

``defn Stack (capacity:Int) -> Stack :   val items = Array<String>(capacity)   var size = 0   new Stack :      defmethod push (this, x:String) :         if size == capacity : fatal("Stack is full!")         items[size] = x         size = size + 1      defmethod pop (this) :         if size == 0 : fatal("Stack is empty!")         size = size - 1         items[size]      defmethod empty? (this) :         size == 0      defmethod print (o:OutputStream, this) :         print(o, "Stack containing [")         print-all(o, join(this, " "))         print(o, "]")      defmethod to-seq (this) :         take-n(size, items)``

### Parametric Type Declaration

The first step is to declare `Stack` as a parametric type.

``deftype Stack<T> <: Collection<T>``

Thus, `Stack` now takes a type parameter, `T`, that indicates what types of objects the stack may hold, and is also no longer a collection of strings. It is now a collection of `T`'s.

### Polymorphic Fundamental Operations

The second step is to declare its fundamental operations as polymorphic functions.

``defmulti push<?T> (s:Stack<?T>, x:T) -> Falsedefmulti pop<?T> (s:Stack<?T>) -> Tdefmulti empty? (s:Stack) -> True|False``

both `push` and `pop` now accept a captured type argument, `T`, that indicates the element type of the stack object. Here are some points to take note of. Notice that the `x` argument for `push` is not a capture location for `T`. This is consistent with our earlier discussion in the section on capture locations. Also notice that the `empty?` multi is unchanged, as the types of the objects in a stack are not needed to check whether the stack is empty.

### Polymorphic Constructor Function

The last step is to make its constructor function polymorphic.

``defn Stack<T> (capacity:Int) -> Stack<T> :   val items = Array<T>(capacity)   var size = 0   new Stack :      defmethod push (this, x:T) :         if size == capacity : fatal("Stack is full!")         items[size] = x         size = size + 1      defmethod pop (this) :         if size == 0 : fatal("Stack is empty!")         size = size - 1         items[size]      defmethod empty? (this) :         size == 0      defmethod print (o:OutputStream, this) :         print(o, "Stack containing [")         print-all(o, join(this, " "))         print(o, "]")      defmethod to-seq (this) :         take-n(size, items)``

The constructor function now takes an explicit type argument, `T`, indicating the element type of the stack object, and returns a `Stack<T>`. Notice that the backing array, `items`, is no longer an `Array<String>`. It is now declared as an `Array<T>` in order to hold the items in the stack. `push` now also accepts a `T` value instead of a `String` value. The rest of the function is unchanged.

### Trying It Out

Let's try out our parametric `Stack` type using a variation of our original test code.

``defn main () :   val s = Stack<Int>(10)   for x in [1, 5, 2, 42, -11, 2, 5, 10, -42] do :      push(s, x)   println("1. Contents of s")   println(s)   println("\n2. Index of 42")   println(index-of(s, 42))   println("\n3. Does it contain any negative numbers?")   println(any?({_ < 0}, s))   println("\n4. Are all numbers negative?")   println(all?({_ < 0}, s))   println("\n5. What are the negative numbers?")   val cap-s = filter({_ < 0}, s)   println-all(join(cap-s, ", "))   println("\n6. What are its unique elements?")   println(unique(s))main()``

Compiling and running the above prints out

``1. Contents of sStack containing [1 5 2 42 -11 2 5 10 -42]2. Index of 4233. Does it contain any negative numbers?true4. Are all numbers negative?false5. What are the negative numbers?-11, -426. What are its unique elements?(1 5 2 42 -11 10 -42)``

Our parametric stack type is now quite general. It can hold items of different types, and it supports all the operations in the core sequence library. Actually, the `Array` and `Vector` types in the core library are defined in much the same way as `Stack`.