Das deutsche Python-Forum

Seit 2002 Diskussionen rund um die Programmiersprache Python
https://www.python-forum.de/

Warum nimmt sum() keine strings?

https://www.python-forum.de/viewtopic.php?t=30418

Seite 2 von 3

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 11:43
von mkesper
Konsequenterweise hätte man eigentlich auch 'a' + 'b' verbieten müssen.

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 11:58
von lunar
mutetella hat geschrieben:Das Ergebnis von 1 + 2 ergibt eine andere Zahl, weil innerhalb der Möglichkeiten von 0 - 9 sich ein 1 + 2 durch die 3 darstellen lässt. Sind alle Möglichkeiten erschöpft, müssen wir auch bei Zahlen eine Konkatenation vornehmen, spätestens ab der 10.
Obwohl bereits alles gesagt ist, möchte ich darauf doch noch mal eingehen, denn die Aussage ist fundamental falsch. Konkatenation zeigt sich nicht darin, dass man plötzlich eine Stelle mehr hat (was Du wohl zu vermuten scheinst). Ich glaube, ein guter Teil Deiner Verwirrung ergibt sich daraus, dass Du nicht genau trennst zwischen der Zahl und der Darstellung der Zahl.

Die Addition ist eine Operation auf Zahlen, die Konkatenation dagegen auf der Darstellung von Zahlen. Es gilt daher "1 + 9 = 10" (Addition), aber "1 + 9 = 19" (Konkatenation). Im Hexadezimalsystem ergibt "0x9 + 0x1" "0xA" (Addition), dieselbe Zahl wie 10, aber eine andere Darstellung. "0x9 + 0x1" (Konkatenation) ergibt aber "0x90x1".

Das Ergebnis der Addition ist immer dasselbe, egal welche Darstellung einer Zahl man wählt, selbst bei abstrakteren Darstellung wie Church-Numeralen oder Peano-Zahlen, doch die Darstellung und somit das Ergebnis der Konkatenation ist immer eine andere.

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 12:23
von Leonidas
mkesper hat geschrieben:Konsequenterweise hätte man eigentlich auch 'a' + 'b' verbieten müssen.
Tatsächlich ist das auch ein Thema über das man sich vortrefflich streiten kann und viele Programmiersprachencommunities haben dazu unterschiedliche Ansichten.

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 15:46
von BlackJack
Weswegen es ja auch eine Vielzahl von Operatorsymbolen in verschieden Programmiersprachen gibt. :-)

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 15:57
von mutetella
@all
Danke für Eure Mühe, das alles hat meinen Horizont wieder ein klein wenig erweitert!!
mkesper hat geschrieben:Konsequenterweise hätte man eigentlich auch 'a' + 'b' verbieten müssen.
Du meinst die Notation, oder? Denn eine Addition von strings gibt es ja nicht. Und auf Konkatenation kann ja nicht verzichtet werden...

mutetella

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 16:01
von pillmuncher
Man hätte auch schreiben können: sowohl ganze Zahlen als auch Zeichenfolgen bilden jeweils eine Algebra, und zwar ein Monoid. Die einfachste Algebra heißt Halbgruppe, das ist eine Menge mit einer assoziativen binären Operation über den Elementen, zB.

Code: Alles auswählen

1 + 2 == 3
2 * 3 == 6
'a' + 'bc' == 'abc'
[1, 2, 3] + [4, 5] == [1, 2, 3, 4, 5]
set([1, 2, 3]) | set([3, 4]) == set([1, 2, 3, 4])
Wie erwähnt, muss die Operation außerdem assoziativ sein:

Code: Alles auswählen

(1 + 2) + 3 == 1 + (2 + 3)
(2 * 3) * 4 == 2 * (3 * 4)
('a' + 'bc') + 'def' == 'a' + ('bc' + 'def')
([1, 2, 3] + [4, 5]) + [6] == [1, 2, 3] + ([4, 5] + [6])
(set([1, 2, 3]) | set([3, 4])) | set([2]) == set([1, 2, 3]) | (set([3, 4]) | set([2]))
Man kann sehen, dass es auf das Operatorsymbol nicht ankommt, sofern sich die Operation nur wie gewünscht verhält.

Ein Monoid erhält man, wenn es in der jeweiligen Menge zusätzlich ein sog. Identitätselement gibt, also ein Element, das bezüglich der Operation neutral ist:

