Type of recursively-types functions

42 views
Skip to first unread message

AnandA

unread,
Oct 28, 2017, 1:59:31 AM10/28/17
to ceylon-users
Hello. I would like to know if there is a way to achieve some kind of recursively-typed functions in Ceylon. (I am not an expert in FP, so please correct any mistaken assumptions.) For example, I can define combinatory logic in Ceylon in a type-safe way like so:

class Fi(shared Fi(Fi) o) { }

Fi veritas =
   
Fi((Fi t) =>
       
Fi((Fi f) =>
          t
));
Fi perfidas =
   
Fi((Fi t) =>
       
Fi((Fi f) =>
          f
));
Fi si =
   
Fi((Fi l) =>
       
Fi((Fi m) =>
         
Fi((Fi n) =>
             l
.o(m).o(n))));

print(si.o(veritas).o(veritas).o(perfidas) == veritas);
print(si.o(perfidas).o(veritas).o(perfidas) == perfidas);
print(si.o(veritas).o(perfidas).o(veritas) == perfidas);
print(si.o(perfidas).o(perfidas).o(veritas) == veritas);

This code works as intended. However, for clarity, brevity, and applicability to other problems, I would like to be able to do implement this behavior using only functions. Take something like the following (nonfunctional) example:

alias Fi => Fi(Fi);

Fi veritas(Fi t)(Fi f) => t;
Fi perfidas(Fi t)(Fi f) => f;
Fi si(Fi l)(Fi m)(Fi n) => l(m)(n);

print(si(veritas)(veritas)(perfidas) == veritas);
print(si(perfidas)(veritas)(perfidas) == perfidas);
print(si(veritas)(perfidas)(veritas) == perfidas);
print(si(perfidas)(perfidas)(veritas) == veritas);


In the function alias version, the Fi type represents functions whose operands and return values can be composed indefinitely. Note that due to their recursive nature, the types Fi, Fi(Fi), and Fi(Fi)(Fi) could be considered functionally equivalent; all that the consumer of any of them knows is that if they have a function that, if called on a Fi, will given them another Fi.

Here is my understanding of what Ceylon currently supports.
  • Recursive aliases are not supported due to being erased during compilation.
  • I am unaware of any current Ceylon feature that could be used to specialize the Callable type recursively or otherwise get the needed kind of infinite chaining.
  • There is a github issue on higher order generics that has been around for several years; would we need that feature to get this functionality? I don't see a release tagged for it, but I did see it on the to-do list on the Eclipse project application page.

Thanks!

Paul Ebermann

unread,
Oct 30, 2017, 8:16:45 PM10/30/17
to ceylon...@googlegroups.com
2017-10-28 7:59 GMT+02:00 AnandA <abu...@gmail.com>:

This code works as intended. However, for clarity, brevity, and applicability to other problems, I would like to be able to do implement this behavior using only functions. Take something like the following (nonfunctional) example:

alias Fi => Fi(Fi);

Fi veritas(Fi t)(Fi f) => t;
Fi perfidas(Fi t)(Fi f) => f;
Fi si(Fi l)(Fi m)(Fi n) => l(m)(n);

print(si(veritas)(veritas)(perfidas) == veritas);
print(si(perfidas)(veritas)(perfidas) == perfidas);
print(si(veritas)(perfidas)(veritas) == perfidas);
print(si(perfidas)(perfidas)(veritas) == veritas);
 
Even if the types would work out, with pure callables you don't have any notion of equality, so your prints would all show `false`.

AnandA

unread,
Oct 30, 2017, 9:00:04 PM10/30/17
to ceylon-users
I believe that it would work for the same reason that the current member-function-based implementation already does work: reference equality.

In any case, the point of the example is to demonstrate the behavior of the type that I am attempting to express within Ceylon.
Reply all
Reply to author
Forward
0 new messages