Lisp Связанный список Emulation Java

Question

Для моего задания мы должны создать эмуляцию связанного списка LISP на Java. Существует два типа List, EmptyList и NonEmptyList. EmptyList является в основном тривиальным и служит только для завершения связанного списка. Способ, которым он должен работать, состоит в том, что каждый Список имеет голову и хвост. Голова - это Объект, а Хвост - следующий Связанный Список. У меня есть Linked интерфейс List следующим образом:

public interface LispList { 
    EmptyList NIL = new EmptyList(); 

    boolean empty(); 
    Object head(); 
    LispList tail(); 
    LispList cons(Object inputHead); 
} 

А вот NonEmptyList класс:

public class NonEmptyList implements LispList{ 
    Object head; 
    LispList tail; 

    public NonEmptyList(Object inputHead) { 
     this.head = inputHead; 
     this.tail = new NonEmptyList(head); 
    } 

    public boolean empty() { 
     return false; 
    } 

    public Object head() { 
     return head; 
    } 

    public LispList tail() { 
     return tail; 
    } 

    public String toString() { 
     return head() + " " + tail().toString(); 
    } 

    public NonEmptyList cons(Object inputHead) { 
     NonEmptyList a = new NonEmptyList(inputHead); 
     return a; 
    } 

    public class NIL{ 
     EmptyList NIL; 
    } 
} 

EmptyList:

public class EmptyList implements LispList { 

    public EmptyList() { 

    } 

    public boolean empty() { 
     return true; 
    } 

    public Object head() { 
     throw new UnsupportedOperationException("EmptyList"); 
    } 

    public LispList tail() { 
     throw new UnsupportedOperationException("EmptyList"); 
    } 

    public String toString() { 
     return ""; 
    } 

    public class NIL{ 
     EmptyList NIL; 
    } 

    public NonEmptyList cons(Object inputHead) { 
     NonEmptyList a = new NonEmptyList(inputHead); 
     return a; 
    } 
} 

А вот мой тестер:

public class LispListTest { 

    public static void main(String[] args) { 
     LispList list = LispList.NIL.cons("C").cons("B").cons("A"); 

     System.out.println(list.tail()); 

     System.out.println(list.toString()); 
    } 
} 

Проблема у меня есть i s в конструкторе NonEmptyList. То, как я это делаю, в настоящее время дает мне исключение переполнения стека. Я пробовал несколько разных вещей, и никто из них не работает так, как мне нужно. Я не уверен, как сделать конструктор таким образом, чтобы хвост указывал на следующий список.

Это моя первая попытка связанного списка, поэтому я могу сделать довольно простую ошибку.

Answer 1

Short anwser

Во-первых, EmptyList класс должен быть синглтон. Не уверен, как достичь этого Java, но вы не должны открывать конструктор для всех.

Затем конструктор NonEmptyList должен принимать два аргумента:

1. Объект для головы.
2. Хвост, экземпляр LispList. Лучше, если вы перегрузите конструктор с этим аргументом, по умолчанию на EmptyList (singleton).

В настоящее время, в конструкторе NonEmptyList вы рекурсивно называем его при назначении tail: таким образом сконструированный бесконечный список с повторенного элемента: (а) это не то, что вы хотите, и (б) без лени это приведет к переполнению стека.

И, наконец, cons является конструктором для непустого списка, поэтому нет необходимости в методе cons.

руководство в Лиспе список

Большинство Lisp Диалекты построить список на вершине пары. Существует некоторая критика в отношении того, как Lisps это делает: это вводит понятия правильных и неправильных списков, и трудно определить общее сравнение по спискам. Тем не менее, это простой и эффективный способ сделать это.

пара строится с помощью CONS функции (я буду использовать Common Lisp, CL, для демонстрации):

(cons 12 45) => (12 . 45) 

Обратите внимание на точку в печатном виде пары.Части пары могут быть извлечены с помощью функции CAR и CDR:

(car (cons 12 45)) => 12 
(cdr (cons 12 45)) => 45 

Пары могут быть объединены с другими парами:

(cons (cons (cons 1 2) 3) (cons 4 5)) 
=> (((1 . 2) . 3) 4 . 5) 

CL обеспечивает сочетание функций CAR и CDR для извлечения суб-пар, например, CDDAR - это ярлык для (CDR (CDR (CAR OBJ))): он берет первый элемент пары (который должен быть самой парой), затем второй элемент результата и второй элемент этого результата.

Lisps также определяют специальный объект пустой пары или ничего (но на самом деле этот объект не является парой, это как математический «пустой набор», который не является набором ...). В CL есть два синонима для него: NIL или ().

Список строится с использованием пар, упорядоченных определенным образом. Список является:

• Либо NIL, или пустой
• Или (CONS OBJ TAIL), где OBJ является любой объект и TAIL список.

Чтобы различать операции по парам и их комбинаций из операций по спискам, Common Lisp предоставляет синонимичные функции:

• FIRST извлекает первый элемент из списка (он же голова), синоним CAR.
• REST возвращает хвост списка, синоним для (CAR (CDR LIST)) или (CADR LIST).

Итак, вот примеры списков:

• NIL является пустым списком
• (CONS 1 NIL) (печатные (1)) список из одного элемента; FIRST вернется 1 и REST вернет пустой список NIL.
• (CONS 1 (CONS 2 NIL)) (печатный (1 2)) - это список из двух элементов; FIRST вернется 1 и REST вернет хвост (2).
• Как правило, список номеров от 1 до N будет (CONS 1 (CONS 2 (CONS 3 ... (CONS N NIL) ..))).

Answer 2

Вот правильный и проверенный ответ:

LispList интерфейс:

public interface LispList 
{ 
LispList NIL = new EmptyList(); 
boolean isEmpty(); 
Object head(); 
LispList tail(); 
LispList cons(Object head); 
} 

EmptyList класс

public class EmptyList implements LispList { 
public String toString() { 
    return ""; 
} 

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

@Override 
public Object head() { 
    throw new UnsupportedOperationException(); 
} 

@Override 
public LispList tail() { 
    throw new UnsupportedOperationException(); 
} 

@Override 
public LispList cons(Object head) { 
    return new NonEmptyList(head, new EmptyList()); 
} 

}

NonEmptyList класс

public class NonEmptyList implements LispList { 
private LispList tail; 
private Object head; 

public NonEmptyList(Object head, LispList tail) { 
    this.head = head; 
    this.tail = tail; 
} 

public String toString() { 
    return head() + " " + tail().toString(); 
} 

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

@Override 
public Object head() { 
    return head; 
} 

@Override 
public LispList tail() { 
    return tail; 
} 

@Override 
public LispList cons(Object head) { 
    return new NonEmptyList(head, new NonEmptyList(head(), tail)); 
} 

}

И проверить главный класс:

public class LispListTester 
{ 
public static void main(String[] args) 
{ 
    LispList list1 = new EmptyList(); 
    System.out.println("[" + list1 + "]"); 
    System.out.println("Expected: []"); 

    LispList list2 = new NonEmptyList("A", new EmptyList()); 
    System.out.println(list2); 
    System.out.println("Expected: A"); 

    LispList list3 = new NonEmptyList("A", new NonEmptyList("B", 
      new NonEmptyList("C", new EmptyList()))); 
    System.out.println(list3); 
    System.out.println("Expected: A B C"); 

    LispList list4 = LispList.NIL.cons("E").cons("D").cons("C").cons("B").cons("A"); 
    System.out.println(list4); 
    System.out.println("Expected: A B C D E"); 
    } 
}