3

I want to model some mathematical structures. For this purpose I want to define an interface, an abstract class for general purpose algorithms and concrete implementations of that class (I have three in mind).

Now the situation arises that the general purpose algorithms that do not depend on the details of the datastructure, but only depend on the three fundamental methods int Length(), Set<int> DescentSet() and int[] Normalform(). Normally this means that I would use the method template pattern, i.e. I would make these three methods abstract and let the concrete implementations deal with it. But: Those methods are interdependent. I really only need any one of them to define the other two. So I really should only make one of them abstract. But the three intended implementations are exactly different on which of these they would prefer to be the abstract method: The first has an easy time computing Length, the second can easily compute DescentSet and the third gets Normalform for free.

What is the most clean solution for this situation?

3
  • If I understand correctly, you want to avoid 3 classes implementing a common interfaces (with 3 methods) because it can lead to code duplication (Length()/DescentSet()/NormalForm() would have to be implemented twice the same in 2 of the 3 algorithms) ? – Spotted Oct 14 '16 at 14:41
  • That is correct. – Johannes Hahn Oct 17 '16 at 7:08
  • I've posted a code review question about solving this with single method interfaces as well as posted an answer showing a strategy pattern solution – candied_orange Oct 19 '16 at 2:01
4

I'd use the strategy pattern here.

One interface that exposes the three methods. Three concrete classes that each define a different method and the others in terms of it.

Any general purpose algorithms can either be moved to the client or the context. I don't recommend inheritance or the template pattern.

2

You didn't tag with a specific programming language, so I'll give the solution in ML, which is at the very least worth pondering, if not directly applicable to OOP.

This is quite a common situation. We are often able to define a suite of functions from a single base function. For example, if we have the "less-than" function leq: t * t -> bool, then we can define the full suite of boolean relations:

geq a b = leq b a
eq a b = (leq a b) and (geq a b)
le a b = (leq a b ) and not (eq a b)
ge a b = (geq a b) and not (eq a b)

A clean(-ish) solution is to use a parametric module (functor) that takes in a structure with the required signature and outputs an extended structure. Using the above example, we can define the following parametric module:

functor MakeRelationalAlgebra(Ord: ORD) = 
struct
    geq a b = Ord.leq b a
    eq a b = (Ord.leq a b) and (geq a b)
    le a b = (Ord.leq a b ) and not (eq a b)
    ge a b = (geq a b) and not (eq a b)
end

Again, you didn't mention which language you're using, only that it seems to be an OOP language, so I'm not sure how this might translate. But I think it's conceptually interesting.

2

Those methods are interdependent. I really only need any one of them to define the other two.

That doesn't seem accurate. Specifically:

  • Length can be derived from the set or the normal form
  • The set can be derived from the normal form
  • The normal form cannot be derived from anything else (if it's anything like it sounds)

Interdependence implies a cycle, but there is no cycle here, the relationships form a tree. And that's crucial, because the normal form is at the root of this tree, so you cannot do without it. That makes it a clear choice for your abstract method.

If the normal form is not necessary for all use cases, then probably you have a smelly design, and you need to change your abstractions. A poor alternative could be to expose on the interface all 3 methods that you need, and in implementations that don't want to keep the more expensive set (takes more memory than length) or the even more expensive normal form (probably takes more memory than the set), you could throw an UnsupportedOperationException. But I don't recommend this. Unused interface methods suggest a smelly design.

1
  • Specifically it's about Coxeter groups and in this case, the three functions really are interdependent. The descent set is actually defined in terms of the length function as $D_L(w) := \{ s\in S | l(sw)<l(w)\}$. The normalform can be derived from the descent set be iteratively picking the smallest element of $D_L(w)$ (resulting in the lexicographical normal form). – Johannes Hahn Oct 17 '16 at 7:04
1

I'd use a combination of the delegation with functional interfaces (for composability) and factory methods (to avoid bad composition).

@FunctionalInterface
public interface Length {
    int length();
}

@FunctionalInterface
public interface DescentSet {
    Set<Integer> descentSet();
}

@FunctionalInterface
public interface NormalForm {
    int[] normalForm();
}

public final class Algorithm {
    private final Length l;
    private final DescentSet d;
    private final NormalForm n;

    private Algorithm(Length l, DescentSet d, NormalForm n) {
        this.l = l;
        this.d = d;
        this.n = n;
    }

    public void compute(int inputData) {
        //TODO use l, d and n
    }

    public static Algorithm algoName1(Length l) {
        DescentSet easySet = () -> new HashSet<>(l.length());
        NormalForm easyNormal = () -> new int[l.length()];

        return new Algorithm(l, easySet, easyNormal);
    }

    public static Algorithm algoName2(DescentSet d) {
        Length easyLength = () -> d.descentSet().size();
        NormalForm easyNormal = () -> new int[d.descentSet().size()];

        return new Algorithm(easyLength, d, easyNormal);
    }

    public static Algorithm algoName3(NormalForm n) {
        Length easyLength = () -> n.normalForm().length;
        DescentSet easySet = () -> new HashSet<>(n.normalForm().length);

        return new Algorithm(easyLength, easySet, n);
    }
}
0

Use delegates and closures, separately or in combination.

In my mind this is the template method idea but the templating is inside the method itself. Further, a delegate is a run-time method template.

It feels like you'd want to use a factory and/or builder.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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