Code: Alles auswählen

3 + 0 = 3
4 * 1 == 4
'hallo' + '' == 'hallo'
[1, 2, 3] + [] == [1, 2, 3]
set([1, 2, 3]) | set() == set([1, 2, 3])
Wenn man Funktionskomposition und eine Identitätsfunktion hat, bilden auch 1-stellige Funktionen ein Monoid:

Code: Alles auswählen

def compose(f, g):
    return lambda x: g(f(x))


class composable(object):

    def __init__(self, function):
        self.function = function

    def __mul__(self, other):
        return composable(compose(self.function, other))

    def __call__(self, x):
        return self.function(x)


@composable
def identity(x):
    return x


@composable
def add4(x):
    return x + 4


@composable
def mul3(x):
    return x * 3


@composable
def pow2(x):
    return x ** 2


u = add4 * mul3
v = add4 * identity

assert u(5) == 27
assert v(5) == add4(5)


a = (add4 * mul3) * pow2
b = add4 * (mul3 * pow2)

assert a(5) == b(5)
Das funktioniert, solange es sich um Endofunktionen handelt, also um Funktionen, deren Definitionsbereich identisch mit ihrem Wertebereich ist. Andere Funktionen, zB. solche, die Zahlen auf Strings, Strings auf Listen, Listen auf Mengen, etc. abbilden, kann man so leider nicht komponieren. Angenommen zB., man hat Funktionen, die nicht nur eine Berechnung ausführen, sondern zusätzlich noch mitschreiben sollen, welche Berechnungen gemacht worden sind:

Code: Alles auswählen

def foo(n):
    result = n + 3
    return result, 'foo: {0} plus 3 ist {1}'.format(n, result)

def bar(n):
    result = n * 2
    return result, 'bar: {0} mal 2 ist {1}'.format(n, result)
Hier bilden foo() und bar() jeweils eine Zahl auf ein Paar (Zahl, String) ab. Versuchte man beide mittels compose() hintereinander auszuführen:

Code: Alles auswählen

broken = compose(foo, bar)
print broken(5)
käme als Ergebnis dies hier heraus:

Code: Alles auswählen

((8, 'foo: 5 plus 3 ist 8', 8, 'foo: 5 plus 3 ist 8'), "bar: (8, 'foo: 5 plus 3 ist 8') mal 2 ist (8, 'foo: 5 plus 3 ist 8', 8, 'foo: 5 plus 3 ist 8')")
Nicht genau das, was man haben möchte. Statt dessen hätte man lieber das Resultat der Berechnung, und dann zB. zeilenweise, welche Funktion was wie berechnet hat, etwa so:

Code: Alles auswählen

foo: 5 plus 3 ist 8
bar: 8 mal 2 ist 16
Kann man solche Funktionen irgendwie komponierbar machen? Ja, zB. so:

Code: Alles auswählen

def logged_bind(logged_function, value, old_log):
    result, new_log = logged_function(value)
    log = '\n'.join([old_log, new_log])
    return result, log

class logged_composable(composable):
    def __mul__(self, other):
        def composed(x, s=''):
            y, t = logged_bind(self.function, x, s)
            return logged_bind(other, y, t)
        return logged_composable(composed)

@logged_composable
def foo(n):
    result = n + 3
    return result, 'foo: {0} plus 3 ist {1}'.format(n, result)

@logged_composable
def bar(n):
    result = n * 2
    return result, 'bar: {0} mal 2 ist {1}'.format(n, result)

baz = foo * bar
result, log = baz(5)
assert result == 16
print log
Das Ergebnis ist dabei tatsächlich das gewünschte.

Wenn man logged_bind() etwas abändert und zusätzlich eine Identitätsfunktion definiert:

Code: Alles auswählen

def logged_bind(logged_function, value, old_log):
    result, new_log = logged_function(value)
    log = '\n'.join(s for s in [old_log, new_log] if s)
    return result, log

@logged_composable
def logged_identity(x):
    return x, ''
dann hat man sogar wieder ein Monoid:

Code: Alles auswählen

a = bar * logged_identity
b = logged_identity * bar
c = bar
assert a(5) == b(5) == c(5)
Strukturen dieser Art nennt man Monaden. Sie stellen einen Mechanismus zur Verfügung, mit dem man Nicht-Endofunktionen komponieren kann. Man kann Monaden in Python explizit machen, indem man ihnen eigene Klassen spendiert:

