2

这是一个对 Haskell 和 C++ 模板元编程做过多的人提出的一个复杂但有趣的问题。请多多包涵

我正在编写一些通用 Java 代码来检查函数的某些代数属性，并且我在为其中一些提出适当的类型时遇到了一些困难。

作为一个有效的例子，这是一个检查函数是否可交换的函数：

<E, R>
boolean checkCommutative( Binary<E,E,R> f
                        , Binary<R,R,Boolean> eq
                        , E a, E b)
{
    return eq.ap(f.ap(a,b), f.ap(b, a));
}

这个函数应该是这样的：“一个f接受两个E并产生一个的二元函数R是可交换的（相等性由eq比较两个的函数定义R），如果对于任何类型的a和，应用到等于应用到。”bEf(a,b)f(b,a)

C.plus(Integer,Integer)然后，我可以通过执行以下操作来测试给定函数是否可交换：

class Plus implements Binary<Integer, Integer, Integer> {
    Integer ap(Integer a, Integer b) { return C.plus(a,b); }
}

class Eq implements Binary<Integer, Integer, Boolean> {
    Boolean ap(Integer a, Integer b) { return a.equals(b); }
}

checkCommutative(new Plus(), new Eq(), rand(), rand());

一切都很好。

现在我想实现一些更复杂的东西。假设我有一个Group<E>带有 plus 方法的通用接口：

interface Group<E> {
    E plus(E,E);
}

假设我有两个实现：TheIntegers和TheRationals：

class TheIntegers  implements Group<Integer> { ... }
class TheRationals implements Group<Fraction> { ... }

现在，我希望能够捕捉到F从整数到有理数的通用函数与g类似Group.plus. 作为第一个剪辑，我想写这样的东西：

<E, R>
booleanCheckCommutesWith( Unary<E,R> f
                        , ?? g
                        , Binary<R,R,Boolean> eq
                        , E a, E b)
{
    return eq.ap(f.ap(g.ap(a,b)), g.ap(f.ap(a), f.ap(b));
}

class F implements Unary<TheIntegers, TheRationals> {
    Fraction ap (Integer x) { ... }
}

checkCommutesWith(new F(), new Plus(), new Eq(), rand(), rand());

这里的问题是类型应该是什么g？问题在于它g适用于两种不同的类型：E和R. 在具体示例中，我们希望g同时表示Group<Integer>.plus(Integer,Integer)和Group<Fraction>.plus(Fraction,Fraction)。

现在，checkCommutesWith上面的实现不可能工作，因为两个调用之间的唯一区别g.ap是泛型类型，它被删除了。因此，我将通过将域和范围添加为对象来对其进行一些修改：

boolean checkCommutesWith( Unary<DE,RE> f
                        , ?? g
                        , Binary<RE,RE,Boolean> eq
                        , S domain, S range
                        , E x, E y)
{
    return eq.ap( f.ap(g.ap(domain, x, y)),
                , g.ap(range, f.ap(x), f.ap(y))
                );
}

class Plus implements ??
{
    <E, G extends Group<E>>
    E ap (G gp, E x, E y) { return gp.plus(x,y); }
}

那么界面（??）应该是什么样子的呢？如果这是 C++，我会写相当于

interface ?? <T> {
    <E, S extends T<E>>
    E ap(S, E, E);
}

但 AFAICT Java 没有模板模板参数的等效项。这就是我卡住的地方。

请注意，我不想将 Group 作为 签名的一部分checkCommutesWith，因为我也希望能够将此代码与其他结构一起使用。我认为应该可以有一个通用的定义（对于“应该”的一些定义:)）。

更新/澄清这里问题的症结在于集合之间映射的定义属性是它们与 eq() 通勤。群同态的定义属性是它们与 plus() 交换。环同态的定义属性是它们与 times() 通勤。我正在尝试定义一个通用的 commutesWith 函数来捕捉这个想法，并且我正在寻找正确的抽象来封装 eq、plus 和 times（以及其他结构）。

4

3 回答 3

1

作为第一个近似值，请参见代码

https://github.com/rfqu/CodeSamples/blob/master/src/so/SoFun.java

至少它编译时没有警告和错误:)

于 2012-10-26T18:19:19.223 回答
1

我不确定它是否足以满足您的目的，但您可能会检查JScience库中定义的类型结构。特别是， 中指定的接口org.jscience.mathematics.structure可能代表一个有用的起点。

于 2012-10-26T03:42:22.907 回答
1

我担心如果没有未经检查的强制转换，Java 类型系统不够强大，无法做到这一点。但是，它们的影响可以降到最低。

考虑用范畴理论术语来定义它。这足以表达一切，群同态是范畴对象之间态射的具体例子。

关于以下代码的注释： 1. 我把你的关系checkCommutesWith变成了一个morphismTester关系。2.eq现在是一个属性CategoryObject而不仅仅是一个参数。3. castToConcreteObjectofCategory用于进行未经检查的演员表。GroupsCategory在我们的示例中，如果使用 for only ，这是安全的GroupObject，并且没有不同的实现CategoryObject<GroupsCategory, E>。

public interface Category<C extends Category<C>>
{
    <E> CategoryObject<C, E>
    castToConcreteObject(CategoryObject<C, E> abstractObject);

    < DOM_E, COD_E
    , DOM_CO extends CategoryObject<C, DOM_E>
    , COD_CO extends CategoryObject<C, COD_E>
    >
    Binary<DOM_E, DOM_E, Boolean>
    morphismTester ( final Unary<DOM_E, COD_E> f
                   , DOM_CO domainObject
                   , COD_CO codomainObject
                   );
}


public interface CategoryObject<C extends Category<C>, E>
{
    Binary<E,E,Boolean> eq();
}


public interface GroupObject<E>
         extends CategoryObject<GroupsCategory, E>
{
    E plus(E a, E b);

    E invert(E a);

    @Override
    Binary<E,E,Boolean> eq();
}

public class GroupsCategory
  implements Category<GroupsCategory>
{
    @Override
    public <E>
    GroupObject<E>
    castToConcreteObject(CategoryObject<GroupsCategory, E> abstractObject)
    {
        return (GroupObject<E>) abstractObject;
    }

    @Override
    public < DOM_E, COD_E
           , DOM_CO extends CategoryObject<GroupsCategory, DOM_E>
           , COD_CO extends CategoryObject<GroupsCategory, COD_E>
           >
    Binary<DOM_E, DOM_E, Boolean>
    morphismTester ( final Unary<DOM_E, COD_E> f
                   , final DOM_CO abstractDomainObject
                   , final COD_CO abstractCodomainObject
                   )
    {
        final GroupObject<DOM_E> domainGroup
            = castToConcreteObject(abstractDomainObject);
        final GroupObject<COD_E> codomainGroup
            = castToConcreteObject(abstractCodomainObject);

        return new Binary<DOM_E, DOM_E, Boolean>()
        {
            @Override
            public Boolean ap(DOM_E a, DOM_E b)
            {
                return codomainGroup.eq().ap
                    (
                        codomainGroup.plus(f.ap(a), f.ap(b)),
                        f.ap(domainGroup.plus(a, b))
                    );
            }
        };
    }
}

可能，要检查更多属性，您需要为每个属性定义一个类别。然后可能存在扩展其他几个类别的类别，这正是描述它们的对象的属性和它们之间的态射的内容。

于 2012-10-26T13:42:11.367 回答