[Progra] Haskell Auswertung

[aRo]

Hi!

Ich habe noch 2 Fragen zur Auswertungsstrategie von Haskell:

1) Die Operatoren sind strikt. Was bedeutet das genau? Nehmen wir an, wir haben eine Funktion: f(3+2:bla). Ich nehme an Haskell weiß jetzt, dass nach dem Doppelpunkt keine Zahl mehr kommt, die er für diese Addition braucht. Also wäre hier der nächste Schritt die 3+2 auszuwerten?

2) Nehmen wir an wir haben eine Funktion f mit folgendem Argument:
f(4:2:blabla). Haskell muss nun entscheiden, ob dies auf ein Pattern ala x:y:xs matcht. Muss er jetzt gucken ob blabla wirklich eine Liste mit Elementen vom Typ Int ist, oder nimmt er das direkt implizit an?

[NeX]

so wie ich das verstanden habe --natürlich ohne gewähr -- weiss haskell ja vorher weiss eine funktion zurückliefert....

denn entweder man schreibt es selbst à la

Code: Alles auswählen

 bla :: [Int] -> Int

oder haskell macht das selbst...zumindest wie ich verstanden habe....

ich habe aber auch eine Frage:

folgende situation:

Code: Alles auswählen

 
len :: [Int] -> Int
len [] = 0
len (x:xs) = 1+length xs


jetzt fallen wir bei dem Aufruf len [1,2,3]

zwei möglichkeiten ein....

(i)
1 + len [2,3]
1 + ( 1 + len [3])

(ii)
oder eben ohne Klammer

...
1 + 1 + len [3]

bei (ii) wäre der nächste auswertungsschritt
2 + len [3]

bei (i) aber nicht denn dann müsste haskell ( 1+len[3]) erst auswerten oder?

[Coolcat]

@NeX: Möglichkeit (i), wobei du wohl

1 + ( 1 + len [3])

meintest. Siehe dazu auch Übung 11, Aufgabe 1 vom WS05/06

Der Grund dafür ist, das der Operator + eben strikt ist. Also len [2,3] muss zuerst vollständig ausgewertet werden, bevor das erste + angewendet wird.

[NeX]

@NeX: Möglichkeit (i), wobei du wohl

1 + ( 1 + len [3])

meintest. Siehe dazu auch Übung 11, Aufgabe 1 vom WS05/06

Der Grund dafür ist, das der Operator + eben strikt ist. Also len [2,3] muss zuerst vollständig ausgewertet werden, bevor das erste + angewendet wird.

ja das meinte ich natürlich...habe ich gerade auch geändert....

d.h. als fazit...man sollte klammern durchaus beachten wenn ich das jetzt richtig verstanden habe....

[Coolcat]

jo

[O.D.]

1) Die Operatoren sind strikt. Was bedeutet das genau? Nehmen wir an, wir haben eine Funktion: f(3+2:bla). Ich nehme an Haskell weiß jetzt, dass nach dem Doppelpunkt keine Zahl mehr kommt, die er für diese Addition braucht. Also wäre hier der nächste Schritt die 3+2 auszuwerten?

Haskell geht peinlichst genau nach den in der prelude angegebenen Operaorprioritäten. Hier mal der entsprechende Block aus der prelude

Code: Alles auswählen

-- Standard value bindings {Prelude} ----------------------------------------

infixr 9  .
infixl 9  !!
infixr 8  ^, ^^, **
infixl 7  *, /, `quot`, `rem`, `div`, `mod`, :%, %
infixl 6  +, -
--infixr 5  :    -- this fixity declaration is hard-wired into Hugs
infixr 5  ++
infix  4  ==, /=, <, <=, >=, >, `elem`, `notElem`
infixr 3  &&
infixr 2  ||
infixl 1  >>, >>=
infixr 1  =<<
infixr 0  $, $!, `seq`

Dein Ausdruck geht nur desshalb auf, da + in Deinem Ausdruck höher priorisiert reduziert wird. Angenommen Du führst einen neuen Operator

Code: Alles auswählen

(+?) = (+)

ein, der genau das gleiche macht wie das plus. Du gibst ihm aber

Code: Alles auswählen

infix 1 +?

(also eine kleinere Priorität). Dann wird Dein Ausdruck in die Hose gehen, weil Haskell dann erst den Datenkonstruktor : auswertet und dann Integer zu [Integer] addieren soll.

2) Nehmen wir an wir haben eine Funktion f mit folgendem Argument:
f(4:2:blabla). Haskell muss nun entscheiden, ob dies auf ein Pattern ala x:y:xs matcht. Muss er jetzt gucken ob blabla wirklich eine Liste mit Elementen vom Typ Int ist, oder nimmt er das direkt implizit an?

blabla KANN nur eine Liste von Werten mit dem Typ Num sein.
Nimm folgenden Ausdruck

Code: Alles auswählen

(\(x:xs) -> x)(3:4:5:[4.2])

Obwohl Dich nur der erste Wert interessiert, darfst Du trotzdem keine ungültige Liste erzeugen. Der Wert 4.2, der ja Double ist, legt sogar das Ergebnis (3) auf Double fest. Schreibst Du statt 4.2 einfach nur 4, dann hat die 3 die als Ergebnis rauskommt den Typ Int bzw. Integer.

[Der Fuß]

Der Grund dafür ist, das der Operator + eben strikt ist. Also len [2,3] muss zuerst vollständig ausgewertet werden, bevor das erste + angewendet wird.

Also, auch wenn die Restliste sehr lange ist, wird dass alles erst ausgewertet bevor vorne irgendwelche zahlen addiert oder gar multipliziert werden?

