Constrained genericity

Constrained genericity
You are encouraged to solve this task according to the task description, using any language you may know.

Constrained genericity means that a parametrized type or function (see Parametric Polymorphism) can only be instantiated on types fulfilling some conditions, even if those conditions are not used in that function.

Say a type is called "eatable" if you can call the function eat on it. Write a generic type FoodBox which contains a collection of objects of a type given as parameter, but can only be instantiated on eatable types. The FoodBox shall not use the function eat in any way (i.e. without the explicit restriction, it could be instantiated on any type). The specification of a type being eatable should be as generic as possible in your language (i.e. the restrictions on the implementation of eatable types should be as minimal as possible). Also explain the restrictions, if any, on the implementation of eatable types, and show at least one example of an eatable type.

Ada

Ada allows various constraints to be specified in parameters of a generics. A formal type constrained to be derived from certain base is one of them: <ada> with Ada.Containers.Indefinite_Vectors;

package Nutrition is

  type Food is interface;
  procedure Eat (Object : in out Food) is abstract;

  package Food_Boxes is
     new Ada.Containers.Indefinite_Vectors
         (  Index_Type   => Positive,
            Element_Type => Food'Class
         );
  subtype Food_Box is Food_Boxes.Vector;

end Nutrition; </ada> The package Nutrition defines an interface of an eatable object, that is, the procedure Eat. Then a container package is instantiated with the elements to of the class Food. I.e. the elements can be only the members of the class. Example of use: <ada> type Banana is new Food with null record; overriding procedure Eat (Object : in out Banana) is null;

type Tomato is new Food with null record; overriding procedure Eat (Object : in out Tomato) is null; </ada> We have declared Banana and Tomato as a Food. <ada>

  Lunch_Box : Food_Box;

begin

  Lunch_Box.Append (Banana'(null record));
  Lunch_Box.Append (Banana'(null record));
  Lunch_Box.Append (Tomato'(null record));

</ada> The lunch box contains two banana and one tomato.

C++

The current C++ standard doesn't support constrained genericity (however you can emulate it by having the container refer to the corresponding eat function without actually calling it). The next version will, however, allow it through concepts: <cpp>

1. include <concepts>
2. include <vector>

auto concept Eatable<typename T> // auto makes it apply automatically {

 void eat(T);

};

template<std::Moveable T>

requires Eatable<T>

class FoodBox { public:

 std::vector<T> food;

}; </cpp> The only requirement to implement an Eatable type is, indeed, that a suitable function eat is defined for it (to put it in the FoodBox, in addition it has to be Moveable, since std::vector requires that; but that's ortogonal to the type being Eatable). A possible implementation of an eatable type could be: <cpp> class Banana {}; void eat(Banana const &) {} </cpp> Even a built-in type can be made eatable by defining a suitable eat function. The following makes double an eatable type: <cpp> void eat(double) {} </cpp>

Another way to make an existing type eatable is to use a concept map. Let's assume we have an abstract base class Food which looks like this; <cpp> class Food { public:

 virtual void munch() = 0;
 virtual ~Food() {}

}; </cpp> Then we can make all classes derived from Food eatable using Food::munch() for eat with the following concept map template: <cpp> template<std::DerivedFrom<Food> T>

concept_map Eatable<T>

{

 void eat(T const& t) { t->munch(); }

} </cpp> The difference to a global function void eat(Food const&) is that the function in the concept map is only visible to functions using that concept map, thus reducing namespace polution. Functions directly operating on Food objects can use the interface provided by Food itself, e.g. apple.munch(), or explicitly invoke Eatable<Food>::eat(apple). Of course, concept maps also work with built-in types: <cpp> concept_map Eatable<int> {

 void eat(int) {}

} </cpp>

Haskell

A type class defines a set of operations that must be implemented by a type:

class Eatable a where
  eat :: a -> String

We just require that instances of this type class implement a function eat which takes in the type and returns a string (I arbitrarily decided).

The FoodBox type could be implemented as follows:

data (Eatable a) => FoodBox a = F [a]

The stuff before the => specify what type classes the type variable a must belong to.

We can create an instance of Eatable at any time by providing an implementation for the function eat. Here we define a new type Banana, and make it an instance of Eatable.

data Banana = Foo -- the implementation doesn't really matter in this case
instance Eatable Banana where
  eat _ = "I'm eating a banana"

We can declare existing types to be instances in the exact same way. The following makes Double an eatable type:

instance Eatable Double where
  eat d = "I'm eating " ++ show d

Another way to make an existing type eatable is to declare all instances of another type class instances of this one. Let's assume we have another type class Food which looks like this;

class Food a where
  munch :: a -> String

Then we can make all instances of Food eatable using munch for eat with the following instance declaration:

instance (Food a) => Eatable a where
  eat x = munch x