Wakatta!

Like Eureka!, only cooler

Seven Languages in Seven Weeks Haskell Day 3.5

Haskell Day 3 had one exercise I forgot about: to implement monads in a different language. In this post I correct this oversight.

There are various implementations of monads for other languages. Some are well suited for the exercise (because they have a flexible syntax like Clojure, for instance). With others the whole thing sticks out like a sore thumb. I think the latter is useful to highlight Haskell’s features.

I choose Java, which shows how helpful Haskell’s syntax and type system really is, compared to a mainstream language. Regarding types, maybe generics would have helped, but I’m not familiar enough with them to figure it out (for professional reasons, I got stuck with Java 1.4 for quite a long time).

I implements a List Monad, and creates a list of pairs where the first element is smaller than the second. In Haskell, this is what it would look like:

List Monad example
1
2
3
4
5
do x <- [1..5]
   y <- [1..5]
   if x < y
     then return (x,y)
     else fail "Not a valid pair"

Haskell’s notation for functions is especially useful here. Note how the Java codes forces me to tie MakePair1 and MakePair2, while the Haskell equivalent seems to have no special construct whatsoever (the do notation hides the underlying anonymous functions).

(ListMonad.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package test.monad;

import java.util.ArrayList;
import java.util.List;

/* Java type system is not rich enough to be used here.
 * Even with generics, some expression do not typecheck,
 * so I use Object everywhere
 */
@SuppressWarnings({ "rawtypes", "unchecked" })
public class ListMonad {
  private List content;
  private ListMonad(final List content) {
      this.content = new ArrayList(content);
  }
  
  ListMonad bind(Func func) {
      ArrayList res = new ArrayList();
      
      for (Object obj: content) {
          res.addAll(func.run(obj).getContent());
      }
      
      return new ListMonad(res);
  }
  
  static ListMonad wrap(Object obj) {
      ArrayList res = new ArrayList();
      res.add(obj);
      
      return new ListMonad(res);
  }
  
  // error param is not used in ListMonad
  static ListMonad fail(String error) {
      return new ListMonad(new ArrayList());
  }
  
  public List getContent() {
      return content;
  }

  interface Func {
      ListMonad run(Object obj);
  }    
  
  static ListMonad monadDo(List lst) {
      return new ListMonad(lst);
  }
  
  public static void main(String [] args) {
      List output = monadDo(Sequence.makeRange(1, 5)).bind(new MakePair1()).getContent();
      
      for (Object obj: output) {
          System.out.println(obj);
      }
  }
}

class MakePair1 implements ListMonad.Func {
  public ListMonad run(Object obj) {
      ListMonad.Func func = new MakePair2(obj);
      return ListMonad.monadDo(Sequence.makeRange(1, 5)).bind(func);
  }
}

class MakePair2 implements ListMonad.Func {
  private Object content;
  public MakePair2(final Object obj) {
      this.content = obj;
  }
  
  public ListMonad run(Object obj) {
      Integer cont = (Integer) content;
      Integer val = (Integer) obj;
      if (cont.intValue() < val.intValue())
          return ListMonad.wrap(new Pair(content, obj));
      else
          return ListMonad.fail("Not a valid pair");
  }
}

@SuppressWarnings({ "rawtypes", "unchecked" })
class Sequence {
  static List makeRange(int from, int to) {
      ArrayList lst = new ArrayList();
      
      for (int i = from; i <= to; i++) lst.add(i);
      
      return lst;
  }
}

class Pair {
  private Object fst;
  private Object snd;
  
  public Pair(final Object fst, final Object snd) {
      this.fst = fst;
      this.snd = snd;
  }
  
  public String toString() {
      return "(" + getFst() + ", " + getSnd() + ")";
  }

  public Object getFst() {
      return fst;
  }

  public Object getSnd() {
      return snd;
  }
}

The implementation is otherwise fairly straightforward given the definition of monads:

  • monadDo and wrap (Haskell’s return) both create a new ListMonad;
  • fail is also a way to create a ListMonad which represents failure. I pass a String argument to have the same signature as Haskell’s fail, but in List Monads such argument is ignored, so I ignore it here as well;
  • bind is the >>= version, which collects the results of the func argument run over each element of the current List content; a new ListMonad with the results as content is returned
  • finally, getContent gives back the current content of the ListMonad.

The test code is nothing fancy (I certainly wouldn’t want to try and write my maze solving algorithm in Java using the ListMonad), but it tests all the features.

Running it produces the expected output:

1
2
3
4
5
6
7
8
9
10
(1, 2)
(1, 3)
(1, 4)
(1, 5)
(2, 3)
(2, 4)
(2, 5)
(3, 4)
(3, 5)
(4, 5)

Aren’t you glad you can write this in Haskell instead?

Comments