Warum stürzt Haskells "Kopf" auf einer leeren Liste ab (oder warum * gibt * er keine leere Liste zurück)? (Sprachphilosophie)

Hinweis für andere potenzielle Mitwirkende: Bitte zögern Sie nicht, abstrakte oder mathematische Notationen zu verwenden, um Ihren Standpunkt zu verdeutlichen. Wenn ich Ihre Antwort unklar finde, werde ich um Aufklärung bitten, aber ansonsten können Sie sich auf bequeme Weise ausdrücken.

Um es klar auszudrücken: Ich suche weder einen "Tresor" head, noch ist die Wahl von headbesonders außergewöhnlich aussagekräftig. Das Fleisch der Frage folgt der Diskussion von headund head', die dazu dienen, Kontext zu liefern.

Ich habe mich jetzt seit ein paar Monaten mit Haskell abgehackt (bis zu dem Punkt, dass es meine Hauptsprache geworden ist), aber ich bin zugegebenermaßen nicht gut über einige der fortgeschritteneren Konzepte oder die Details der Sprachphilosophie informiert (obwohl) Ich bin mehr als bereit zu lernen. Meine Frage ist dann weniger eine technische (es sei denn, es ist und ich merke es einfach nicht), sondern eine der Philosophie.

Für dieses Beispiel spreche ich head.

Wie ich mir vorstellen kann, werden Sie wissen,

Prelude> head []    
*** Exception: Prelude.head: empty list

Dies folgt aus head :: [a] -> a. Meinetwegen. Offensichtlich kann man kein Element von (handgewellt) keinem Typ zurückgeben. Gleichzeitig ist es einfach (wenn nicht trivial) zu definieren

head' :: [a] -> Maybe a
head' []     = Nothing
head' (x:xs) = Just x

Ich habe hier im Kommentarbereich bestimmter Aussagen eine kleine Diskussion darüber gesehen . Bemerkenswert ist ein Alex Stangl

"Es gibt gute Gründe, nicht alles" sicher "zu machen und Ausnahmen zu werfen, wenn die Voraussetzungen verletzt werden."

Ich stelle diese Behauptung nicht unbedingt in Frage, bin aber gespannt, was diese "guten Gründe" sind.

Zusätzlich sagt ein Paul Johnson:

'Zum Beispiel könnten Sie "safeHead :: [a] -> Vielleicht a" definieren, aber anstatt entweder eine leere Liste zu behandeln oder zu beweisen, dass dies nicht möglich ist, müssen Sie "nichts" behandeln oder beweisen, dass dies nicht möglich ist . '

Der Ton, den ich aus diesem Kommentar lese, deutet darauf hin, dass dies eine bemerkenswerte Zunahme von Schwierigkeit / Komplexität / etwas ist, aber ich bin nicht sicher, ob ich verstehe, was er da rausbringt.

Ein Steven Pruzina sagt (2011 nicht weniger),

"Es gibt einen tieferen Grund, warum z. B. 'head' nicht absturzsicher sein kann. Um polymorph zu sein und dennoch eine leere Liste zu verarbeiten, muss 'head' immer eine Variable des Typs zurückgeben, die in einer bestimmten leeren Liste nicht vorhanden ist Delphic, wenn Haskell das könnte ... ".

Geht der Polymorphismus verloren, wenn die Behandlung leerer Listen zugelassen wird? Wenn ja, wie und warum? Gibt es bestimmte Fälle, die dies offensichtlich machen würden? Dieser Abschnitt wurde von @Russell O'Connor ausführlich beantwortet. Alle weiteren Gedanken sind natürlich willkommen.

Ich werde dies bearbeiten, wie es die Klarheit und der Vorschlag vorschreiben. Alle Gedanken, Papiere usw., die Sie zur Verfügung stellen können, werden am meisten geschätzt.

Geht der Polymorphismus verloren, wenn die Behandlung leerer Listen zugelassen wird? Wenn ja, wie und warum? Gibt es bestimmte Fälle, die dies offensichtlich machen würden?

Der freie Satz für headbesagt, dass

f . head = head . $map f

Die Anwendung dieses Theorems auf []impliziert dies

f (head []) = head (map f []) = head []

Dieser Satz muss für jeden gelten f, also muss er insbesondere für const Trueund gelten const False. Dies impliziert

True = const True (head []) = head [] = const False (head []) = False

Wenn headalso richtig polymorph ist und head []ein Gesamtwert Truewäre , dann wäre gleich False.

PS. Ich habe einige andere Kommentare zum Hintergrund Ihrer Frage, die besagen, dass Sie, wenn Sie die Voraussetzung haben, dass Ihre Liste nicht leer ist, diese erzwingen sollten, indem Sie einen nicht leeren Listentyp in Ihrer Funktionssignatur verwenden, anstatt eine Liste zu verwenden.

Warum verwendet jemand head :: [a] -> aanstelle des Mustervergleichs? Einer der Gründe ist, dass Sie wissen, dass das Argument nicht leer sein kann und den Code nicht schreiben möchten, um den Fall zu behandeln, in dem das Argument leer ist.

