Funktionale Programmierung mit Haskell

minhen

knivil schrieb:

Die Mathematik hat mich eines besseren belehrt. Kreativitaet laesst sich schwer prozedural ausdruecken (und waere dann wohl nicht mehr als Kreativitaet zu betrachten).

Was verstehst du unter Kreativität und wieso ist dies mit Rekursion, nicht aber prozedural möglich? Kann es sein, dass Kreativität für dich etwas ist, was nicht explizit ausbuchstabiert dort stehen darf, sondern implizite Schritte umfassen muss, die nur immateriell im Geiste herumschweben dürfen? Bei einem solchen Verständnis wäre Rekursion natürlich kreativer. Wie gesagt, Rekursion befindet sich eine Abstraktionsstufe höher. Doch mein Verständnis von Kreativität ist das nicht.

knivil

Irgendwie gehts langsam am Thema vorbei: Funktionale Programmierung vs. Prozedurale. Rekursion kann ich auch mit Prozeduren machen. Es ging um Prozeduren als natuerlicher Ansatz um Probleme zu loesen. Damit kann man aber manchmal schwerlich Problemloesungsstrategien entwickeln. Aussderm habe ich nie behauptet, dass Kreativitaet irgendwas mit Rekursion zu tun haette.

minhen

Natürlich geht Rekursion auch prozedural, das ist jedem hier klar. (Zumindest habe ich es hier schon mehrfach geschrieben.) Worauf die Dichotomie also eigentlich hinaus wollte, sollte eigentlich klar sein.

Hast du denn ein Beispiel, wo man das Problem rekursiv anpacken muss? Meine Behauptung ist, dass man die Probleme zunächst rein sequentiell ohne Rekursion durchdenkt. Und dass Rekursion eben ein Endprodukt ist. Das, wenn man es beherrscht, natürlich auch einfach zu handhaben ist und auch nicht schwerer nachvollziehbar ist. Rekursion bleibt dabei aber ein Endprodukt. Bei der Suche nach einer Lösung eines Problems fängt man sequentiell an. Meine Behauptung. Wo ist das nicht so? Mir fällt das ehrlich gesagt schwer vorzustellen. Wie soll man eine Lösung finden, ohne dass man erst die Einzelfälle durchdenkt? Man muss ja nicht alle durchdenken. Doch auch wenn ich die ersten x Fälle durchdenke und dann sage "aha, das ist ja rekursiv lösbar!" habe ich sequentiell angefangen.

knivil

habe ich sequentiell angefangen

Probieren ist immer sequentiell, damit kann man alles erschlagen. Aber man hat nur angefangen ...

aha, das ist ja

Genau hier faengt Kreativitaet an, das ist nicht mehr sequentiell oder prozedural.

eigentlich hinaus wollte, sollte eigentlich klar sein.

Mir ist es nicht klar. Aber das trifft sich gut, du scheinst mich auch nicht zu verstehen.

Jester

minhen schrieb:

Hast du denn ein Beispiel, wo man das Problem rekursiv anpacken muss? Meine Behauptung ist, dass man die Probleme zunächst rein sequentiell ohne Rekursion durchdenkt.

Ein Beispiel, das man rekursiv anpacken *muss* wird er wohl kaum haben. Immerhin lässt sich jedes Problem, das sich rekursiv lösen lässt auch iterativ lösen.

Allerdings ist es manchmal tatsächlich einfacher etwas rekursiv zu lösen, als iterativ. Ich würde zum Beispiel wetten, dass jemand, der über schnelle Berechnung von Potenzen nachdenkt zuerst ein rekursive Sqare-and-Multiply auf dem Blatt stehen hat und erst einige Zeit später die iterative Implementierung hingeschrieben hat (die für ne Sprache wie C++ effizienter sein sollte). Insofern sehe ich Rekursion nicht zwingend als das Endprodukt an.

Tatsächlich habe ich manchmal ne Menge Arbeit damit, rekursive Algorithmen so umzuformulieren, dass sie sich halbwegs vernünftig implementieren lassen.

mazal

Rekursion kommt häufig vor und ist oftmals die "natürlichste" Herangehensweise an ein Problem, da man es Recht häufig mit rekursiven Strukturen zu tun hat: Grammatiken, Dateisystemen, Bäumen etc.

mazal schrieb:

Rekursion kommt häufig vor ...

wie in dem lied 'ein mops kam in die küche...'

knivil