Code: Alles auswählen

class LoggingMonad(object):

    def __init__(self, value, log=''):
        self.value = value
        self.log = log

    def __rshift__(self, function):
        result = function(self.value)
        log = '\n'.join(s for s in [self.log, result.log] if s)
        return LoggingMonad(result.value, log)

    class composable(composable):
        def __mul__(self, other):
            return composable(lambda x: self.function(x) >> other)

    @staticmethod
    @composable
    def identity(x):
        return LoggingMonad(x, '')


@LoggingMonad.composable
def foo(n):
    result = n + 3
    return LoggingMonad(result, 'foo: {0} plus 3 ist {1}'.format(n, result))


@LoggingMonad.composable
def bar(n):
    result = n * 2
    return LoggingMonad(result, 'bar: {0} mal 2 ist {1}'.format(n, result))


source = LoggingMonad(5)
target = source >> (foo * bar)
assert target.value == 16
print target.log


a = source >> (bar * LoggingMonad.identity)
b = source >> (LoggingMonad.identity * bar)
assert (a.value, a.log) == (b.value, b.log)
Das >> übernimmt hier die Aufgabe von logged_bind() oben.

Der Witz bei alldem ist nun, dass das Logging in jeder Funktion unabhängig von allem anderen funktioniert. Jede Funktion muss nur ihren eigenen Log-String ausgeben und die monadische bind-Funktion >> kümmert sich darum, dass die Konkatenation der Log-Strings der Aufrufreihenfolge folgt. Die Alternative wäre, dass jede Funktion einen zusätzlichen Parameter mit dem bisherigen Log bekommt, den sie dann selbst (fehleranfällig) mit dem eigenen Log-String konkatenieren müsste. Das möchte man dann doch lieber nicht.

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 16:18
von mutetella
Ok. Ich mach' dann mal an meinem Kalender weiter...

Re: Warum nimmt sum() keine strings?

Verfasst: Montag 12. November 2012, 21:36
von pillmuncher
@mutetella: Ich hab's nochmal anders aufgebaut, dann wird's vielleicht klarer, warum man sowas brauchen könnte.

Re: Warum nimmt sum() keine strings?

Verfasst: Dienstag 13. November 2012, 09:10
von mutetella
@pillmuncher
Es ist auch nicht so, dass ich mir das nicht angeschaut habe (und noch ein paar mal anschauen werde). Allerdings ist das hartes Brot für mich, da muss ich lange d'ran kauen... :)
Jedenfalls herzlichen Dank auch für Deine Mühe! Ich bin immer wieder schwer beeindruckt und begeistert davon, wieviel Tiefe eine oberflächlich betrachtet "einfache Sache" doch haben kann.

mutetella

Re: Warum nimmt sum() keine strings?

Verfasst: Dienstag 13. November 2012, 09:52
von lunar
@mutetella Man sollte vielleicht noch hinzufügen, dass pillmunchers Beitrag theoretische Aspekte beschreibt. So würde man nicht Python programmieren.

Python ist eine imperative Sprache, in der sich die Semantik eines Programms aus der genauen Abfolge der Anweisungen ergibt. Per definitionem hat eine solche Sprache Zustände und jede Anweisung beschreibt den Übergang von einem Zustand in den nächsten. Die Anweisung "a = 10" lässt das Programm also in einen Zustand übergehen, in dem die Variable "a" nun den Wert "10" hat. Das theoretische Fundament solcher Sprachen ist die Turingmaschine.

In funktionalen Sprachen dagegen ergibt sich die Semantik eines Programms aus der Abfolge von Funktionsaufrufen. Während ein imperatives Programm eine Sequenz von Anweisungen ist, ist ein funktionales Programm ein einziger geschlossener Ausdruck. Man kann es sich quasi als eine riesige mathematische Formel vorstellen. Die theoretische Grundlage dieser Sprachen ist das Lambda-Kalkül, in dem es keine Zustände gibt. Ebenso wie in der Mathematik gibt es keine Variablen, die sich verändern.

