Rozszerzanie stosu LinkedList. Naruszenie zasady substytucji Liskowa?

Istnieje klasa LinkedList z funkcjami takimi jak add_first (), add_last (), add_after (), remove_first (), remove_last () i remove ()

Teraz istnieje stos klas, który zapewnia funkcje takie jak push (), pop (), peek () lub top (), a do implementacji tych metod rozszerza metody klasy LinkedList. Czy jest to naruszenie zasady substytucji Liskowa?

Na przykład rozważmy przypadek add_after (), aby dodać węzeł w n-tej pozycji listy połączonej. Można to zrobić w klasie podstawowej, ale nie w klasie Stack. Czy warunki są osłabiane tutaj, czy modyfikujesz metodę add_after (), aby dodać ją na górę stosu?

Ponadto, jeśli nie jest to naruszenie, czy ten zły projekt? A jak zaimplementowałbyś funkcjonalność stosu za pomocą klasy LinkedList?

— jxvmiranda
źródło

Pytanie Jaka byłaby wada zdefiniowania klasy jako podklasy samej listy? pyta o nieco inny problem, ale większość odpowiedzi dotyczy również tutaj: lepiej jest utworzyć stos z listą jako członek prywatny, niż dziedziczyć z listy.

— amon

Tak, jest to zły projekt, ponieważ uniemożliwi zmianę wewnętrznej reprezentacji stosu na coś innego niż lista połączona (np. Tablica). Ujawniasz także operacje, których stosy zwykle nie obsługują. Użyj kompozycji zamiast dziedziczenia.

— Lee,

Czy chcesz przedłużyć LinkedList? Być może zechcesz posłuchać rady pewnego Joshua Blocha (który odegrał znaczącą rolę w projektowaniu frameworku kolekcji Java), gdy powiedział: „Wolę kompozycję niż dziedziczenie” - Może masz LinkedListwewnątrz swojej klasy stosu, ale tak naprawdę go nie rozszerzasz?

— corsiKa

Powiedziałbym, że nie może spełnić zasady podstawienia Liskowa, ponieważ „stos jest rodzajem listy połączonej” nie jest prawdziwym stwierdzeniem. „Stack” to tak naprawdę interfejs (mam na myśli koncepcyjnie, a nie konstrukcję Java). Stos można zaimplementować za pomocą połączonej listy. Jak inni powiedzieli, użyłbyś prywatnego członka danych typu, LinkedListktóry wykonuje ciężkie podnoszenie się za kulisy (kompozycja). W ten sposób użytkownicy Twojego kodu nie mogą przypadkowo użyć stosu, w którym potrzebowali listy lub odwrotnie.

— Jasmijn

Wydaje się, że to, co byłoby rozsądniejsze, byłoby odwrotnie. Gdybym to robił, prawdopodobnie miałbym połączoną klasę list implementującą interfejs „stosu”, ponieważ jest w pełni zdolny do tego. W przeciwnym razie jest to niewłaściwy sposób, ponieważ stos jest koncepcją, lista połączona jest implementacją, która może działać między innymi jako stos.

— Rzeczywistość

Odpowiedzi:

Teraz istnieje stos klas, który zapewnia funkcje takie jak push (), pop (), peek () lub top (), a do implementacji tych metod rozszerza metody klasy LinkedList. Czy jest to naruszenie zasady substytucji Liskowa?

Nie. Można dodawać metody w podtypie.

Na przykład rozważmy przypadek add_after (), aby dodać węzeł w n-tej pozycji listy połączonej. Można to zrobić w klasie podstawowej, ale nie w klasie Stack.

Jest to naruszenie LSP. LSP mówi, że instancje podtypu muszą być zastępowalne dla instancji nadtypu bez zmiany pożądanych właściwości programu. Jeśli podtyp usunie metodę, wówczas dowolny kod wywołujący tę metodę ulegnie awarii (lub otrzyma NoMethodErrorwyjątek lub coś wzdłuż tych linii). Oczywiście „brak awarii” jest pożądaną właściwością.

Czy warunki są osłabiane tutaj, czy modyfikujesz metodę add_after (), aby dodać ją na górę stosu?

Modyfikacja add_after()metody w ten sposób stanowi naruszenie Reguły historii (najważniejsza z zasad!), A tym samym nie pomaga naprawić naruszenia LSP.

A jak zaimplementowałbyś funkcjonalność stosu za pomocą klasy LinkedList?

Używając kompozycji.

UWAGA: Wszystko, co napisałem powyżej, dotyczy tylko języków, które mylą podtytuły i podklasy! LSP dotyczy podtypów , a nie podklas. W języku, którego nie należy mylić dwóch, byłoby to całkowicie dopuszczalne, aby Stackpodklasy LinkedList, tak długo, jak nie zrobić to podtyp z LinkedList.

— Jörg W Mittag
źródło

Co to jest reguła historyczna? Nie udało mi się go znaleźć w Internecie.

— Zapadlo,

Manipulując obiektem podtypu i obserwując go metodami nadtypu, musi być niemożliwe obserwowanie historii, której nie można było zaobserwować również z obiektem nadtypu. Ta reguła powoduje, że LSP ma zastosowanie do języków niefunkcjonalnych. Wszystkie inne rzeczy były już znane na długo przedtem. Reguły poprzedzające i uzupełniające stanowią przeformułowanie reguł ko- i kontrawariancji dla typów funkcji. Reguła historii sprawia, że wszystko to dotyczy zmiennych danych. Bez niego LSP byłby użyteczny tylko dla języków czysto funkcjonalnych.

— Jörg W Mittag,

Myślę, że wyjaśnienie w artykule na Wikipedii jest dość dobre: wikipedia.org/wiki/Liskov_substitution_principle Ale jak zawsze powinieneś naprawdę przeczytać oryginalne źródło.

— Jörg W Mittag,

@ JörgWMittag: Chociaż uważam, że rozsądne jest, aby typy zawierały w umowach gwarancje dotyczące tego, co „historia” będzie obserwować, ale nie będzie konieczne, nie uważam, że konieczne byłoby, aby każdy nadtyp był w stanie wygenerować każdą sekwencję obserwacji może to być możliwe na obiekcie podtypu - po prostu, że nadtyp dokumentuje możliwość, że konsumenci nadtypu mogą zaobserwować takie sekwencje.

— supercat

Ponieważ Jörg W Mittag zajął się już wszystkimi kwestiami, rozwinąłem nieco tę część:

Czy warunki są osłabiane tutaj, czy modyfikujesz metodę add_after (), aby dodać ją na górę stosu?

Zasadniczo, gdy pojawia się pytanie, czy jakaś hierarchia narusza LSP, zależy to od tego, jaki kontrakt stanowisz. Więc jaka umowa add_afterma? Jeśli to brzmi, jakkolwiek szalone, jak „Dodaj węzeł na n-tej pozycji lub na górze”, to nic ci nie jest, warunek końcowy jest spełniony, LSP nie jest naruszany. W przeciwnym razie jest to naruszenie LSP.

— Zapadło
źródło