Existential (phantom ?) type parameters on constructors

[gneuvill]

Hey, me again,

the following haskell idiom seems currently not expressible using derive4j :

data Stream a = forall s. Stream (s -> Step a s) s

Would it be possible to allow that kind of construct :

@Derive4J(flavour = Flavour.FJ)
abstract class Stream<A> {
  interface Cases<R, A, S> {
    R Stream(Unlifted<S> s, F<S, Step<A, S>> stepper, S init);
  }
  abstract <R, S> R match(Cases<R, A, S> cases);
}

or better

@Derive4J(flavour = Flavour.FJ)
abstract class Stream<A> {
  interface Cases<R, A> {
    <S> R Stream(Unlifted<S> s, F<S, Step<A, S>> stepper, S init);
  }
  abstract <R> R match(Cases<R, A> cases);
}

What do you think ?

[jbgi]

Yes, this is something that I wanted to add to the roadmap (and also planned by adt4j in sviperll/adt4j#15 and sviperll/adt4j#38).
I started working on this and

@Data(flavour = Flavour.FJ)
abstract class Stream<A> {
  static class Step<A, S> {/*...*/}
  interface Cases<R, A> {
    <S> R Stream(F<S, Step<A, S>> stepper, S init);
  }
  abstract <R> R match(Cases<R, A> cases);
}

should totally be doable. The main pain point is that I cannot use lambdas anymore to instantiate Cases when there is type parameters on constructors.

[gneuvill]

The main pain point is that I cannot use lambdas anymore to instantiate Cases when there is type parameters on constructors.

Argh ! This is unfortunate indeed. Would it affect the user interface ?

[jbgi]

Well, it will impact pattern matching: you will need to either use method reference or traditional instantiation of a (anonymous) class

[gneuvill]

Oh noes... And my first proposition ? (phantom type on the Cases interface ?)

[jbgi]

I think in the first proposition you would be forced to use Object as type argument for S when pattern matching... would be kind of ugly, no?

[gneuvill]

Even by threading the type all along ?

Streams.<A, S>cases()
  .Stream(...)

or with the match method :

myStream.<A, S>match(...)

(assuming S is introduced in the scope anyhow (method, class, whatever...)

[jbgi]

mmm... where does S would come from? if you try to actually implement the Stream constructor, I can not see how it would work out. the semantic is completely different.

[gneuvill]

Yeah, I was considering things on the user side only but I've not (yet) looked at your code and the way it generates its (immensely beneficial ) mess...

[gneuvill]

Indeed, this

public abstract class Stream<A> {
    private Stream() {}

    protected abstract <S, R> R match(F3<Unlifted<S>, F<S, Step<A, S>>, S, R> f);

    private static final class Impl<A, S> extends Stream<A> {
        final Unlifted<S> us;
        final F<S, Step<A, S>> stepper;
        final S init;

        private Impl(Unlifted<S> us, F<S, Step<A, S>> stepper, S init) {
            this.us = us;
            this.stepper = stepper;
            this.init = init;
        }

        @Override
        protected <S, R> R match(F3<Unlifted<S>, F<S, Step<A, S>>, S, R> f) {
            return f.f(us, stepper, init);
        }
    }
}

obviously doesn't compile...

[jbgi]

@gneuvill what I meant is that even without speaking of the code-generation part, the first proposition is impossible to implement:

abstract class Stream<A> {
  interface Cases<R, S, A> {
    R Stream(F<S, Step<A, S>> stepper, S init);
  }
  abstract <R, S> R match(Cases<S, R, A> cases);

  static <S1, A> Stream<A> Stream(F<S1, Step<A, S1>> stepper, S1 init) {
    return new Stream<A>() {
      @Override <S2, R> R match(Cases<S2, R, A> cases) {
        F<S2,Step<A,S2>> _stepper = ???;
        S2 _init = ???;
        return cases.Stream(_stepper, _init);
      }
    };
  }
}

[jbgi]

😄

[gneuvill]

Je comprends vite mais faut m'expliquer longtemps...

[clinuxrulz]

I know this is an old issue, but I've seen a solution to this in purescript.

data Stream a = forall s. Stream (s -> Step a s) s

is really ment to be

data Stream a = exists s. Stream (s -> Step a s) s

_exists_ because there is only one type for s but we do not know what it is.

You can define a helper class Exists that does the same as: https://pursuit.purescript.org/packages/purescript-exists/0.2.0/docs/Data.Exists

Or you can also mimic an exists qualification using codensity.

That is: exists a. F a is isomorphic to forall r. (forall a. F a -> r) -> r where F is Stream in this case.

[clinuxrulz]

This is my first time trying derive4j. I believe the following is one possible solution:

https://gist.github.com/clinuxrulz/0a56108f31bafa1452b7b38eba198285

Edit: Also if you want to define the Exists class your gonna need higher kinded types. (The hkt project)

Edit: Example: Creating a Stream of natural numbers (including 0).

        Stream<Integer> nats =
            Streams.Stream(
                new ExistsSStreamF<Integer>() {
                    @Override
                    public <R> R apply(ForallSStreamF<Integer, R> f) {
                        return f.apply(
                            StreamFs.StreamF(
                                (Integer x) -> Steps.Step(x, x + 1),
                                0
                            )
                        );
                    }
                }
            );

Little bit messy.

[gneuvill]

Hi @clinuxrulz,

Here is the reasoning I followed to transcribe the Free datatype from scalaz in java (using derive4j and hkt) :

as you noted, forall on value constructors denotes an existential quantification in haskell. And in java, existentials are encoded with ? (wildcards). Now, the problem with ? is that each occurrence of it in a signature refers to a unique type. Hence the solution I've opted for in my encoding of Free to use an inner type (Free.Sub) that captures the whole signature and to existentially quantify it in the constructor declaration (R Gosub(Sub<f, A, ?> sub) in the gist below).

See https://gist.github.com/gneuvill/ec3f7c434549a19eefe7697e9549a849 for the complete example.

What I like in this encoding is that it makes use of the 'true' java existentials in a type safe way ; however the drawbacks of this approach is that you must use helper methods to 'capture' the wildcard (resumeGosub, resumeSubGosub, stepGosub, stepSubGosub and foldMapGosub in the gist) and that you must pay the price of a wrapper type (Sub).

[clinuxrulz]

@gneuvill I like it, and I did not know Java could do that. I'll remember that trick.