Oder: http://99-bottles-of-beer.net/ . Hier mal die Variante in Scheme (wenn man etwas mit quotes rumspielt, geht es vielleicht auch kuerzer, auch die Mapidee von Haskell kann man uebernehmen):

;;; Tim Goodwin (tim@pipex.net)

(define bottles
  (lambda (n)
    (cond ((= n 0) (display "No more bottles"))
          ((= n 1) (display "One bottle"))
          (else (display n) (display " bottles")))
    (display " of beer")))

(define beer
  (lambda (n)
    (if (> n 0)
        (begin
          (bottles n) (display " on the wall") (newline)
          (bottles n) (newline)
          (display "Take one down, pass it around") (newline)
          (bottles (- n 1)) (display " on the wall") (newline)
          (newline)
          (beer (- n 1))))))

(beer 99)

knivil schrieb:

Oder: http://99-bottles-of-beer.net/ . Hier mal die Variante in Scheme...

die BASIC-version von der seite da^^ finde ich besser. die ist dazu noch iterativ.

frosch03

Also wenn ich mal aus meiner Haskellerfahrung berichten darf.
Oft geht man da noch einen Schritt weiter, und versucht von der Rekursion zu abstrahieren indem
man Funktionen höherer Ordnung verwendet (z.B. fold). Damit bin ich dann nicht mehr iterativ, und hab mich auch nicht explizit um die Rekursion gekümmert.

Keine Ahnung wie es euch geht, aber um den Turm von Hanoi zu lösen fällt mir grad nur die rekursive Lösung ein. Kann es sein, dass diese hier auch deutlich einfacher ist als die Iterative mittels Schleife?

Jester

frosch03 schrieb:

Keine Ahnung wie es euch geht, aber um den Turm von Hanoi zu lösen fällt mir grad nur die rekursive Lösung ein. Kann es sein, dass diese hier auch deutlich einfacher ist als die Iterative mittels Schleife?

volkard vor einigen Jahren schrieb:

//zielRichtung ist die richtung vom startturm zum zielturm
if(istUngeradeGerade(anzahlDerTürme))
 richtung:=zielRichtung
else
 richtung:=dieAndereRichtung(zielRichtung)
zieh die kleine scheibe zykisch nach richtung
solange nicht fertig
 zieh den einzig möglichen zug, der nicht die kleine scheibe benutzt
 zieh den kleinsten zykisch nach richtung

sieht auch nicht so richtig schwierig aus.

knivil schrieb:

Oder: ... Hier mal die Variante in Scheme...

die APL vers. 2 ist aber auch interessant

wobei ich natürlich nicht die scheme- mit der APL-vers. 2 vergleichen will, da liegen hinsichtlich Lesbarkeit ja Welten dazwischen :p

frosch03 schrieb:

Aber im Ernst jetzt, was erwartest du denn. Selbst wenn ich dir jetzt eine Bildschirmseite voller Links gebe um dich zu beeindrucken, nutzt dir das doch recht wenig. Denn woher weißt du, ob da überhaupt etwas sinnvolles drin steht? Oder währ dir das egal? So oder so, wenn du wirklich Quellen hinterfragen willst, kommst du ums lesen derselben nicht drum rum.

Mich interessieren keine Seiten von Links, sondern präzise eine oder zwei Quellen. Und unter Quelle verstehe ich kein ganze Zeitschriften Serie. Das ist so, als würde ich eine Behauptung aufstellen und dir dann 3 Bücher a 600 Seiten in die Hand drücken und sagen, dass dort drin die Begründung zu meiner Behauptung drin steht.

minhen schrieb:

Was verstehst du unter Kreativität und wieso ist dies mit Rekursion, nicht aber prozedural möglich? Kann es sein, dass Kreativität für dich etwas ist, was nicht explizit ausbuchstabiert dort stehen darf, sondern implizite Schritte umfassen muss, die nur immateriell im Geiste herumschweben dürfen? Bei einem solchen Verständnis wäre Rekursion natürlich kreativer. Wie gesagt, Rekursion befindet sich eine Abstraktionsstufe höher. Doch mein Verständnis von Kreativität ist das nicht.

Wo wir bei Mathematik sind. Denke doch einfach mal an die ganzen Induktions-Beweise, die es gibt. Ich wünsche viel Spaß beim finden eines direkten Beweises.

u_ser-l schrieb:

also gut, zugegeben, Haskell hat schon was. Auch wenn es auf den ersten Blick ein wenig nach Hieroglyphen einer außerirdischen Intelligenz aussieht

