java - 无法理解Java在方法上调用方法

Question

所以我正在阅读有关 Java 的内容，并且遇到了一个示例。我不知道它是如何工作的。下面您将在 ConsLoRunner 类中看到 sortByTime() 方法。我的问题是它如何能够输出一些东西，它不会一遍又一遍地递归该方法，并且永远不会到达 insertByTime(this.first) 方法吗？

旁注:该示例是马拉松运行者，并根据他们的时间对他们进行排序(从最快到最慢)。

class Runner {
    String name;
    int age;
    int bib;
    boolean isMale;
    int pos;
    int time;

    Runner(String name, int age, int bib, boolean isMale, int pos, int time) {
        this.name = name;
        this.age = age;
        this.bib = bib;
        this.isMale = isMale;
        this.pos = pos;
        this.time = time;
    }

    public boolean finishesBefore(Runner r) {
        return this.time < r.time;
    }
}

interface ILoRunner {
    ILoRunner sortByTime();
    ILoRunner insertByTime(Runner r);
}

class MtLoRunner implements ILoRunner {

    public ILoRunner sortByTime() {
        return this;
    }

    public ILoRunner insertByTime(Runner r) {
        return new ConsLoRunner(r, this);
    }

}

class ConsLoRunner implements ILoRunner {
    Runner first;
    ILoRunner rest;

    ConsLoRunner(Runner first, ILoRunner rest) {
        this.first = first;
        this.rest = rest;
    }
    /*******HOW DOES IT DO THIS?????**********/
    public ILoRunner sortByTime() {
        return this.rest.sortByTime().insertByTime(this.first);
    }

    public ILoRunner insertByTime(Runner r) {
        if (this.first.finishesBefore(r)) {
            return new ConsLoRunner(this.first, this.rest.insertByTime(r));
        }
        else {
            return new ConsLoRunner(r, this);
        }
    }
}

class ExamplesRunners {
    MtLoRunner empty = new MtLoRunner();
    Runner tim = new Runner ("Tim", 1, 2, true, 5, 6);
    Runner bob = new Runner ("Bob", 5, 6, true, 9, 50);
    Runner jim = new Runner ("Jim", 5, 6, true, 10, 40);

    ILoRunner list1 = new ConsLoRunner(this.tim, new ConsLoRunner(this.bob, new ConsLoRunner(this.jim, this.empty)));

    boolean testSort(Tester t) {
        return t.checkExpect(this.list1.sortByTime(), new ConsLoRunner(this.tim, new ConsLoRunner(this.jim, new ConsLoRunner(this.bob, this.empty))));
    }
}

Answer 1

I have no idea how it works.

我会尝试回答这个问题。

您正在查看 List Data Structure 的(相当令人困惑的)Java 版本，通常出现在 LISP 等语言中.

在我们的例子中，“列表”可以递归地定义。它是:

• 空列表，用 () 或 nil 表示，或
• 第一个元素后跟另一个列表(其余元素):(first，rest)

如您所见，Java 类与这些概念有清晰的映射:

ILoRunner    -> An abstract List, the root type
MtLoRunner   -> An empty list: () or nil
ConsLoRunner -> A non-empty list: (first, rest)

线索就在名称 ConsLoRunner 的开头。在 LISP 中，cons 是一个“构造函数”，它创建一个包含另外两个对象的对象。 cons 通常用于创建列表。但它也可用于创建非列表结构。抱歉，我离题了。

将示例重写为列表表示形式，运行者列表 list1 大致如下所示(为简单起见，省略其他字段):

(Tim  <-- first: Tim, rest: (Bob ...)
    (Bob <-- first: Bob, rest: (Jim ())
        (Jim ()))) <-- first: Jim, rest: () // rest of the list is empty, no more elements.

正是 ExamplesRunners 正在做的事情。

现在是令人困惑的部分。该代码按运行者的完成时间对运行者进行排序。这个想法非常简单，要对这样的列表进行排序，我们

1. 首先对列表的其余部分进行排序
2. 然后将第一个元素插入到第一步中的排序列表中

这就是ConsLoRunner.sortByTime正在做的事情。但请注意，它返回一个新的、已排序的列表。 所以原始列表永远不会改变。

将元素 x 插入排序列表也很简单:

1. 将 x 与列表的第一个元素进行比较
2. 如果 x 较小，则在整个列表之前插入 x
3. 否则，将 x 插入列表的其余部分

请记住，插入是通过创建一个新的 cons 对象以及适当的元素顺序来完成的。同样，原始列表被保留。

IMO，如果代码是针对实际列表接口(interface)编写的，而不是与新列表的内部表示和构造混合在一起，那么代码会更容易阅读。

// The list interface
interface List<T extends Comparable<T>> {

    boolean isEmpty();

    T first();

    List<T> rest();
}

// Instances of this class represents an empty list: ()
class Empty<T extends Comparable<T>> implements List<T> {

    @Override
    public boolean isEmpty() {
        return true;
    }

    @Override
    public T first() {
        return null;
    }

    @Override
    public List<T> rest() {
        return null;
    }

    @Override
    public String toString() {
        return "()";
    }
}

// A non-empty list, composed of the first element and the rest.
class Cons<T extends Comparable<T>> implements List<T> {

    private final T first;
    private final List<T> rest;

    public Cons(T first, List<T> rest) {
        this.first = first;
        this.rest = rest;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public T first() {
        return first;
    }

    @Override
    public List<T> rest() {
        return rest;
    }

    @Override
    public String toString() {
        return "(" + first +", " + rest + ")";
    }
}

public class Lisp {

    // Creates and returns a sorted list from the given list
    // The original list is never changed.
    public static <T extends Comparable<T>> List<T> sort(List<T> list) {
        if (list.isEmpty()) {
            // Empty lists are already sorted.
            return list;
        } else {
            // We first sort the rest of the list
            List<T> sortedRest = sort(list.rest());
            // Then insert the first element into the sorted list
            return insert(list.first(), sortedRest);
        }
    }

    // Creates and returns a sorted list with x inserted into a proper position in the already sorted list
    private static <T extends Comparable<T>> List<T> insert(T x, List<T> list) {
        if (list.isEmpty() || x.compareTo(list.first()) < 0) {
            return new Cons<>(x, list);
        } else {
            // Recursive call return a sorted list containing x
            return new Cons<>(list.first(),
                              insert(x, list.rest()));
        }
    }

    public static void main(String [] args) {
        List<Integer> alist = new Cons<>(7, new Cons<>(1, new Cons<>(4, new Empty<>())));
        System.out.println("Sorted:   " + sort(alist));
        System.out.println("Original: " + alist);
    }
}

输出

Sorted:   (1, (4, (7, ())))
Original: (7, (1, (4, ())))