Feature: Higher order type constructors

Internals & Design
,
1

Apologies if this has already been discussed before. I couldn’t find an issue on GitHub or a discussion on Discourse that seems to address this (though I feel like I remember seeing one before…).

It would be really nice to have type constructors in Julia, and by that, I mean higher order type constructors. For example, it would be nice to be able to do this:

function foo(data::A{T}) where {T,A<:AbstractArray}
   # do something with type A
end

This provides access to the base UnionAll type of data, which is otherwise quite difficult (maybe impossible?) to get without using inttrospection.

One can then use the type A to construct new parametric types like A{C}. You can kind of think of this as a generalization of what similar does for Arrays to any parametric type (though one must still make assumptions about the constructor, of course).

This is a very common pattern in functional programming languages and is really quite powerful.

I don’t know much about the internals of Julia’s compiler, and I’m guessing there’s probably some limitations that might make this difficult or impossible to implement, but I wanted to at least throw the idea out there, in case it hasn’t been discussed before.

If there is an existing clever way to accomplish this that I’m not aware of, please let me know!

1 Like
2

Do you want something like

julia> function foo(x::A) where A<:AbstractArray{T} where T
         Base.typename(A).wrapper{T}
       end
foo (generic function with 1 method)

julia> foo(rand(3))
Array{Float64,N} where N

julia> foo(rand(Int, 3))
Array{Int64,N} where N

julia> foo(rand(3)){2}
Array{Float64,2}

julia> foo(rand(3)){2}(undef, 2, 2)
2×2 Array{Float64,2}:
 5.0e-324  6.94036e-310
 0.0       0.0

?

4 Likes
3

Note that this isn’t really a sensible thing. Not all subtypes use the same type parameters in the same order as the parent. In the case of AbstractArray{T, N}, a common builtin counterexample is BitArray{N}. It only has one type parameter. So were you to do this, you’d end up with an error in that (and many other) case(s).

Really there’s a big hole in our APIs and interfaces in this particular case for AbstractArray. Adapt.jl can help.

6 Likes
4

I don’t quite understand the use case, could you elaborate?

5

Yes, this works for the particular use case I described, but it relies on introspection and internal APIs (i.e. wrapper). What I’m describing would be a way to support it directly through the type system.

6

I disagree.

You can view A{C} as being a union over all parameterized types of this form. You can further constrain A or C and this would narrow the union further.

BitArray{N} would also fit into this pattern. Here, A=BitArray and C=N. No problem there.

I understand the problem that type arguments may not be consistent between child and parent types, but this is a problem of type design, not a problem with the type constructors conceptually. In this case, care would need to be taken in specifying the type bounds if the user intended for T to be the array type. You could also imagine allowing constraints on the constructor itself, i.e. A{T} <: AbstractArray{T}.

One of the use cases for type constructors is in converting between eltypes (@Kolaru mentioned this on Slack). So for example, say you have B{T} <: A{T} and C{T} <: A{T} and you want to write a generic function for converting between element types for all types <:A. Then it would be nice to have:

convert_param(S, a::P{T}) where {T,P<:A} = P(convert(S,fields(a)...))

which would produce P{S} where P is a subtype of A. This works nicely as long as the type hierarchy of A respects an implicit constructor interface.

Many other use cases come up when writing @generated functions or in other settings when you are operating directly on types. For example, you might want to define rules for whether or not certain types are compatible:

iscompatible(::Type{C{T}},Type{B{T}}) where {T,B<:A,C<:A} = false
iscompatible(::Type{B{T}},Type{B{T}}) where {T,B<:A} = true

So here we are saying that all subtypes of A that belong to the same UnionAll family (i.e. the same subtree) are compatible with eachother, but if they belong to different subtrees, they are not.

2 Likes
7

It doesn’t fit into the pattern if you had expected N to behave like the T in AbstractArray{T}. How is Julia to know that? If we had this feature, I guarantee you it’d be an immediate foot-gun for folks trying to do B{Bool} where B<:AbstractArray. Julia can actually represent the type BitArray{Bool} or even BitArray{<:Real}. It’s an unhelpful and unconstructable type, but it’s representable and Julia will happily do type computations on it.

That’s precisely the point. Julia doesn’t know that you decided this particular subtype tree should follow your specific “type parameter-and-implicit-constructor” interface. Instead of demanding your subtypes take care to follow those requirements and implement that particular constructor, you can just demand they implement some function (it could even be the abstract supertype) that takes in the particular type you want to model/construct. Not only is that currently possible, but it’s also more understandable and straightforward. Yes, it becomes more annoying if you could otherwise lean on the implicitly-defined constructor, but someone is defining a function for your subtype somewhere at the end of the chain. One way folks have worked around this is through macros on the struct definition that add additional constructors and other required interface methods.

As for things like iscompatible, the standard way there is through traits.

3 Likes
8

It doesn’t fit into the pattern if you had expected N to behave like the T in AbstractArray{T} . How is Julia to know that?

