eclipse-archived/ceylon

FR: Type-transforming functions aka allow transformation of types with type functions

Closed this issue · 13 comments

xkr47 commented

Given a type function*),

<T> => Iterable<T>

it would be nice if we could use these functions to operate on types.

As a simple basic case could be a "map" function that would be available on tuple types.

alias ArrayOf<Arr,<T>> given Arr satisfies Tuple<> => Arr.map(T);

This could be used like:

ArrayOf<A, <T> => Wrapper<T>> wrap<A>(A objs)
    given A satisfies Tuple<>
{
  return objs.collect((a) => Wrapper(a));
  // I guess we would need Tuple to implement a type-safe collect method..?
}

[Wrapper<Integer>, Wrapper<String>] x = wrap([1,"lol"]);

Or directly without type aliases:

Iterable<Arr> join<Arr>(Arr.map(<T> => Iterable<T>) iterables)
    given Arr satisfies Tuple<>
{
   ...
}

Iterable<[String,Integer,Boolean]> joined = join([
  {"lol", "wow", "nice"},
  {1, 2, 3},
  {true, false, false}
]);
print(joined);
// {["lol",1,true], ["wow",2,false], ["nice",3,false]}

WDYT?

Disclaimer: The new syntax shown here probably needs refinement..

*)

gavinking commented

Allowing arbitrary functions on types would introduce undecidability. There is an issue somewhere which mentions the possibility of adding a few built-in type functions to accomplish certain sorts of operations over tuple types. But I don't think we're ever going to let you write your own.

xkr47 commented

Yeah I can't come up with a need for own functions right now..

gavinking commented

Can I close this?

xkr47 commented

I do want to find the original issue though :)

RossTate commented

Allowing arbitrary functions on types would introduce undecidability.

I certainly agree that inferring higher-kinded type arguments is (likely to be) undecidable, but we actually found that having higher-kinded type arguments is still decidable for subtyping.

xkr47 commented

Thanks @RossTate, unfortunately I was perhaps not able to completely follow this; are you saying that it would be possible to implement just the "map" functionality for tuples, possibly with some limitations when it comes to automatically inferring types in expressions when not explicitly stated? If so, could the compiler just require one to explicitly specify the types through either type parameters or declaring the type of the variables where the results of expressions are stored (splitting expressions to smaller units if necessary)?

RossTate commented

I don't really understand the notation in your examples, so it's hard for me to say things concretely about your examples. I'm guessing what I'm saying is that you could have generic methods that take a higher-kinded type parameters (i.e. a type functions) so long as you explicitly specific what that type function is every time you invoke the generic method.

gavinking commented

I don't really understand the notation in your examples

Nor do I, and I think there's a high likelihood we're all talking past each other here.

xkr47 commented

Hi, I haven't really studied this area so I apologize for my lack of vocabulary and conventions to express my ideas..

If we take the second example, my idea was that Arr.map(<T> => Iterable<T>) would take a tuple, say [String, Integer] (as the Arr type argument) and apply the <T> => Iterable<T> mapping to each element of the tuple, which would give us [Iterable<String>, Iterable<Integer>].

Thus, with that example set of type parameters, the signature (or what to call it) of the join method be:

Iterable<[String, Integer]> join<Arr>([Iterable<String>, Iterable<Integer>] iterables)
    given Arr satisfies Tuple<>
{
   ...
}

This idea occured to me when I failed to find another way to create a function that would accept an arbitrary amount of iterables on input and merging elements from each them together into tuples available from the output iterable..

Thanks for taking interest!

gavinking commented

Right, @xkr47, so what you are really asking for is a higher-order type function, let's call it Map<F,S> that applies a second type function F<T> to the element types of a sequence type, taking, for example, [X,Y,Z] and producing [F<X>,F<Y>,F<Z>], or taking [T*] and producing [F<T>*].

Thus, you could write the signature of Tuple.map() like this:

class Tuple<Element,First,Rest> 
        extends Object satisfies [Element+]
        given First satisfies Element
        given Rest satisfies Element[] {

    shared 
    Tuple<Result<Element>, Result<First>, Map<Result,Rest>> 
    map<Result<E>>
            (Result<Element>(Element) collecting) 
            given E satisfies Element;

}

(I think I've written that down correctly!)

I agree that this would be a useful thing to have, but my approach to this problem would be to make Map a type function built-in to the compiler and language specification.

gavinking commented

Note, @xkr47, that this Map is a higher-order type function. That is, it's a type function that accepts a type function. Being a type function, and thus a type, it has an uppercase name, and pointy brackets around its parameters.

zamfofex commented

@gavinking, what if Result is not consistent?

Like, there is nothing saying I can’t write collect<ListMutator> (i.e. collect<<T> => ListMutator<T>>), in which case Result<Element> might not be a supertype of Result<First> (and most likely won’t be).

I can’t seem to find unsoundnesses with that, but I think someone who is smarter than I am could.

The reason I can’t seem to find an unsoundness is that the collecting parameter returns an instance of Result<OldElement>, which is exactly the same as NewElement.

gavinking commented

@Zambonifofex OK, fine, so add an out annotation, perhaps:

    shared 
    Tuple<Result<out Element>, Result<First>, Map<Result,Rest>> 
    map<Result<E>>
            (Result<Element>(Element) collecting) 
            given E satisfies Element;