[Coolcat]

jap

[NeX]

so noch eine frage die sich gerade wieder egeben hat....

folgende Situation 30/10 + foo(....)

foo :: [Int] -> Int

wie sieht der nächste auswertungsschritt aus?

(i) 3 + foo(...)
hier wäre es meine auffassung von leftmost outermost....
er muss den ausdruck 30/10 ja auch auswerten um + rechnen zukönnen...

(ii) 30/10 + (40/10 +foo(....))
hier würde ich sagen das er weiss das 30/10 eine Int Zahl ist und bei foo
weiss er das noch nicht....

somit weiss ich wieder nicht was sache ist

[O.D.]

1. Gegenfrage: Wie kommst Du aus der Ausgangsituation auf (ii)?
2. Gegenfrage: Wie kommst Du darauf, dass er den "Rückgabetyp" von foo nicht kennt. Du hast foo doch selbst als [Int]->Int angegeben, daher ist doch der Rückgabetyp ein Int.

[sumpfmensch]

wenn ich leftmost - outermost richtig verstanden habe, guckt er immer von links aus und versucht dann von da den ausdruck auszuwerten...

das hieße hier (i)

[HE]

so noch eine frage die sich gerade wieder egeben hat....

folgende Situation 30/10 + foo(....)

foo :: [Int] -> Int

wie sieht der nächste auswertungsschritt aus?

(i) 3 + foo(...)
hier wäre es meine auffassung von leftmost outermost....
er muss den ausdruck 30/10 ja auch auswerten um + rechnen zukönnen...

(ii) 30/10 + (40/10 +foo(....))
hier würde ich sagen das er weiss das 30/10 eine Int Zahl ist und bei foo
weiss er das noch nicht....

somit weiss ich wieder nicht was sache ist

So, hier mal etwas zu genau diesem Thema, was Herr Giesl nochmal beleuchtet hat. Sei der folgende Code gegeben:

Code: Alles auswählen

length [] = 0
length (_:xs) = 1 + length xs

head (x:_) = x

facs 0 = [1]
facs (n+1) = (n+1) * (head facs n) : facs n

isEmpty1 []    = True
isEmpty1 (_:_) = False

isEmpty2 xs = length xs == 0


(Das ist aus der Übung 11 im WS05/06)

Die Frage ist jetzt, wie isEmpty2 ausgewertet werden soll für einen
Aufruf isEmpty2 facs 2 (ein paar Schritte ausgelassen, um schneller zum
interessanten Teil zu kommen):

Code: Alles auswählen

   isEmpty2 facs 2
-> length 2 * (head facs 1) : facs 1
-> 1 + length facs 1
-> 1 + length 1 * (head facs 0) : facs 0
-> 1 + 1 + length facs 0

(a) -> 2 + length facs 0
(b) -> 1 + 1 + length 1:[]


Dazu nun die Antwort von Prof. Giesl:

(b) ist richtig und zwar aus folgendem Grund:

Da steht am Anfang 1 + (1 + length facs 0), mit dieser Klammerung.
Dass + assoziativ ist, wei Haskell nicht. Da + nur auswerten kann,
wenn beide Argumente bereits voll ausgewertete Zahlen sind, kann
keines der beiden + selbst ausgewertet werden. Stattdessen muss
man bei der Auswertung von length facs 0 weitermachen.

Dazu nochmal ein Kommentar von mir: Ich bin mir nicht sicher, dass das unbedingt so sein muss, sondern glaube, dass das ein Implementationsdetail ist, denn:
1 + 1 + 1 + foo könnte auch als (((1 + 1) + 1) + foo) geklammert sein (wenn der Parser entsprechend arbeitet und immer den Operator ganz rechts zuerst betrachtet). Dann ist aber Outermost bar + foo [mit bar == ((1+1)+1)], das kann nicht ausgewertet werden, weil beide Teilausdrücke nicht evaluiert worden sind. Der, der nun leftmost ist, ist bar, d.h. das führt zu 3 + foo. Wobei das rein hypothetisch ist, im Allgemeinen dürfte der Parser immer von links nach rechts gehen.

[Eshmael]

Aber 1+1:ksjdg ist doch eindeutig und wertet 1+1 unabhängig von dem hinter dem : aus. Korrekt? Also wäre der nächste Schritt 2:ksjdg .. right?

[mirko]

Aber 1+1:ksjdg ist doch eindeutig und wertet 1+1 unabhängig von dem hinter dem : aus. Korrekt? Also wäre der nächste Schritt 2:ksjdg .. right?

Code: Alles auswählen

Hugs> 1+1:[3]
[2,3]
Hugs>


beantwortet das deine frage?

[Eshmael]

ähm... NEIN.... das erst wenn er MUSS auflöst ist klar.

Etwas genauer worauf meine Frage abzielt:

Code: Alles auswählen

1+1:(funktion exp1 exp2 ... expn)

Passiert nun im nächsten Schritt:
a) Auswertung 1+1 oder
b) Auswertung funktion?

Da bei :

Code: Alles auswählen

 1+1+(funktion exp1 ... expn)

...auch erst die Funktion ausgewertet wird bevor addiert wird (obwohl das theoretisch auch früher ginge).

Ich nehme nur an das strikt meint: Solange eine Summe von mit strikten Operatoren verbundenen Ausdrücken vorliegt müssen alle Ausdrücke ausgewertet werden, bevor die Operatoren angewendet werden.

In dem Falle meiner Frage ist aber die Summe von [...blabla...] abgeschlossen weil : nicht strikt ist.

Korrekt?