Simple, I already proposed it. Since type constructors are essentially type-valued functions, it should be possible to specify the constraint where {T,A{T}<:AbstractArray{T}}. Then BitVector would no longer be a valid argument.

I guarantee you it’d be an immediate foot-gun…

You could say this about a lot of things in Julia (or any language)… like slices performing copies, values-as-type-parameters, abstract fields in structs, operator overloading etc. The mere fact that someone can screw-up and misuse a feature is not a sufficient argument not to have it.

Instead of demanding your subtypes take care to follow those requirements and implement that particular constructor, you can just demand they implement some function (it could even be the abstract supertype) that takes in the particular type you want to model/construct.

How is this any different? It’s an implicit interface either way. They’re both, in some way, unclear.

This is really besides the point, though. The core concept behind type constructors is the ability to construct a generic type from other generic types. That’s it.

Maybe I haven’t illustrated good enough use cases here (I’ll certainly post some when I think of them… I’m kind of bad at that), but the fact that this is a standard feature in other languages (Haskell, Scala, F#, etc.) should, I hope, provide some indication that it’s not useless.

As for things like iscompatible , the standard way there is through traits.

“Traits” (quotes because Julia’s trait-like pattern is absolutely not the same as traits in the broader sense) are a poor solution for this. Besides just the overhead of defining the trait type, you would also need to create a separate trait-implementation for every subtype (or at least every subtree). All of this to express what I proposed in just two lines of (much clearer, imho) code. Additionally, there is currently no way to allow a type to have multiple traits which is a huge limitation.

But regardless, the point was not that there is no other solution. It’s that type-constructors provide a simple and intuitive alternative that, in my opinion, would be a valuable option to have.

9

Yes, that’s all I’m trying to say. Only one is currently possible in Julia. The other would make subtyping even more complex than it currently is (estimated at \Pi_2^P-hard or perhaps beyond into PSPACE) or completely undecideable… and it’s only useful at all if your subtype trees follow a particular form that’s not true in general.

10

What do you mean? It would make the compiler’s job harder? I assume this is what you mean, since you referred to time/space complexity.

Haskell has type constructors and is, I think, decidable.

I know Julia isn’t Haskell (and I definitely don’t want it to be), but this is one feature that would be great to have.

11

And also, what I was trying to say, is that I didn’t intend for anyone to get hung up on that one particular example with the constructor pattern. I think the idea of constructing types with generic types is far more general than that.

12

It’s not type-constructors that are troublesome, it’s the ::A{T} where A subtyping (dispatch) relation. And yes, supporting that would be harder to compute, but also harder to reason about, harder to use, and harder to implement. The key part, though, is that it’d be more complex for a benefit that’s only applicable in limited cases and isn’t meaningful in general.

13

I see. I definitely don’t agree that it’s not meaningful in general. The meaning is very clear; A is a UnionAll (or I suppose type name) and T is the type parameter. It’s a union over parametric types. The fact that there are corner cases where the representation of the type parameter is unclear doesn’t change this. I also don’t agree that it’s necessarily harder to use (for one thing, you don’t have to use it…). But I can definitely understand why there would be implementation difficulties.

I have found myself trying to do this multiple times since I started using Julia, but sadly I can’t remember the precise use cases off the top of my head…

14

The way I plan to solve the problem in my use case (reparametrization of few types) is to define explicitly for each type something like the following

reparametrize(b::B, T) = B{T}(b)  # Or wathever is the correct constructor

I think that at the end of the day it is simple enough, while it’s a bit sad we can’t do it in a more generic way.

A similar way to get the UnionAll would be to define for each type for which it makes sense

unionall(::Type{<:B}) = B

I wouldn’t recommend it though, because this is straight up the most confusing function I’ve ever written in Julia and it really looks like it’s doing nothing.

2 Likes
15

@mbauman Is there possibly a less complex compromise here? For example, we could add type constructors, i.e. allowing A{T} where A and T are both generic, but simply disallow dispatch constraints on A? This would actually improve consistency, in my opinion, since Julia currently lets you treat generic types exactly like concrete/direct types in your code except (arbitrarily) when it comes to specifying type arguments.

Under this scheme, the user is allowed to write a function:

reparameterize(b::B{T}, ::S) where {S,B{T}} = B{S}

and perhaps even specify type constraints on B{T}:

reparameterize(b::B{T},::S) where {S,B{T} <: SomeType}

but cannot add constraints to B individually. Then it’s basically just a simple rewrite rule for the compiler since B{T} can be rewritten as a single type parameter R=B{T} for dispatch.

The only complications, as far as I can see, would be:

  1. Enforcing that R is a parametric type, and…
  2. Implementing the syntactic sugar for B=typename(R).wrapper

But maybe I’m missing something.

Edit: Ok one slightly weird thing is how to bind T if the type R=B{T} has more than one type argument. I suppose the most logical thing would be to bind T to the first type argument, though this might be a bit unintuitive from a user’s point of view. Enforcing that R is a parametric type with only one type argument would also perhaps make sense but would, I assume, greatly complicate dispatch.

2 Likes