ggT

[BlackMamba]

Hallo, in der Uni mussten wir die Programiersprache Haskell lernen....sehr blöde Sache....
Naja, ich habe mal probiert etwas in Python zu übertragen und zwar den ggt Algorithmus. Leider gibt es immer eine ErrorMeldung und da ich leider noch kein Vernünftiges Programm habe, das mit die Fehler in meinem Quellcode anzeigt (kennt jemand ein gutes was auch unter Vista läuft?) bzw, zumindest die Zeile anzeigt, stelle ich das hier mal rein.
Danke schon im Vorraus für die Hilfe.

Code: Alles auswählen

def ggT(a,b):
    if a > b :
        if b == 0 :
            print a
        else :
            ggT b ( a % b)
    else :
        ggT(b,a)
    return [a]
    return [b]



print ggT(1234567891, 123456789)        

[Gnushi]

N'Abend!

Leider gibt es immer eine ErrorMeldung und da ich leider noch kein Vernünftiges Programm habe, das mit die Fehler in meinem Quellcode anzeigt (kennt jemand ein gutes was auch unter Vista läuft?) bzw, zumindest die Zeile anzeigt, stelle ich das hier mal rein.

Das von dir geschriebene Programm ist nicht in Python geschrieben. Bitte lies mal irgendein Tutorial, wo Schlüsselworte wie "return" erklärt werden und man auf den Aufbau von Funktionen eingeht.

Fehlermeldungen siehst du, wenn du
python programm.py
eintippst, am besten im DOS-Fenster.

GnuShi

[noise]

Leider gibt es immer eine ErrorMeldung und da ich leider noch kein Vernünftiges Programm habe, das mit die Fehler in meinem Quellcode anzeigt

Huch? Was genau ist an dem traceback unverständlich?

Code: Alles auswählen

    ggT b ( a % b)
        ^
SyntaxError: invalid syntax

[BlackMamba]

hab meinen Fehler gefunden.

Danke für die Hilfe!

[BlackJack]

Einzahl? Da sind wohl mehrere drin. Allerdings ist eine rekursive Lösung nicht so günstig, wenn es eine einfache Iterative gibt. In Haskell kann man so etwas nur als Rekursion ausdrücken, in Python sollte man Rekursion auf Probleme beschränken, die Rekursion wirklich benötigen weil ein Funktionsaufruf relativ teuer ist, es das Rekursionslimit gibt, und der Compiler keine Endrekursion erkennt und optimiert.

Code: Alles auswählen

