Polymorphism using generics.
Published: 2022-12-17 23:21:32


One common way to achieve polymorphism in programming languages is through the use of generics. Generics allow developers to specify a placeholder type in their code, which can then be filled in with a specific type at runtime.

In the case of a ordered queue, we want to be able to specify whether it should be a min queue, a max queue, or follow some other ordering function. One approach we can take is to use a generic type A and specify that it must implement the Ord trait. This would allow us to use the Ord function generated by A to order the elements in the queue.

```
struct OrdQueue[A : Ord] {
    ...
}
```
However, this approach has a limitation: we can't use a non-default implementation of Ord for a particular type, since each type has a unique implementation of the Ord trait. This means that we can't use a single data structure to create both a min queue  and a max queue.

To overcome this limitation, we can take a different approach and define our OrdQueue struct to take a function ord as a parameter, rather than relying on the Ord trait. This function will be used to compare elements in the queue.

```
struct OrdQueue[A] {
   ord: Fn (A, A) -> bool
}

def newOrdQueue[A](f: Fn (A, A) -> bool) -> OrdQueue[A] {
   OrdQueue { ord: f }
}
```
This approach allows us to specify any ordering function we want, rather than being limited to the default implementation of Ord. However, it does require us to provide an ordering function even when the Ord trait is already implemented for the type A.
   
It is possible to combine the two approaches we discussed earlier and create a queue that can accept either the default implementation of Ord for a particular type, or a custom implementation specified by the user.

One way to achieve this is to specify a default parameter for the Ord trait. This default parameter will be used when a ord trait is required only if the user does not provide a custom implementation.

With this approach, the user can create an OrdQueue for a particular type A in two ways:

Without specifying a custom implementation of Ord, in which case the default implementation will be used.
By specifying a custom implementation of Ord, which will override the default.
For example, if we want to create an OrdQueue for Int values that uses the custom implementation of Ord, we can do so like this:
```
const reverseOrd = impl Ord for Int {
    fn greater(x: Int, y: Int) -> bool { x < y}
}

b = OrdQueue[Int: reverseOrd]
```
If we want to create an OrdQueue for Int values that uses the default implementation of Ord that provides a reverse ordering, we can do so like this:
```
a = OrdQueue[Int] which is translated too
a = OrdQueue[Int: default]
```

This approach allows us to create a queue that can adapt to a wide range of ordering requirements, while still providing a default implementation for cases where a custom implementation is not needed.

Every function call must have an unambiguous default impl for the type.

To find the default implementation of a trait, we can follow a set of rules similar to the "orphan rules" in Rust. These rules ensure that there is only one possible default implementation for a particular trait and type, and that it can be easily located by the compiler.

According to the rules we outlined, the search for the default implementation of a trait follows the following steps:

Check the current function for the parameter. If the parameter is annotated with a generic type of the trait, we defer to the implementation provided by the user of the function.

First we check the trait crate and the type crate. If the trait is defined in a different crate than the type, and that crate defines a default implementation for the type, use that implementation.

We then check the current crate, and finally we check the crate where the function is defined. It's important to note that every crate must have an unambiguous default implementation for the type in question. This means that if a crate define default implementations for the same type (with the same specificity), the compiler will raise an error, as it will not be able to determine which implementation to use.

It's important to note that when searching for the default implementation of a trait, the more specific implementation will always be preferred over a more general implementation, as long as both are defined within the same crate.

For example, consider the two implementations of Ord that you provided:

```
impl Ord for A(B, C) where B: Ord and C: Ord {
    fn greater(x: A, y: A) -> bool { x.1 > y.1 or (x.1 = y.1 and x.2 > y.2)}
}

impl Ord for (String, String){
     fn greater(x: (String, String) y: (String, String)) -> bool {
    x.1.concat(x.2) > y.1.concat(y.2)
}
```
If both of these implementations are defined within the same crate, the second implementation will be used as the default for the tuple (String, String), since it is more specific than the first implementation.

However, if the first implementation is defined in a crate that is searched before the crate where the second implementation is defined, the first implementation will be used as the default for the tuple (String, String), even though it is less specific. This is because the search for the default implementation follows a specific order, and the more specific implementation will only be preferred if it is found in the same crate.