Deep pattern-matching

[sviperll]

Following @nobeh comment in #15

Let's consider this psuedo/modelling code:

data Map<A, B> = EmptyMap | InsertAssoc(Pair<A, B>, Map<A, B>);

which defines a Map data structure in ADT composed of an EmptyMap and an InsertAssoc operation. And, it is quite straightforward to map the above to:

@GenerateValueClassForVisitor
@Visitor(selfReferenceVariableName = "SELF", resultVariableName = "M")
public interface MapVisitor<M,SELF,A,B> {
  M EmptyMap();
  M InsertAssoc(Pair<A, B> argPair, SELF argMap);
}

Now, I have a different challenge to deal with, which generally is under the class of "pattern matching" which is addressed in this library by using the visitor pattern. Consider the following:

def Map<A, B> put(Map<A, B> ms, A k, B v) =
  case ms {
    EmptyMap => InsertAssoc(Pair(k, v), EmptyMap);
    InsertAssoc(Pair(k_, v_), ts) => if (k == k_)
      then
        InsertAssoc(Pair(k_, v), ts)     
      else 
        InsertAssoc(Pair(k_, v_), put_(ts, k, v))
      ;
  };

The above is a put function that defines how to an insert operation to a Map. My question is how would you generally translate this example of pattern matching with deep matching structure to a visitor pattern?

I thought that this might be relevant into this ticket but if not, please feel free to move into a new ticket.

[nobeh]

Thanks for creating this ticket.

[sviperll]

I think the general solution is just nested calls to accept method (this is what Haskell/ML compilers internally do for you):

class Map<K, V> {
    Map<K, V> put(final K k, final V v) {
        return accept(new MapVisitor<Map<K, V>, Map<K, V>, K, V>) {
            Map<K, V>  EmptyMap() {
                return InsertAssoc(Pair.Pair(k, v), this);
            }
            Map<K, V>  InsertAssoc(final Pair pair, final Map<K, V> ts) {
                return pair.accept(new PairVisitor<K, V, Map<K, V>>() {
                    Map<K, V> Pair(final K k1, final V v1) {
                        return k.equals(k1) ? InsertAssoc(Pair.Pair(k, v), ts) : InsertAssoc(pair, ts.put(k, v))
                    }
                });
            }
        });
    }
}

But with your particular example there are at least two work arounds.

1. Just use getters

class Map<K, V> {
    Map<K, V> put(final K k, final V v) {
        return accept(new MapVisitor<Map<K, V>, Map<K, V>, K, V>) {
            Map<K, V>  EmptyMap() {
                return InsertAssoc(Pair.Pair(k, v), this);
            }
            Map<K, V>  InsertAssoc(final Pair pair, final Map<K, V> ts) {
                return k.equals(pair.getFst()) ? InsertAssoc(Pair.Pair(k, v), ts) : InsertAssoc(pair, ts.put(k, v));
            }
        })
    }
}

1. Inline Pair

@GenerateValueClassForVisitor
@Visitor(selfReferenceVariableName = "SELF", resultVariableName = "M")
public interface MapVisitor<M,SELF,A,B> {
  M EmptyMap();
  M InsertAssoc(A key, B value, SELF argMap);
}

[nobeh]

Not intending to pursue a dispute of comparison of different libraries targetting the same problem areas, what's derive4j standpoint on this topic, @jbgi?

[jbgi]

@nobeh there will be no fundamental difference with derive4j, only the lambda syntax can make things more readable:

@Data
public abstract class Map<A,B> {

    public interface MapVisitor<A,B, M> {
        M EmptyMap();
        M InsertAssoc(Pair<A, B> argPair, Map<A,B> argMap);
    }

    public abstract <M> M accept(MapVisitor<A,B, M> visitor);

    public static <A, B> Map<A,B> put(Map<A, B> ms, A k, B v) {
        return ms.accept(visitor(

                () -> InsertAssoc(pair(k, v), EmptyMap()),

                (argPair, argMap) -> k.equals(argPair.left())
                        ? InsertAssoc(pair(k, v), ms)
                        : InsertAssoc(argPair, put(ms, k, v))
        ));
    }
}

Now if you want pattern guards syntactic sugar you may want to use https://github.com/aol/cyclops/tree/master/cyclops-pattern-matching or http://javaslang.github.io/javaslang-docs/2.0.0-RC3/#_match

Also with derive4j you can nest fluent pattern matches when cases have only one argument.

[nobeh]

Thanks for the note. Actually, we've had a few trials with a few libraries include aol-cyclops, others such as motif. In the end none of them actually help us in the context of deep pattern matching.

Our motivation is in the context of generating programming language source code such as Java and Haskell from ABS that is a concurrent object modelling language. For a language such as Haskell, this is quite straightforward. However, for a language such as Java, it becomes an obstacle.

I have not had javaslang under my radar. I will give it a try.

cc @rudi, @bezirg, @vlad-serbanescu

[sviperll]

With pure visitors you can probably somewhat solve the problem by implementing all possible destruction patterns in visitor with abstract class or default methods.

Like this

    abstract class AbstractMapVisitor<A, B, R> implements MapVisitor<A, B, R> {
        abstract R EmptyMap();

        R InsertAssocWithPairAndEmptyMap(A key, B value);

        R InsertAssocWithPairAndInsertAssoc(A key, B value, Pair<A, B> entry2, Map<A, B> map);

        R InsertAssocWithPair(final A key, final B value, Map<A,B> argMap) {
            return argMap.accept(new MapVisitor<A, B, R>() {
                R EmptyMap() {
                    return InsertAssocWithPairAndEmptyMap(key, value);
                }
                R InsertAssoc(Pair<A, B> entry2, Map<A, B> map) {
                    return InsertAssocWithPairAndInsertAssoc(key, value, entry2, map);
                }
            });
        }

        R InsertAssoc(Pair<A, B> argPair, final Map<A,B> argMap) {
            return argPair.accept(new PairVisitor<A, B, R>() {
                R Pair(A first, B second) {
                    return InsertAssocWithPair(first, second, argMap);
                }
            });
        }
    }

So your original put method will look like this:

class Map<A, B> {
    Map<A, B> put(A key, B value) {
        return accept(new AbstractVisitor<A, B, Map<A, B>>() {
            Map<A, B> EmptyMap() {
                return Map.InsertAssoc(Pair.Pair(key, value), Map.EmptyMap());
            }
            Map<A, B> InsertAssocWithPair(A key1, B value1, Map<A, B> map) {
                if (key.equals(key1))
                    return Map.InsertAssoc(Pair.Pair(key, value), map);
                else 
                    return Map.InsertAssoc(Pair.Pair(key1, value1), map.put(key, value));
            }
        });
    }
}