How do you implement Haskell's IO type in Java?

Question

This is my first attempt:

import java.util.function.*;
import java.util.ArrayList;
public class IO<A> {
    private Function<World,Tuple<World,A>> transform;
    private class World {
        private ArrayList<String> stdin;
        private ArrayList<String> stdout;
        public World() {
            this.stdin  = new ArrayList<String>();
            this.stdout = new ArrayList<String>();
        }
    }
    private class Tuple<F,S> {
        public F fst;
        public S snd;
        public Tuple(F fst, S snd) {
            this.fst = fst;
            this.snd = snd;
        }
    }
    public IO(Function<World,Tuple<World,A>> transform) {
        this.transform = transform;
    }
    public IO<A> pure(A a) {
        return new IO<A>(r -> new Tuple<World,A>(r,a));
    }
    public <B> IO<B> bind(IO<A> io, Function<A,IO<B>> f) {
        return new IO<B>(r -> {
            Tuple<World,A> result = io.transform.apply(r);
            IO<B> ioB = f.apply(result.snd);
            return ioB.transform.apply(result.fst);
        });
    }
}

But when I try to compile this I get the following error:

IO.java:29: error: incompatible types: IO<B>.World cannot be converted to IO<A>.World
            Tuple<World,A> result = io.transform.apply(r);
                                                        ^
  where B,A are type-variables:
    B extends Object declared in method <B>bind(IO<A>,Function<A,IO<B>>)
    A extends Object declared in class IO

What I don't understand is the world class has no relationship to the type variable but javac thinks it does. What am I doing wrong?

Answer 1

Leaving aside the fidelity of your approach to replicating Haskell's IO type in Java:

The compiler thinks that the A in your bind method's signature is the same as the A in the class definition. You've told us it's not in words. In order to communicate that to the compiler, you need to make things static and introduce a couple of method-level type parameters:

import java.util.function.*;
import java.util.ArrayList;
public class IO<A> {
    private Function<World,Tuple<World,A>> transform;
    private static class World {
        private ArrayList<String> stdin;
        private ArrayList<String> stdout;
        public World() {
            this.stdin  = new ArrayList<String>();
            this.stdout = new ArrayList<String>();
        }
    }
    private static class Tuple<F,S> {
        public F fst;
        public S snd;
        public Tuple(F fst, S snd) {
            this.fst = fst;
            this.snd = snd;
        }
    }
    private IO(Function<World,Tuple<World,A>> transform) {
        this.transform = transform;
    }
    public static <A> IO<A> pure(A a) {
        return new IO<A>(r -> new Tuple<World,A>(r,a));
    }
    public static <A,B> IO<B> bind(IO<A> io, Function<A,IO<B>> f) {
        return new IO<B>(r -> {
            Tuple<World,A> result = io.transform.apply(r);
            IO<B> ioB = f.apply(result.snd);
            return ioB.transform.apply(result.fst);
        });
    }
}

Answer 2

I think an "operational monad" approach is better for explaining the essence of Haskell I/O. The Haskell version can be quite simple:

data PrimOp a where
  PutStr :: String -> PrimOp ()
  GetLine :: PrimOp String
  -- Whatever other primitives you want

data MyIO a where
  Pure :: a -> MyIO a
  Bind :: !(MyIO a) -> (a -> MyIO b) -> MyIO b
  LiftPrim :: !(PrimOp a) -> MyIO a

instance Functor MyIO where
  fmap = liftM

instance Applicative MyIO where
  pure = Pure
  (<*>) = ap

instance Monad MyIO where
  (>>=) = Bind

The MyIO values aren't some magical world-passing functions; they're just plain data. We can interpret the data to actually perform the action represented if we so desire:

runPrimOp :: PrimOp a -> IO a
runPrimOp (PutStr s) = putStr s
runPrimOp GetLine = getLine

runMyIO :: MyIO a -> IO a
runMyIO (Pure a) = pure a
runMyIO (Bind m f) = runMyIO m >>= runMyIO . f
runMyIO (LiftPrim prim) = runPrimOp prim

It would actually be possible to write a Haskell compiler whose IO type looks a lot like MyIO, and whose runtime system interprets values of that type directly.

---

I have attempted a translation to Java below. I've never really been a Java programmer, and it's been a long time since I used it at all, so this may be terribly unidiomatic or even wrong. I imagine you'd probably want to use some version of the "visitor pattern" to represent interpretations of Bind and Pure (bringing things into the realm of something general like Control.Monad.Operational), while using a run method for a PrimOp subclass of IO. Since I don't really know the right Java way I've tried to just keep it simple.

public interface IO <A> {
  public A run ();
}

public final class Pure <A> implements IO <A> {
  private final A val;
  Pure (A x) { val = x; }
  public A run () {
      return val;
      }
}

The tricky bit is Bind, which needs existential quantification. I don't know the idiomatic way to do this in Java, so I did something awkward that seems to work. Namely, I wrote an auxiliary class OpenBind that exposes two type variables, and then a class Bind that wraps up an OpenBind leaving one of those variables wild.

import java.util.function.Function;

public final class Bind <A> implements IO <A> {
    private final OpenBind <?,A> ob;

    public <B> Bind (IO <B> m, Function <B,IO <A>> f) {
        ob = new OpenBind <B,A> (m, f);
    }

    public A run() {
        return (ob.run());
    }

    private final static class OpenBind <Fst,Snd> {
        private final IO <Fst> start;
        private final Function <Fst, IO <Snd>> cont;
        public OpenBind (IO <Fst> m, Function <Fst, IO <Snd>> f) {
            start = m;
            cont = f;
        }
        public final Snd run () {
            Fst x = start.run();
            IO <Snd> c = cont.apply(x);
            return (c.run());
        }
    }
}

The primops themselves are pretty simple (I couldn't find a Java equivalent of () so I wrote my own Unit):

public class PutStr implements IO <Unit> {
  private String str;
  public PutStr (String s) {
      str = s;
  }
  public Unit run () {
      System.out.print(str);
      return Unit.unit;
  }
}

public final class Unit {
  private Unit () {}
  public static final Unit unit = new Unit ();
}

public class GetLine implements IO <String> {
    private GetLine () {}
    public static final GetLine getLine = new GetLine ();
    public String run () {
      // Replace the next line with whatever you actually use to
      // read a string.
      return "";
  }
}