Dummerweise ist die reale Welt zustandsbehaftet. Eine Funktion, die auf den Bildschirm zeichnet, ändert den Zustand des Bildschirms. Mithin besteht auch in funktionalen Sprachen die Notwendigkeit, Zustände zu beschreiben. An dieser Stelle zerfällt das Lager funktionaler Sprachen. Es gibt funktionale Sprachen, die dieses Problem pragmatisch lösen, indem sie einfach Sprachkonstrukte aus imperativen Sprachen übernehmen, beispielsweise die ML-Familie (SML, OCaml, F#). Dort gibt es Anweisungen, die Variablen einführen und verändern. Das ist einfach, schließt aber funktionale Reinheit („Purity“) aus.

Diese funktionale Reinheit, also die vollständige Abwesenheit von Seiteneffekte, ist aber eine durchaus wünschenswerte Eigenschaft. Dann nämlich ist eine Funktion über ihre Parameter und Rückgabewerte vollständig definiert, sie verändert unter Garantie keine globalen Zustände, e.g. globale Variablen, Bildschirmausgabe, etc. Das eröffnet verschiede Möglichkeiten, unter anderem Parallelisierung (da es per definitionem keine Race conditions geben kann), automatische Korrektheitsbeweise, etc. In solchen Sprachen muss man globale Zustände dann allerdings mühsam simulieren, indem man den vorherigen Programmzustand an jede Funktion übergibt, und aus jeder Funktion wieder zurückgibt. Damit kann man prinzipiell alles ausdrücken, nur ist es unendlich mühsam.

Monaden sind ein theoretisches Konstrukt, um das zu vereinfachen. Der Trick ist letztlich, dass man Funktionen einfach „hintereinanderschalten“ kann, und der Zustand dann implizit verwaltet wird. Daneben kann man mit Monaden noch diverse andere schicke Dinge tun, deren Praxistauglichkeit aber – nun ja – eher zweifelhaft ist. ;)

Re: Warum nimmt sum() keine strings?

Verfasst: Dienstag 13. November 2012, 15:07
von pillmuncher
@lunar: Ich gebe dir im Wesentlichen Recht. Strenge funktionale Reinheit ist nicht pythonisch und man braucht in Python im Gegensatz zu Haskell keine Monaden, um Zustände zu simulieren. Andererseits ist die Kritik aus dem funktionalen Lager am imperativen Programmierstil ja auch nicht ganz unberechtigt. Zu viele, sich möglicherweise überlagernde Zustände in einem Programm führen schnell dazu, dass man den Überblick verliert und Fehler einbaut.

Dass Monaden nicht besonders praxistauglich sind... hm. Einige Probleme lassen sich auch in Python elegant mittels Monaden lösen. Wenn man eine externe DSL baut, dann kann man den Interpreter leicht mittels Continuation Passing Style implementieren. Weil das aber eine Art funktionales Äquivalent zum goto ist, kann einem die Continuation Monade dabei helfen, nicht den Überblick zu verlieren. Außerdem bekommt man dann call/cc, eine Art funktionales Äquivalent zum Irrsinn. :wink:

Ein anderes Beispiel, wo Monaden in Python zweifellos nützlich sind, sind monadische Parser-Kombinatoren. Vor kurzem habe ich dazu ein Beispiel gepostet, das allerdings keinen Gebrauch vom Bind-Parser macht. Ein anderes Beispiel auf StackOverflow zeigt, wie einfach man mit einem monadischen Bind-Parser kontext-sensitive Grammatiken parsen kann.

In meiner Antwort auf mututella oben bin ich nur auf Monaden gekommen, weil ich mich nicht bremsen konnte. Wichtiger ist der Hinweis auf Algebra im Allgemeinen und Monoide im Besonderen. Das ist ein so basales Konzept, auf das man immer wieder stößt, und wenn man einen Problembereich als Monoid beschreiben kann, dann kann man - dh. ich - oft eine einfache und elegante Implementation daraus ableiten.

Re: Warum nimmt sum() keine strings?

Verfasst: Dienstag 13. November 2012, 15:54
von lunar
@pillmuncher Ich sage nicht, dass Monaden nicht besonders praxistauglich wären. Ich sage nur, dass manche Probleme, die man - gerade in der Haskell-Community - gerne mit Monaden löst, auch auf andere Weise gelöst werden können, gerade in nicht rein funktionalen Sprachen.

Der Interpreter ist ein gutes Beispiel: Eine CPS-Implementierung ist nicht die einzige Möglichkeit, man könnte auch ganz klassische AST-Traversierung verwenden, entweder per Pattern Matching und Rekursion oder über eine Visitor-Klasse, je nach Art der Sprache. Natürlich ist die CPS-Implementierung in einer Sprache mit Monaden sehr elegant, doch die Alternativen sind nicht minder gut, denn Eleganz ist letztlich auch eine Frage der Möglichkeiten, die eine Sprache bietet. In einer guten imperativen Sprache kann man auch elegante Lösungen implementieren ;)

