Specifying Function Contract

Internals & Design
4

This is an interesting take. To me it appears related to the distinction between parametric and ad-hoc polymorphism in Haskell:

  • A generic function is parametric polymorphic if it works with arguments of different types (originally all types, but extended to allow restrictions to certain type classes). Here is an example similar to yours:

    sum :: (Foldable t, Num a) => t a -> a
sum = foldr (+) 0

    The type states precisely the information you want:

    1. The container type[1] t must be Foldable, i.e., implement foldr etc.
    2. The element type a must be Numeric, i.e., implement + etc.

    An important aspect of such a parametric function is that it only has a single implementation which can nevertheless work, e.g., by being instantiated, with different concrete types.

  • A generic function is ad-hoc polymorphic if it’s part of a type-class – which are rather similar to interfaces or traits. In this case, it can have multiple implementations for every concrete type implementing the type class.

    In the above example, foldr is part of the Foldable type-class, and is for instance implemented differently for lists (foldr f z [] = z; foldr f z (x:xs) = f y (foldr f z ys)) or Maybe (foldr f z Nothing = z; foldr f z (Just x) = f x z).

    In this way, a type class specifies which functionality a type must support in order to implement it. From what I understand, Rust uses a similar approach with traits corresponding to the ad-hoc polymorphic part and functions with trait bounds to the parametric polymorphism.

In Julia the situation is considerably more complicated as every function can be written in a generic way, i.e., work for any type adhering to some interface of used methods, as well as being overloaded for different types. In this respect, generic functions could be considered as parametric and ad-hoc polymorphic at the same time. According to this view, your sum example defines a parametric polymorphic function (Imho, the requirement of an iterate method should not be part of it as it’s an implementation detail of reduce – which might or might not actually require it).

Overall, I’m not even sure how to best describe the flexible approach of Julia in a type system at all. Not even considering multiple dispatch which further complicates the situation.

  1. As Haskell has higher-kinded types, the container type t itself can be parametric. Thus, the element type does not need to associated with container, e.g., via eltype, but it’s defined via t a. ↩︎

3 Likes