def ggT(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

[noise]

in Python sollte man Rekursion auf Probleme beschränken, die Rekursion wirklich benötigen weil ein Funktionsaufruf relativ teuer ist, es das Rekursionslimit gibt, und der Compiler keine Endrekursion erkennt und optimiert.

Ja, das finde ich auch. Vor allem sind viele "offensichtlich" rekursive Algorithmen auch iterative ausdrückbar, wie zum beispiel das flatten von listen.

Naja, tail call optimization würde Pyhon gut stehen, aber das für und gegen bzw. die Machbarkeit war ja schon Gegenstand diverser Diskurse auf einigen mailing lists.

EDIT: Der Vollständigkeitshalber: dafür gibt es ein Dekorator der aber langsam ist. Zumindest hat man aber dadurch nicht das Problem mit dem Rekursionslimit. Natürlich nur für echte rekursive Strukturen nutzen, da echt langsam!

http://aspn.activestate.com/ASPN/Cookbo ... ipe/474088

[BlackMamba]

jetzt funktionierts....war ein bischen mit der Syntax durcheinander gekommen.

Code: Alles auswählen

def Euclid (a,b):
    if (b == 0) :
        return a
    else :
        return Euclid (b, (a % b))




print Euclid (123456789,12345678)    

[BlackMamba]

ich habs aber wieder rekursiv gelöst.

Danke nochmal für eure Tipps.

[BlackMamba]

@ BlackJack : Da hast du recht, in Haskell weiß man vor lauter Rekursionen nicht wo man hin soll...

[BlackJack]

Na, immer einen rekursiven Abstieg weiter runter, bis man den Rekursionsanker trifft und dann wieder rauf. Ist doch ganz einfach.

Oder halt möglichst viel mit den Funktionen höherer Ordnung ausdrücken.

[noise]

Na, immer einen rekursiven Abstieg weiter runter, bis man den Rekursionsanker trifft und dann wieder rauf. Ist doch ganz einfach.

[BlackJack]

Wobei beim ggT von der Klarheit her die explizit rekursive Variante gewinnt:

Code: Alles auswählen

ggt a 0 = a
ggt a b = ggt b (a `mod` b)

ggt' a b = let f (x, y) = (y, x `mod` y) in
    fst . head . dropWhile (\z -> snd z /= 0) $ iterate f (a, b)

Wobei die kürzeste Variante wohl noch das hier sein dürfte:

Code: Alles auswählen

ggt = gcd

[BlackMamba]

@ BlackJack:
>> fst . head . dropWhile (\z -> snd z /= 0) $ iterate f (a, b)

Ist das so eine Art Listenbeschreibung, wie man sie auch in Haskell verwendet?
Kann man dann z.B. die folgende Permutationsfunktion auch in Python generieren? Um z.B. den Algorithmus für den TSP zu programieren?

Code: Alles auswählen

permut :: [Stadt] -> [[Stadt]]
permut [] = [[]]
permut (xs) = [ y:ys | y <- xs , ys <- permut (remove y xs) ]
-- Permutation

[BlackJack]

Hallo! Das ist alles *Haskell* in meinem letzten Beitrag. Ich denke Du kennst die Sprache!? `ggt'` verwendet nur Funktionen aus der `Prelude`. Und dort ist auch `gcd` schon definiert ─ "greatest common divisior", also "ggt" auf englisch.

`permut` lässt sich selbstverständlich auch in Python realisieren, aber das würde man so nicht machen. Haskell ist eine "lazy" Sprache, d.h. es wird von Listen immer nur so viel ausgewertet, wie auch zu Berechnungen an anderer Stelle gebraucht wird. Die Haskell-Funktion erstellt also nicht alle möglichen Listen auf einmal. Das würde nämlich eine Menge Speicher verbrauchen, obwohl man in dem TSP-Algorithmus nie alle Listen auf einmal betrachtet, sondern immer eine nach der anderen. In Python würde man deshalb dafür eher eine Generator-Funktion schreiben, also explizit "lazy" arbeiten.

[BlackMamba]

ups.....peinlich, klar ist das Haskell Code.....da war ich heute morgen wohl noch nicht ganz wach.... Entschuldigung!

Aber wie könnte man denn so eine Generatorfunktion schreiben? Gibts da Tutorials oder ähnliches zu?

Danke für die Hilfe!

[noise]

Aber wie könnte man denn so eine Generatorfunktion schreiben? Gibts da Tutorials oder ähnliches zu?

Hi ich kenne mich mit Haskell nicht aus und kann daher deine definition von ``permut `` nicht lesen, aber zu Generatoren in Python kann ich was sagen.

Ein generator wird ganz einfach so definiert:

Code: Alles auswählen

>>> def gen(iterable):
	for elem in iterable:
		yield elem

		
>>> li = [1,2,3,4,5]
>>> gen(li)
<generator object at 0x00E8C9E0>
>>> it = gen(li)
>>> it.next()
1
>>> it.next()
2
>>> it = gen((1,2))
>>> it.next()
1
>>> it.next()
2
>>> it.next()

Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
    it.next()
StopIteration
>>> for elem in gen(li):
	print elem

	
1
2
3
4
5
>>> 

Wie man sieht ist das entscheidende das `yield`. mit `next()` yielded man bei bedarf das nächste Element.

Zum Thema Generatoren hier ein bisschen lesestof:
http://www.python.org/dev/peps/pep-0255/
http://www.python.org/dev/peps/pep-0289/
http://www.python.org/dev/peps/pep-0342/
http://docs.python.org/whatsnew/pep-342.html

Ich muss gestehen ich bin ein großer Fan von Pythons Generatoren und benutze sie überall wo es nur geht. Seit 2.5 kann man mit den Generatoren auch "coroutines" schreiben, mit `send()`, `throw()` und `close()`.

HTH
noise

[audax]

Was gefällt dir denn an Haskell nicht? Ich bin gerade dabei, Haskell zu lernen und finds eigentlich ziemlich genial, wenn auch sehr ungewohnt.

Allerdings programmiere ich auch in Python meist recht funktional...nur halte ich mich da mit Rekursion zurück

[BlackMamba]

@ audax:
Haskell an sich ist ja ganz ok...besonders weil man zum Beispiel viele mathematische Formeln quasie direkt in Haskell übernehmen kann.
Aber an der Uni macht das kein Spaß.
Kann dir ja gerne mal den Link mit den Übungsaufgaben und Unterlagen geben, aber Musikstücke zu programmieren mit Haskell, machen vielen von uns nicht ganz so viel Spaß...
Und was noch dazukommt, man braucht Haskell nie wieder. Vor drei Wochen hatten wir die letzte Vorlesung für Haskell, wir werden die Sprache das ganze Studium nie wieder gebrauchen und später glaube ich auch nicht.

[BlackMamba]

@ noise:

Danke für den Quellcode und die Links, muss ich mir heute nachmittag mal alles in Ruhe anschauen und ausprobieren.

[BlackJack]

Ich habe die `permut` mal 1:1 nach Python übersetzt. Dazu muss man im Quelltext von BlackMamba noch `Stadt` und `remove` definieren:

Code: Alles auswählen

import List
type Stadt = String

remove :: Stadt -> [Stadt] -> [Stadt]
remove y xs = xs \\ [y]

permut :: [Stadt] -> [[Stadt]]
permut [] = [[]]
permut xs = [ y:ys | y <- xs , ys <- permut (remove y xs) ]

main = putStrLn . unlines . map show $ permut ["Berlin", "Tokyo", "New York"]

In Python nahezu 1:1 "übersetzt" sieht das so aus:

Code: Alles auswählen

from pprint import pprint


def remove(y, xs):
    result = list(xs)
    result.remove(y)
    return result


def permut(xs):
    if not xs:
        return [[]]
    else:
        #      [ y  : ys |   y <- xs ,   ys <- permut (remove y xs) ]
        return [[y] + ys for y in xs for ys in permut(remove(y, xs))]


pprint(permut(['Berlin', 'Tokyo', 'New York']))