Das Beispiel auf Stack Overflow ist zwar nett, aber meines Erachtens nicht das Argument für Monaden (zumal der Antwortende dort die Sprache auch durch das Einfügen von schließenden Tags auch so modifiziert, dass sich der Parser auf sie anwenden lässt. Die ursprüngliche Frage zeigt keine schließenden Tags). Man kann die dort gezeigte Sprache auch kontextfrei parsen, und in einer zusätzlichen Iteration über den AST validieren. Das wäre nicht wesentlich komplizierter als ein monadischer Parser, aber halt vor allem in einer Sprache mit Zuständen. Die dort gezeigte Sprache kann man ohnehin mit mächtigeren Bibliotheken für (nicht mehr ganz so) reguläre Ausdrücke parsen, ich glaube, Perl und .NET haben entsprechende Konstrukte in ihren RE-Implementierungen.

Ich sage wohlgemerkt nicht, dass Monaden nicht elegant oder interessant wären, im Gegenteil, doch ich glaube, dass man viele Probleme, die man mit Monaden löst, gar nicht hätte, wenn man eine weniger strenge und mehr pragmatische Sprache verwenden würde :) Gerade in der Haskell-Community wird mit Monaden gerne geistige Masturbation betrieben. Man verzeihe mir diesen Ausdruck, doch mir fiel kein passenderes Bild ein. ;) Hinzu kommt, dass Monaden zur sinnvollen Anwendung einen gewissen theoretischen Hintergrund voraussetzen. Man muss mindestens die Bedeutung und den tieferen Sinn der Monaden-Gesetze verstanden haben, und schon das ist bestimmt nicht jedem Programmierer gegeben. Ich glaube auch, dass diese Komplexität eines der größten Hindernisse zur weiteren Verbreitung von Haskell ist, genau wie die theoretischen Aspekte früher der Verbreitung von LISP grenzen gesetzt haben.

Was die grundlegende Betrachtung zu algebraischen Strukturen angeht, gebe ich Dir natürlich uneingeschränkt recht.

Re: Warum nimmt sum() keine strings?

Verfasst: Dienstag 13. November 2012, 15:57
von lunar
@mutetella Entschuldige, wenn wir Deine Frage hier so in die Theorie entführen. Fühle Dich bitte nicht ausgeschlossen :) Stelle gerne Fragen, wenn Dich etwas interessiert.

Re: Warum nimmt sum() keine strings?

Verfasst: Dienstag 13. November 2012, 16:50
von mutetella
@lunar
Überhaupt kein Problem, ganz im Gegenteil! Ich sitze hier, lese eure Beiträge, switche ständig zwischen Google, Wikipedia und Linguee (ich brauch' unbedingt 'mal 'nen zweiten Monitor!!) und hab' richtig Spass dabei. Schade nur, dass ich bereits einen ganz anderen Weg gegangen bin und deshalb heute insbesondere vom Programmieren so wenig Ahnung hab' und das auch nicht mehr aufholen kann. Da kann ich jedem nur raten: Augen auf bei der Berufswahl! :mrgreen:

Ja klar, ich stelle Fragen, wenn es mir zu bunt wird... :)

mutetella

Re: Warum nimmt sum() keine strings?

