4

I asked this question a while ago - the answers were really helpful, and as I read them and the questions that were linked - I also saw this, and the first answer I think really addresses what I thought was the essence of the more powerful type system.

I was trying to really understand the pseudo-implementation of the functor that the author gives in his example - and I wondered if anyone can give me a slightly simpler explanation of this part of his answer.

Directly quoted from the answer - it's these bits that I don't quite get.

for this block of code.

interface Functor<A> {
    Functor<B> map(Function<A, B> f);
}
  1. The type system doesn't allow us to express the invariant that the map method always returns the same Functor subclass as the receiver.
  2. Therefore, there's no statically type-safe manner to invoke a non-Functor method on the result of map.

Is a simple way of looking at this that in a concrete implementation of Functor, you can declare what you want to use as A, but not what you want to use as B, or even the B is the same on both sides of the map function?

More generall, my slightly simplistic interpretation of this is that single-kinded types really mean that it limits how far you can "reach" or "specify" the contract you are trying to specify with your types. With higher kinded types, you get much more flexibility on how you specify your types, i.e you can constrain and bind your functions more specifically that you can with simple java generics.

... or I really it could be that I just don't understand what a Type Constructor is or why it's useful!

2 Answers 2

4

About the point 1., let's discuss it with an example:

class Maybe<A> implements Functor<A> {
  public <B> Functor<B> map(Function<A, B> f) {
    // implementation....
  }
}

class List<A> implements Functor<A> {
  public <B> Functor<B> map(Function<A, B> f) {
    return new Maybe<B>(); // error, but I can do this
  }
} 

See the problem? The map implementation of List is returning Maybe just because Maybe implements Functor. This is about the power of the type system: I want to say that map not only returns a Functor but it returns a very specific Functor.

About the point 2., type safety, I think the problem described by the post is the following: let's imagine that you want to call the get(0) method on the list and you want to call it after you call map

list.map(...).get(0) // error because Functor doesn't have add

You have to actually downcast the return of map to List.

((List<B>)list.map(...)).get(0)

In a language like Haskell, the fmap function takes a Functor F and returns another instance of that Functor F, so one can do:

 head (fmap (...) list)
4

It is helpful to look at Haskell code from the original answer:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Here f denotes the same type in both f a (argument) and f b (result).


In Java version, Functor<B> in result doesn't guarantee that it's the same Functor as in Functor<A>. Let's start with correct example:

// This functor is totally OK: map returns the same type
class ContainerFunctor<A> implements Functor<A> {
    private final A element;

    public ContainerFunctor(A element) {
        this.element = element;
    }

    public ContainerFunctor<B> map(Function<A, B> f) {
        return new ContainerFunctor<B>(f.apply(element)); 
    }
}

// Usage:

ContainerFunctor<Integer> intF = new ContainerFunctor<Integer>(123);
ContainerFunctor<String> strF = intF.map(new Function<Integer, String> {
    public String apply(Integer i) {
        return i.toString();
    }
});

Here intF and strF are the same kind of functors, ContainerFunctor, which is expected behavior of a functor.

Now let's see how it can be violated:

class BrokenFunctor implements Functor<A> {
    private final A element;

    public BrokenFunctor(A element) {
        this.element = element;
    }

    // it SHOULD return BrokenFunctor, but type system can't force it
    Functor<B> map(Function<A, B> f) {
        return new ContainerFunctor<B>(f.apply(element));
    }
}

// Usage:

BrokenFunctor<Integer> intF = new BrokenFunctor<Integer>(123);

// Broken!
BrokenFunctor<String> strF = (BrokenFunctor<String>) intF.map(new Function<Integer, String> {
    public String apply(Integer i) {
        return i.toString();
    }
});

The Java's type system is weaker in this case: there is no way to force BrokenFunctor.map to return another BrokenFunctor as a result. This is bad because we cannot tell what kind of functor we will end up with after calling map. We still can make it right by discipline (telling everyone about the additional implicit contract of an interface), but there is no way to force it. So, if you ever create an interface like Functor, you can't force all possible implementations to be correct.


The type system doesn't allow us to express the invariant that the map method always returns the same Functor subclass as the receiver

True: in example above, BrokenFunctor.map doesn't return BrokenFunctor.

Therefore, there's no statically type-safe manner to invoke a non-Functor method on the result of map.

Also true: we have to cast the result of BrokenFunctor.map to ContainerFunctor to make it work:

// not type-safe!
ContainerFunctor<String> strF = (ContainerFunctor<String>) intF.map(new Function<Integer, String> {
    public String apply(Integer i) {
        return i.toString();
    }
});

And again, in case of ContainerFunctor casting is not needed, but there is no way to force all implementations to behave this way.

2
  • 2
    Note that if you're only dealing with kind * (i.e. non-generic classes/interfaces) it's possible to write static methods that behave correctly. Here's a (contrived) example using Integers and Doubles: ideone.com/6NuhDD But this doesn't get you very far without higher-kinded types, having to pass in the typeclass explicitly sucks, and it'll most likely confuse all of your peers.
    – Doval
    Apr 28, 2015 at 23:40
  • This is a real help.. I guess the key point is in java, you an only tell the type system to return "a (i.e, any) functor", not "the specific functor you want" & the only way round it is to to try and generate all possible subclasses - which is clearly silly.
    – phatmanace
    Apr 29, 2015 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.