Gleichung von "Programmierung Perlen" - kann mir jemand erklären?
Es fühlt sich an, als würde ich feststecken, meine Freunde. Kann mir jemand erklären, wie man Gleichungen aus "Perlen des funktionalen Algorithmus Designs", Kapitel 11 ("Nicht die maximale Segmentsumme") auswählt.
Hier ist das Problem (ein bisschen vereinfacht) Lassen Sie uns einige Zustände mit gegebenen Übergängen haben:
%Vor%Definieren wir nun pick:
%Vor%Der Autor behauptet, dass die folgenden sieben Gleichungen gelten:
%Vor%Kann mir jemand in einfachen Worten erklären, warum diese Gleichungen wahr sind, wie können wir einen offensichtlichen Beweis beweisen? Ich habe das Gefühl, dass ich S-Gleichungen fast verstehe, aber insgesamt bleibt das schwer fassbar.
1 Antwort
Ok, ich musste deinen Zustandsgraphen visualisieren:
Geben Sie eine Typ-Signatur für pick :: State -> [[Bool]] -> [(State, [Bool]) ein.
Nun, das geht nicht mit Ihrer ersten Gleichung pick E xs = [[]] - es müsste pick E xs = [(E,[])] sein.
Vielleicht wollten Sie pick so definieren:
Unter der Annahme dieser Definition macht die erste Gleichung jetzt Sinn. Es wird behauptet, dass, wenn Sie bei E beginnen, die einzige Folge von Booleschen Werten in xs , die bei E enden, die leere Liste ist.
Beachten Sie, dass dabei Folgendes gilt: [] ∈ xs .
Auch wenn ys = replicate n False , pick E [ys] = [ys] , so bedeutet dies, dass ∀ n , ys ∉ xs .
Die zweite, vierte und sechste Gleichung haben alle die Form pick _ [ ] = [ ] , was trivial wahr ist durch die Definition von map und filter .
Die dritte Gleichung, pick S (xs ++ [x]) = map (++[x ]) (pick S xs ++ pick E xs) , macht auch keinen Sinn. Ich vermute, es versucht zu sagen:
Das heißt: Jeder Pfad, der bei E beginnt und bei S endet, kann erstellt werden, indem ein bestehender Pfad zu E oder S und anhängender True erstellt wird. Genauso muss jeder Pfad, der auf S endet, mit True enden.
Die fünfte Gleichung ist in ähnlicher Weise unsinnig und sollte wie folgt angegeben werden:
%Vor%Und die siebte Gleichung sollte wie folgt formuliert werden:
%Vor%Tags und Links algorithm haskell functional-programming finite-automata