Verfasst: Dienstag 13. November 2012, 18:45
von pillmuncher
lunar hat geschrieben:Ich sage nicht, dass Monaden nicht besonders praxistauglich wären. Ich sage nur, dass manche Probleme, die man - gerade in der Haskell-Community - gerne mit Monaden löst, auch auf andere Weise gelöst werden können, gerade in nicht rein funktionalen Sprachen.
Ja, ich hatte dich da ungenau zitiert. Du nanntest die Praxistauglichkeit "nun ja - eher zweifelhaft" ;) Und natürlich gebe ich dir Recht.
lunar hat geschrieben:Der Interpreter ist ein gutes Beispiel: Eine CPS-Implementierung ist nicht die einzige Möglichkeit, [...] die Alternativen sind nicht minder gut, denn Eleganz ist letztlich auch eine Frage der Möglichkeiten, die eine Sprache bietet.
Es hängt IMO von beidem ab, der Implementierungssprache und der zu interpretierenden. Wenn letztere deklarativ ist, bietet sich die CPS-Variante an, weil das Environment, das duch die Continuations transportiert werden muss, dann "monoton" ist und leicht als Stack modelliert werden kann, und Continuations sind ja sowas wie ein selbst verwalteter "zukünftiger" call stack. Aber letztlich sind alle Lösungen äquivalent.
lunar hat geschrieben:Das Beispiel auf Stack Overflow ist zwar nett, aber meines Erachtens nicht das Argument für Monaden (zumal der Antwortende dort die Sprache auch durch das Einfügen von schließenden Tags auch so modifiziert, dass sich der Parser auf sie anwenden lässt. Die ursprüngliche Frage zeigt keine schließenden Tags). Man kann die dort gezeigte Sprache auch kontextfrei parsen, und in einer zusätzlichen Iteration über den AST validieren. Das wäre nicht wesentlich komplizierter als ein monadischer Parser, aber halt vor allem in einer Sprache mit Zuständen.
.Naja, ich schrieb dort (ich war der Antwortende :) ), dass das die Lösung wäre, sofern die Grammatik modifiziert werden könnte, was der OP ja schon angedeutet hatte. Was mir an meiner Lösung gefällt, ist, dass sie deklarativ, extrem kurz, aber trotzdem sehr leicht verständlich ist. Man kann alles quasi "auf einen Blick" erfassen. Imperativ programmiert würde es wohl länger und unübersichtlicher werden.
lunar hat geschrieben:[...]ich glaube, dass man viele Probleme, die man mit Monaden löst, gar nicht hätte, wenn man eine weniger strenge und mehr pragmatische Sprache verwenden würde :)
Ja. Ich habe lange überlegt, welche Monaden man in Python brauchen könnte, und mehr als die Continuation Monade, monadische Parser-Kombinatoren und vielleicht die beschriebene Logging-Monade ist mir nicht eingefallen. Die List-Monade ist durch die list comprehension in Python zur Genüge abgedeckt, die Maybe/Error/Failure-Monaden durch Exceptions, None und Generatoren, die ungültige Werte herausfiltern, die IO-Monade durch print(), input() und open().
lunar hat geschrieben:Hinzu kommt, dass Monaden zur sinnvollen Anwendung einen gewissen theoretischen Hintergrund voraussetzen. Man muss mindestens die Bedeutung und den tieferen Sinn der Monaden-Gesetze verstanden haben, und schon das ist bestimmt nicht jedem Programmierer gegeben. Ich glaube auch, dass diese Komplexität eines der größten Hindernisse zur weiteren Verbreitung von Haskell ist, genau wie die theoretischen Aspekte früher der Verbreitung von LISP grenzen gesetzt haben.
Das sehe ich ebenso. Allerdings macht es mich auch ratlos. Ich denke mir immer, die anderen Programmierer müssten das doch verstehen, wenn ich es sogar verstehe. Andererseits deutet das Fake-Zitat von Philip Wadler "a monad is a monoid in the category of endofunctors, what's the problem?" schon auf das Problem der Theoretiker hin, sich gegenüber Ottonormalprogrammierer verständlich zu machen. Als ich mit Monaden angefangen habe, habe ich auch erst lange nichts kapiert, weil es in diesem krausen math-speak daherkam und kein Monaden-Tutorial wirklich auf den wesentlichen Punkt kam, d.i. dass Monaden primär einen Kompositionsmechanismus für Nicht-Endofunktionen sind, also Pipelining von Funktionen vom Typ T-->T'.

@mutetella: Ich hoffe, ich habe es in meinem Beitrag oben nicht ebenso gemacht, ich habe mir zumindest Mühe gegeben, die basalen Konstrukte (Monoid, Endofunktion, ...) verständlich zu machen. Wenn mir das nicht gelungen sein sollte, gib bitte bescheid, ich denke, ich kann es evtl. noch vereinfachen, die Konzepte selbst sind nämlich nicht schwer.

Re: Warum nimmt sum() keine strings?

Verfasst: Mittwoch 14. November 2012, 02:49
von pillmuncher
@mutetella: Um nochmal auf sum() zurückzukommen: wie bereits erwähnt ist ein Monoid eine Struktur, bestehend aus einer Menge von Elementen (die sog. Trägermenge, zB. Zahlen, Strings, Mengen, 1-stellige Endofunktionen), mit einer binären assoziativen Operation (zB. +, *, |) und einem Identitätselement bezüglich dieser Operation, dh. einem Element, das sich bezüglich der Operation neutral verhält.