Natürlich ist Ihr head'Typ [a] -> Maybe ain der Standardbibliothek als definiert Data.Maybe.listToMaybe. Wenn Sie jedoch eine Verwendung von headdurch ersetzen listToMaybe, müssen Sie den Code schreiben, um den leeren Fall zu behandeln, wodurch dieser Verwendungszweck zunichte gemacht wird head.

Ich sage nicht, dass das Verwenden headein guter Stil ist. Es verbirgt die Tatsache, dass es zu einer Ausnahme führen kann, und in diesem Sinne ist es nicht gut. Aber es ist manchmal bequem. Der Punkt ist, dass headeinige Zwecke erfüllt werden, denen nicht gedient werden kann listToMaybe.

Das letzte Zitat in der Frage (über Polymorphismus) bedeutet einfach, dass es unmöglich ist, eine Funktion vom Typ zu definieren, [a] -> adie einen Wert in der leeren Liste zurückgibt (wie Russell O'Connor in seiner Antwort erklärte ).

Es ist nur natürlich zu erwarten, dass Folgendes zutrifft: xs === head xs : tail xs- Eine Liste ist identisch mit ihrem ersten Element, gefolgt vom Rest. Scheint logisch, oder?

Zählen wir nun die Anzahl der Nachteile (Anwendungen von :), wobei die tatsächlichen Elemente außer Acht gelassen werden, wenn das angebliche 'Gesetz' angewendet wird auf []: []sollte identisch sein mit foo : bar, aber das erstere hat 0 Nachteile, während das letztere (mindestens) einen hat. Oh, hier stimmt etwas nicht!

Das Typensystem von Haskell ist trotz all seiner Stärken nicht in der Lage, die Tatsache auszudrücken, dass Sie nur headeine nicht leere Liste aufrufen sollten (und dass das 'Gesetz' nur für nicht leere Listen gilt). Durch headdie Verwendung wird die Beweislast auf den Programmierer verlagert, der sicherstellen sollte, dass sie nicht für leere Listen verwendet wird. Ich glaube, dass abhängig getippte Sprachen wie Agda hier helfen können.

Zum Schluss noch eine etwas operativ-philosophischere Beschreibung: Wie soll head ([] :: [a]) :: aumgesetzt werden? Es aist unmöglich, einen Wert des Typs aus der Luft zu zaubern (denken Sie an unbewohnte Typen wie data Falsum), und es würde bedeuten, irgendetwas zu beweisen (über den Curry-Howard-Isomorphismus).

Es gibt verschiedene Möglichkeiten, darüber nachzudenken. Also werde ich sowohl dafür als auch dagegen argumentieren head':

Gegen head':

Es ist nicht erforderlich head': Da Listen ein konkreter Datentyp sind, können head'Sie alles, was Sie damit tun können, durch Mustervergleich tun.

Außerdem head'tauschen Sie nur einen Funktor gegen einen anderen aus. Irgendwann möchten Sie sich den Messingnägeln zuwenden und das zugrunde liegende Listenelement bearbeiten.

Zur Verteidigung von head':

Aber Pattern Matching verdeckt, was los ist. In Haskell sind wir an der Berechnung von Funktionen interessiert, was besser erreicht werden kann, indem sie mit Kompositionen und Kombinatoren punktfrei geschrieben werden.

Wenn Sie an die []und MaybeFunktoren denken , head'können Sie sich außerdem zwischen ihnen hin und her bewegen (insbesondere die ApplicativeInstanz von []mit pure = replicate.)

Wenn in Ihrem Anwendungsfall eine leere Liste überhaupt keinen Sinn ergibt , können Sie sich jederzeit für die Verwendung entscheiden NonEmpty, wenn neHeaddie Verwendung sicher ist. Wenn Sie es aus diesem Blickwinkel sehen, ist nicht die headFunktion unsicher, sondern die gesamte Listendatenstruktur (auch für diesen Anwendungsfall).

Ich denke, das ist eine Frage der Einfachheit und Schönheit. Das liegt natürlich im Auge des Betrachters.

Wenn Sie aus einem Lisp-Hintergrund stammen, wissen Sie möglicherweise, dass Listen aus Nachteile bestehen, wobei jede Zelle ein Datenelement und einen Zeiger auf die nächste Zelle hat. Die leere Liste ist keine Liste an sich, sondern ein spezielles Symbol. Und Haskell geht mit dieser Argumentation.

Meiner Ansicht nach ist es sowohl sauberer, einfacher zu überlegen als auch traditioneller, wenn leere Liste und Liste zwei verschiedene Dinge sind.

... Ich kann hinzufügen - wenn Sie sich Sorgen machen, dass der Kopf unsicher ist - verwenden Sie ihn nicht, sondern verwenden Sie stattdessen den Mustervergleich:

sum     [] = 0
sum (x:xs) = x + sum xs