interface Same {
  public boolean same(Object other);
}

interface FoldFun {
  public Object value(Object v, Object r);
}

interface MapFun {
  public Object value(Object v);
}

interface List {
  Object fold(final FoldFun f, Object v);
  List map(final MapFun f);
  String toString();
}

abstract class ListImpl implements List {
  abstract public Object fold(final FoldFun f, Object v);

  public List map(final MapFun f) {
    return
      (List) this.fold(
               new FoldFun() {
                 public Object value(Object v, Object r) {
                   return new Pair(f.value(v), (List)r); }},
               new Nil());
  }

  public String toString() {
    return "( " + 
           this.fold(
             new FoldFun() {
               public Object value(Object v, Object r) {
                 return (v.toString()) + " " + ((String) r);
               }},
             "") +
           ")";
  }
}

class Nil extends ListImpl {
  public Object fold(FoldFun f, Object v) {
    return v;
  }
}

class Pair extends ListImpl {
  private Object fst;
  private List snd;

  Pair (Object fst, List snd) {
    this.fst = fst;
    this.snd = snd;
  }

  public Object fold(FoldFun f, Object v) {
    return f.value(fst, snd.fold(f,v));
  }
}

////////////////////////////////////////

class OurInt implements Same {
  public int i;

  OurInt(int i) {
    this.i = i;
  }

  public boolean same(Object other) {
    return (this.i == ((OurInt)other).i);
  }

  public String toString() {
    return String.valueOf(i);
  }
}

class Test {
  static List subst(final Same old, final Object nw, List ls) {
    return 
      ls.map(
        new MapFun() {
          public Object value(Object v) {
            if (old.same(v)) {
              return nw; }
            else {
              return v; }
          }
        });
  }

  static List insert(final Object nw, final Same old, List ls) {
    return (List)
             ls.fold(
               new FoldFun() {
                 public Object value(Object v, Object r) {
                   if (old.same(v)) {
                     return new Pair(nw, new Pair(v, (List)r)); }
                   else {
                     return new Pair(v,(List)r); }
                 }
               },
             new Nil());
  }

  public static void main(String argv[]) {
    OurInt one = new OurInt(1);
    OurInt two = new OurInt(2);
    OurInt three = new OurInt(3);
    OurInt twohundred = new OurInt(200);
    List l = new Pair(one, new Pair(two, new Pair(three, new Nil())));

    List r1 = subst(two, twohundred, l);
    System.out.println("Result of subst: " + r1.toString());

    List r2 = insert(twohundred, two, l);
    System.out.println("Result of insert: " + r2.toString());
  }
}


/*   PART 2

1. m4
2. m2
3. ambiguous
4. m4
5. no match
6. m4
7. no match
8. m2
9. m1
10.m3

 */