Binär bedeutet, dass die Operation 2-stellig ist, also zwei Elemente der Trägermenge auf ein drittes derselben abbildet. Die Infixnotation (zB. _ + _, _ * _) ist dafür nicht wesentlich, mit Präfixnotation und Klammern um die Argumente würde es genauso funktionieren (zB. plus(1, 2), mal(4, 5)). Entscheidend ist nur die sog. Signatur der Operation. Wenn T die Trägermenge ist, dann ist die Signatur TxT-->T. Das x bezeichnetet dabei den Operator für das Kreuzprodukt. Das ist die Menge aller Paare (a, b), so dass a und b Elemente aus T sind. Beide können auch dasselbe Element sein (sonst könnte man ja zB. kein Quadrat bilden).

Wenn die Operation über der gesamten Menge definiert ist, also für jedes beliebige Paar von Elementen wieder ein Element erzeugt, dann sagt man, die Trägermenge ist abgeschlossen bezüglich der Operation.

Deswegen, und weil die Operation qua Voraussetzung auch assoziativ ist, dh., dass zB. für + und alle Zahlen a, b, c gilt: (a + b) + c == a + (b + c), kann man die Operation verallgmeinern auf beliebige Tupel von Elementen der Trägermenge: a + b + c + d + e + ... == (a + (b + (c + (d + (e + ...) == sum((a, b, c, d, e, ...)). Wenn die Trägermenge int ist, dann sind sum((1, 2, 3)), sum((4, 5)), sum((3, 3, 3, 3)), sum((1,)), sum(()) alles gültige Ausdrücke.

Beim letzten Beispiel ist aber nicht unmittelbar klar, was das Ergebnis sein könnte. Hier kommt uns zuhilfe, dass int mit + ein Monoid bildet, dh., dass es auch ein Identitätselement bezüglich + besitzt, und das ist 0. Wir können also einfach definieren, dass sum(()) == 0 ist. Begründen können wir das damit, das jedes Tupel, dem wir ein leeres Tupel hinzufügen, wieder das ursprüngliche Tupel ergibt: (1, 2, 3) + () == (1, 2, 3), (4, 5) + () == (4, 5), () + () == (). Wenn die Summe von 1, 2 und 3 == 6 ist, und die Konkatenation von (1, 2, 3) und () wieder (1, 2, 3), dann muss sum((1, 2, 3) + ()) == sum((1, 2, 3)), also 6, sein. Da außerdem sum((1, 2, 3) + ()) == sum((1, 2, 3)) + sum(()) sein muss, muss auch sum(()) == 0 sein, da 6 == 6 + sum(()).

Tatsächlich ist das auch das Ergebnis, das Python ausspuckt:

Code: Alles auswählen

>>> sum(())
0
Da Python nicht entscheiden kann, ob irgendein leeres Tupel eines ist, das keine Zahlen enthält, oder eines, das keine Strings enthält, kann es nur festlegen, dass sum() in Python eben nur für Zahlen definiert ist und berechnet daher für ein leeres Zahlentupel das Identitätselement von Zahlen bezüglich +, und das ist 0.

Ich glaube, dass das der Grund dafür ist, dass sum() keine Strings akzeptiert, und nicht das quadratische Laufzeitverhalten der wiederholten Stringkonkatenation mittels +. Man hätte sum() leicht so implementieren können, dass es den Typ des ersten Elements der Sequenz ansieht und, falls er str ist, an ''.join() delegiert. Man könnte dagegenhalten, dass die Typen der Elemente der Sequenz ja nicht alle Strings zu sein brauchen, und die Vermutung, alle Elemente wären vom selben Typ wie das erste Element, zu stark sei. Aber jetzt gilt ja ebenso die Vermutung, dass alle Elemente Zahlen sind, und falls sich diese Vermutung als falsch herausstellt, wird eben eine Exception ausgelöst:

Code: Alles auswählen

>>> sum((1, 2, 3, 'hallo', 4))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'str'
Beide Situationen sind also symmetrisch. Welches + verwendet wird, ist ebenso vom tatsächlichen Typ abhängig, da auf Maschinenebene int-+ ja nicht dasselbe ist, wie float-+, oder complex-+. Man muss daher immer den tatsächlichen Typ der Elemente bestimmen, hätte es also auch für Strings tun können. Bleibt als einziger Unterschied das Identitätselement, das für Strings '' ist, für int 0, für float 0.0 und für complex 0j, und

Code: Alles auswählen

>>> 0 == 0.0 == 0j
True
>>> 0 == ''
False

Re: Warum nimmt sum() keine strings?

Verfasst: Mittwoch 14. November 2012, 08:27
von BlackJack
Der Beitrag klingt jetzt so ein bisschen als wenn man `sum()` nur für Zahlen benutzen kann. Eigentlich kann man es für alles benutzen ausser Zeichenketten, denn das verwendete neutrale Element ist zwar mit 0 vorbelegt, aber man kann da optional ein beliebiges Anderes angeben:

Code: Alles auswählen

In [24]: xs
Out[24]: [['a'], ['b'], ['c']]

In [25]: sum(xs, [])
Out[25]: ['a', 'b', 'c']
Und das obwohl dieses Beispiel genau das gleiche ungünstige Laufzeitverhalten hat wie das Aufsummieren von Zeichenketten. Einzig auf den Typ Zeichenkette prüft `sum()` allerdings intern. ”Komisch” ist das also schon.

Re: Warum nimmt sum() keine strings?

Verfasst: Mittwoch 14. November 2012, 09:28
von snafu
BlackJack hat geschrieben:Und das obwohl dieses Beispiel genau das gleiche ungünstige Laufzeitverhalten hat wie das Aufsummieren von Zeichenketten.
Stimmt. Aber für Strings gibt es eine Alternative, um ungünstiges Laufzeitverhalten zu vermeiden - nämlich das in der Fehlermeldung beschriebene `.join()`. Für Listen und andere Objekte gibt es so etwas nicht. Ich stimme aber zu, dass diese künstliche Beschränkung merkwürdig ist. Wenn man `sum()` im streng mathematischen Sinn sehen möchte, dann sollte man IMHO ausschließlich Zahlen erlauben und zum Konkatenieren von vielen aufeinander folgenden Objekten eine separate Möglichkeit anbieten. Fände zumindest ich irgendwie besser.

Wobei auf der anderen Seite die Anwendung von "*" und "+" in Python ja ohnehin recht weit gefasst ist und man sich mit meiner Idee wohl auch gewissermaßen das "ducktypische" Verhalten kaputt machen würde. Oder sagen wir mal: Nicht das Verhalten an sich, aber es wäre halt eine starke Einschränkung. Naja, keine Ahnung... ^^

Re: Warum nimmt sum() keine strings?

Verfasst: Mittwoch 14. November 2012, 10:16
von mutetella
Ok, ich häng' noch sehr stark an den Begrifflichkeiten fest:
  1. Endofunktion
    Sind 'identity', 'add4', 'mul3' und 'pow2' in pillmunchers 'composable'-Beispiel Endofunktionen?
    Mir ist noch nicht ganz klar, was damit gemeint ist, dass bei einer Endofunktion
    domain -> codomain | input -> output | Definitionsbereich -> Wertebereich
    sein muss. Bedeutet das mit anderen Worten, wenn 'int' reinkommt darf auch nur mit 'int' gehandelt werden und muss auch 'int' rauskommen (oder 'str' oder was auch immer)?
  2. Das Identitätselement...
    ...ist zur Ermittlung des Typs notwendig? Also letztlich ein type()? Ein Spiegel?
  3. Monoiden
    Sind das Monoiden...
    (0 2 3 -)
    ('' 'b' 'd' +)
    ( () (0,) (3,4) *)
    ... und das keine
    (2 3 -)
    (0 2 3 /)
    ( () ('a',) (3,4) *)
    ??

Re: Warum nimmt sum() keine strings?

Verfasst: Mittwoch 14. November 2012, 11:56
von pillmuncher
BlackJack hat geschrieben:

Code: Alles auswählen

In [24]: xs
Out[24]: [['a'], ['b'], ['c']]

In [25]: sum(xs, [])
Out[25]: ['a', 'b', 'c']
Um Don Knuth zu paraphrasieren: Beware of bugs in the above statements; I have only proved them correct, not tried them. :oops:
Alle Zeiten sind UTC+01:00
Seite 2 von 3

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de