In dieser Aufgabe sollen Sie insbesondere Rekursion einüben. Wir nutzen eine rekursive definierte Datenstruktur für Listen und schreiben ganz viele Methode für diese, die alle am besten rekursiv zu lösen sind.
Studieren Sie den zur Aufgabe gehörenden Lehrbrief und lösen Sie die Aufgaben darin. Testen Sie ihre Lösungen zunächst am besten interaktiv in der JShell.
package name.panitz.util;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Consumer;
import java.util.Comparator;
import java.util.NoSuchElementException;
public sealed interface LL<E> permits LL.Nil, LL.Cons{
static public final record Nil<E>() implements LL<E>{
@Override public String toString(){return "[]";}
}
static public final record Cons<E>(E hd,LL<E> tl) implements LL<E>{
@Override public String toString(){return show();}
}
default boolean isEmpty(){return this instanceof Nil;}
default E head(){
if (this instanceof Cons<E> c) return c.hd();
throw new NoSuchElementException("head on empty list");
}
default LL<E> tail(){
if (this instanceof Cons<E> c) return c.tl();
throw new NoSuchElementException("tail on empty list");
}
static final LL nil = new Nil<>();
static <E>LL<E> nil(){return nil;}
static <E>LL<E> cons(E hd,LL<E> tl){return new Cons<>(hd,tl);}
static <E>LL<E> of(E...es){
LL<E> r = nil();
for (int i=es.length-1;i>=0;i--) r = cons(es[i],r);
return r;
}
default String show(){
StringBuffer result = new StringBuffer("[");
boolean first = true;
for (var it = this;!it.isEmpty();it=it.tail()){
if (first) first = false;else result.append(", ");
result.append(it.head());
}
result.append("]");
return result.toString();
}
default int length(){
return 0; /*ToDo*/
}
default E last(){
return null; /*ToDo*/
}
default LL<E> append(LL<E> that){
return nil(); /*ToDo*/
}
default LL<E> drop(int i){
return nil(); /*ToDo*/
}
default LL<E> take(int i){
return nil(); /*ToDo*/
}
default LL<E> sublist(int from, int length) {
return nil(); /*ToDo*/
}
default LL<E> reverse(){
return nil(); /*ToDo*/
}
default LL<E> intersperse(E e){
return nil(); /*ToDo*/
}
default boolean isPrefixOf(LL<E> that){
return false; /*ToDo*/
}
default boolean isSuffixOf(LL<E> that){
return false; /*ToDo*/
}
default boolean isInfixOf(LL<E> that){
return false; /*ToDo*/
}
default E get(int i){
/*ToDo*/
throw new IndexOutOfBoundsException();
}
default LL<E> rotate(){
return nil(); /*ToDo*/
}
default LL<LL<E>> tails(){
return of(nil()); /*ToDo*/
}
default void forEach(Consumer<? super E> con) {
/*ToDo*/
}
default boolean containsWith(Predicate< ? super E> p) {
return false; /*ToDo*/
}
default boolean contains(E el) {
return false; /*ToDo*/
}
default LL<E> dropWhile(Predicate< ? super E> p){
return nil(); /*ToDo*/
}
default LL<E> takeWhile(Predicate< ? super E> p){
return nil(); /*ToDo*/
}
default LL<E> filter(Predicate<? super E> p){
return nil(); /*ToDo*/
}
default <R> LL<R> map(Function<? super E, ? extends R> f){
return nil(); /*ToDo*/
}
static public record Pair<A,B>(A fst,B snd){
@Override public String toString(){return "("+fst()+", "+snd()+")";}
}
default <B> LL<Pair<E,B>> zip(LL<B> that){
return nil(); /*ToDo*/
}
default Pair<LL<E>,LL<E>> span(Predicate<? super E> p){
return new Pair<>(nil(),nil()); /*ToDo*/
}
default Pair<LL<E>,LL<E>> partition(Predicate<? super E> p){
return new Pair<>(nil(),nil()); /*ToDo*/
}
default boolean isSorted(Comparator<? super E> cmp){
return false; /*ToDo*/
}
default LL<E> qsort(Comparator<? super E> cmp){
return nil(); /*ToDo*/
}
}
Subato