Grundsätzlich: weshalb sollte man Haskell nehmen und nicht Scheme oder eine Sprache aus der ML-Reihe, zB SML oder OCaML ??

Weil Haskell eine reine funktionale Sprache ist. Das Bedeutet, dass wenn du Haskell benutzen kannst, dann hast du auch funktionale Programmierung verstanden. Nimmst du etwas wie ML, welches auch prozedurale Programmierung unterstützt, dann programmierst du am Ende unter Umständen nur prozedural mit einer anderen Syntax.

Also wenn du Haskell verstanden hast, dann hast du funktionale Programmierung verstanden. Das sollte dich dazu befähigen so gut, wie jede andere funktionale Programmiersprache zu verwenden und dann nur ein wenig Syntax und noch ein paar Feinheiten zu lernen.

Was man dann am Ende einsetzt, halte ich dann für nebensächlich.

Noch bezüglich Real-World Anwendungen von funktionaler Programmierung. Erlang ist für Webserver in letzter Zeit recht beliebt geworden. Und wird wohl auch von eigen großen Firmen eingesetzt.

Jetzt habe ich schon das halbe (übrigens toll geschriebene) "Learn you a Haskell ..."-Tutorial durchgelesen ... und Ihr seid daran schuld

frosch03

ProgChild schrieb:

sondern präzise eine oder zwei Quellen.

Alles klar. Wenn dir jetzt mal meinen Post anschaust, dann hab ich dir da ganz Präzise eine Quelle genannt, nämlich: "Runtime Support for Multicore Haskell" [1] und wenn du das so in Google eingibst, bekommst du sofort den link aufs pdf. Gut, vielleicht hast du das übersehen oder dir fehlte der link aufs pdf, den geb ich dir natürlich gerne Genial sind auch die drei "Scrap your boilerplate" paper [2]. So und jetzt aber genuch, den Rest darfst'e dir selber ergoogeln

Bzgl. Erlang: ich weiß ja nicht ob ihr Jabber einsetzt, aber DER jabberserver (ejabberd) ist in Erlang geschrieben, und der rockt auch mal

@u_ser-l: An sowas ist man gerne Schuld

[1] http://www.haskell.org/~simonmar/papers/multicore-ghc.pdf
[2] http://research.microsoft.com/en-us/um/people/simonpj/papers/hmap/gmap3.pdf

knivil

Jester schrieb:

frosch03 schrieb:

Keine Ahnung wie es euch geht, aber um den Turm von Hanoi zu lösen fällt mir grad nur die rekursive Lösung ein. Kann es sein, dass diese hier auch deutlich einfacher ist als die Iterative mittels Schleife?

volkard vor einigen Jahren schrieb:
//zielRichtung ist die richtung vom startturm zum zielturm
...
sieht auch nicht so richtig schwierig aus.

Die genannte Umsetzung glaube ich erst, wenn ich das funktionierende Programm sehe. Habe mal eine iterativer Version in Scheme gesehen, die sah wesentlich komplizierter aus, hat aber funktioniert. Leider lernt man aus der Iterativen nicht viel, das sie halt ... kompliziert ist. Die rekursive Variante ist um einiges eleganter.

Zu higher order functions: ich meinte ja, dass z.B. map ausnutzen kann. In Scheme gibt es auch fold-left / fold-right etc. aber diese sind halt rekursiv implementiert. (wobei iterativ und rekusiv in Scheme gleich aussehen, man spricht aber von iterativ, wenn der Stack (Expansion) beschraenkt und unabhaengig von der Eingabe ist O(1)). Die gepostete Scheme-Version von 99 Bottles of Beer ist iterativ.

volkard

knivil schrieb:

Die genannte Umsetzung glaube ich erst, wenn ich das funktionierende Programm sehe.

nimmst du mal vorlieb mit
http://www.mah-jongg.ch/towerofhanoi/
und probierst als mensch das verfahren.
wirst sehen, daß es für den menschen sogar viel netter ist als die rekursive.

und es ist auch möglich, das zu programmieren. das verfahren ist nur das argument dagegen, daß man das rekursiv programmieren MÜSSE.

Habe mal eine iterativer Version in Scheme gesehen, die sah wesentlich komplizierter aus, hat aber funktioniert.

mit dem berechnen der höhen für die grafik ists iterativ nicht ganz so einfach, als wie wenn man die rekursiv mitschickt. aber die zugfolge ist iterativ nachgerade triv.