NG Programmiersprache?

volkard schrieb:

10 a=1:b=1
20 a=a+b:print a
30 b=b+a:print b
40 goto 20

back to basic

Nexus

Mr. N schrieb:

Die iterative Version von dir besitzt durchaus eine beachtliche Komplexität. Man muss schon nachdenken, was das macht. Genauso wie bei der Version mit zipWith. Natürlich ist für dich die iterative Version einfacher, weil du es seit Jahren übst, auf iterative Algorithmen zu starren, und sie zu entziffern. Bei den funktionalen Pendants fehlt dir da einfach die Übung.

Dass man mit funktionalen Programmiersprachen gewisse Anweisungen sehr elegant und kompakt ausdrücken kann, bestreite ich gar nicht. Das ist ja auch etwas, was mir an Haskell so gefällt. Allerdings erfordert dieser Weg einige Abstraktion, zum Beispiel viel mehr als eine Schleife. Oder zumindest eine andere Art von Abstraktion, von der ich behaupte, dass sie am Anfang weniger naheliegend und intuitiv ist.

Nimm zum Beispiel Pseudocode: Er dient dazu, unabhängig von der Programmiersprache Abläufe und Algorithmen zu beschreiben. Und er besitzt oft die Form eines iterativen Rezepts wie bei der Schleife hier, je nach Problem auch einer einfachen Rekursionsvorschrift. Aber sowas Ähnliches wie zipWith findet man nirgends, weil High-Order-Functions eher schwierig zu verstehen sind. Hingegen ist ein

f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1

auch für Leute verständlich, die gar nicht programmieren können.

Ironisch ist doch, dass sowohl C++ als auch Haskell die Fibonacci-Berechnung so formulieren könnten. Aber in Haskell nimmt man aus Performancegründen zipWith und tail , und in C++ nimmt man aus Performancegründen for .

volkard

Nexus schrieb:

Aber in Haskell nimmt man aus Performancegründen zipWith und tail , und in C++ nimmt man aus Performancegründen for .

Man staunt, was sich die Haskell-Leute so basteln, um auf O(n) Zeit zu kommen.

fib 0 = 0
fib 1 = 1
fib n | even n         = f1 * (f1 + 2 * f2)
      | n `mod` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2
      | otherwise      = (2 * f1 + f2) * (2 * f1 - f2) - 2
   where k = n `div` 2
         f1 = fib k
         f2 = fib (k-1)

oder

fibs = scanl (+) 0 (1:fibs)
fibs = 0 : scanl (+) 1 fibs

oder

fibs = fix (scanl (+) 0 . (1:))
fibs = fix ((0:) . scanl (+) 1)

oder

fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

oder

fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

oder

import Control.Monad.State
fib :: Integer -> Integer
fib n = flip evalState (0,1) $ do
  forM (xrange n) $ \_ -> do
    (a,b) <- get
    put (b,a+b)
  (a,b) <- get
  return a 

xrange n = [0..(n-1)]

Da läuft doch was schief! Wobei ich nicht behaupten will, bei C++ liefe nicht auch was schief.

Mr. N

fib n = fib' n     0       1 1
  where fib' total current a _ | total == current = a
        fib' total current a b                    = fib' total (current + 1) b (a + b)

Um die iterative Version mal klassisch und ohne Control.Monad.State in die tail-rekursive Form zu übersetzen.

Und wieso ist es nun ein Problem, dass man in Haskell mehrere Lösungen für ein Problem finden kann?

Wenn bei Haskell und C++ "etwas schief läuft", wo läuft es dann nicht schief?

Mr. N

Und weils so schön ist, zipWith in C++:

using std::vector;
using boost::result_of;

template<typename F, typename T1, typename T2>
vector<typename result_of<F(T1,T2)>::type>
zipWith(F f, vector<T1> const &a, vector<T2> const &b) {
  vector<typename result_of<F(T1,T2)>::type> res;
  vector<T1>::const_iterator itA = a.begin();
  vector<T2>::const_iterator itB = b.begin();
  for (; itA != a.end() && itB != b.end(); ++itA, ++itB)
    res.push_back(f(*itA, *itB));
  return res;
}

knivil

Mr. N schrieb:

(define (sum xs) (fold-left + 0 xs))

In Scheme bzw. Srfi-1 gibt es nur fold und entspricht deinem fold-left.

volkard schrieb:

Ich bevorzuge da Sachen, die weniger abstrakt als Rekursion sind.
summe=0
foreach i in xs
  summe+=i

Und schwubs hat man vergessen die Summe zu initialisieren. Diese Variante hat aber auch weitere Nachteile. Kannst du allein mit diesen Zeilen beweisen, dass es das gleiche wie ist

(as,bs) = split xs
summe1=0
foreach i in as
  summe1 += i

summe2=0
foreach i in bs
  summe2 += i

summe = summe1 + summe2

Wahrscheinlich, da es ein einfacher Fall ist. (Dieses Beispiel zielt auf Parallelitaet ab).

Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

Man kann sie auch herleiten, siehe Funktionale Programmierung.: Sprachdesign und Programmiertechnik. Auch sind die expliziten Zuweisungen in der C-Variante ueberfluessig.

Ich find die Version, die Volkard gepostet habe, am leichtesten

Auch nur weil du damit gross geworden bist.

fibi = let next n m = (n+m) : (next m (n+m)) in 0:1:(next 0 1)

Meine bevorzugte Variant, da es unfold nicht direkt gibt, bzw. mit diesem unschoenen Maybe dazwischen. Nachteilhaft ist die explizite Rekursion. Sie ist die iterate-Variante.

Zeus

knivil schrieb:

Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

Man kann sie auch herleiten, siehe Funktionale Programmierung.: Sprachdesign und Programmiertechnik. Auch sind die expliziten Zuweisungen in der C-Variante ueberfluessig.

Hab ich das nicht getan?

knivil schrieb:

Ich find die Version, die Volkard gepostet habe, am leichtesten

Auch nur weil du damit gross geworden bist.

Ich bin mit imperativen Programmiersprachen groß geworden und finde Volker's Rekursive Definition am besten! Was willst du mir mit dein Kommentar sagen, dass du mich nicht verstanden hast? Ich weiss es nicht!!

otze

Zeus schrieb:

Ich bin mit imperativen Programmiersprachen groß geworden und finde Volker's Rekursive Definition am besten! Was willst du mir mit dein Kommentar sagen, dass du mich nicht verstanden hast? Ich weiss es nicht!!

Er meinte etwas wie: Es ist natürlich, dass du etwas besser findest, woran du dich dein ganzes Programmiererleben gewöhnt hast.

Man hat das früher auch anders ausgedrückt: Was der Bauer nicht kennt, frisst er nicht.

Zeus

Dann bin ich halt ein Bauer der Sich nach etwas anderem sehnt als, dass was er anbaut. Klargestellt?!

knivil

Hab ich das nicht getan?

Du hast es dir ueberlegt, wahrscheinlich durch etwas probieren und so, wohl aber nicht formal. Ok: das ist eine Unterstellung, aber wahrscheinlich trifft sie zu.

Mr. N

knivil schrieb:

Mr. N schrieb:
(define (sum xs) (fold-left + 0 xs))
In Scheme bzw. Srfi-1 gibt es nur fold und entspricht deinem fold-left.

Natürlich gibt es fold-left. In R6RS.

http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-4.html

Ich habe sogar einen Interpreter gefunden, der das unterstützt.

knivil

Ok, ich bezog mich auf R5RS.

Mr. N schrieb:

hehe schrieb:

Da nehme ich dann doch lieber eine for-schleife.

Dann zeig deine Künste.

Jetzt stehts zwar schon da, aber das hatte ich, noch vor meinem ersten Beitrag, nachdem ich mir das http://de.wikipedia.org/wiki/Fibonacci-Folge angeschaut hatte, in 5 Minuten hingeschmiert, um zu prüfen, ob man das nicht mit ner for-schleife hin bekommt.

int fib( int n )
{
	int a = 0;
	int b = 1;
	for(int i = 0;i<n;i++ )
	{
		a=a+b;
		int t=b;
		b=a;
		a=t;
	}
	return a;
}

Zeus schrieb:

http://stackoverflow.com/questions/1518726/recursive-fibonacci
int fib(int n)
{
    int a = 1, b = 1;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }           
    return b;
}
Auf die iterative Version bin ich nur darauf gekommen, weil ich es in Tabellenform auf Papier gebracht habe.

Ok, meine Lösung ist doch anders. Meine gibt für fib(0) auch 0 aus. So wie es auf Wikipedia steht.

*john 0

thatway schrieb:

Wer greift da wen persönlich an?

Du solltest dringend lernen zwischen fachlicher und persönlicher Kritik zu unterscheiden. Denn bisher hast Du noch nicht einmal ansatzweise erkennen lassen, daß Du die verschiedene Argumente pro und contra MI kennen würdest, die sich wie ein roter Pfaden durch die OO-Literatur zieht. Kritik in diesem Punkt an Dir ist also vollkommen berechtigt, denn bisher hast Du nur die Empfehlung möglichst keine MI in C++ zu verwenden monoton heruntergebetet. Aus Deinen Äußerungen hier im Forum kann man jedenfalls nicht schließen, daß Du Dich jemals mit dem Thema tiefer auseinandergesetzt hättest.

Das Buch von Stroustrup zeigt sehr deutlich weshalb es sinnvoll ist MI in C++ zu haben, es kostet faktisch nichts, und in wenigen Fällen erleichtert sie einem enorm das Leben. Daher sehe ich MI als notwendig für eine zukünftige Programmiersprache an, es kostet faktisch nichts, aber in bestimmten Fällen vereinfacht MI das Design einer Klassenbibliothek.

Phoemuex

Die schönste Lösung ist doch sowieso das Folgende

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
    double const wurzelFuenf = sqrt(5.0);
    double const phi = (1.0 + wurzelFuenf)/2.0;
    double phiHochN = 1;
    for(int N = 0; N < 20; ++N)
    {
        cout << "f_" << N << ": " << static_cast<int>(phiHochN/wurzelFuenf + 0.5) << endl;
        phiHochN *= phi;
    }
}

volkard

Phoemuex schrieb:

Die schönste Lösung ist doch sowieso das Folgende

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
    double const wurzelFuenf = sqrt(5.0);
    double const phi = (1.0 + wurzelFuenf)/2.0;
    double phiHochN = 1;
    for(int N = 0; N < 20; ++N)
    {
        cout << "f_" << N << ": " << static_cast<int>(phiHochN/wurzelFuenf + 0.5) << endl;
        phiHochN *= phi;
    }
}

wurzelFuenf ist schlechter zu lesen als sqrt(5) und damit eine böse Auslagerung. Achso, wegen Performance, weil Du die zahl zweimal brauchst. Aber die Potenzierschleife statt pow ist böse UND riecht langsam.
Wobei ich mich schon immer frage, ab welchen Zahlen die geschlossene Formel schneller als die paar Integer-Additionen ist.

~john schrieb:

thatway schrieb:

Wer greift da wen persönlich an?

Du solltest dringend lernen zwischen fachlicher und persönlicher Kritik zu unterscheiden. Denn bisher hast Du noch nicht einmal ansatzweise erkennen lassen, daß Du die verschiedene Argumente pro und contra MI kennen würdest, die sich wie ein roter Pfaden durch die OO-Literatur zieht. Kritik in diesem Punkt an Dir ist also vollkommen berechtigt, denn bisher hast Du nur die Empfehlung möglichst keine MI in C++ zu verwenden monoton heruntergebetet. Aus Deinen Äußerungen hier im Forum kann man jedenfalls nicht schließen, daß Du Dich jemals mit dem Thema tiefer auseinandergesetzt hättest.

Das Buch von Stroustrup zeigt sehr deutlich weshalb es sinnvoll ist MI in C++ zu haben, es kostet faktisch nichts, und in wenigen Fällen erleichtert sie einem enorm das Leben. Daher sehe ich MI als notwendig für eine zukünftige Programmiersprache an, es kostet faktisch nichts, aber in bestimmten Fällen vereinfacht MI das Design einer Klassenbibliothek.

Wenn Du dein Wissen aus 15 Jahren alten Büchern beziehst und nicht weißt wie man was richtig entwirft, mach dafür nicht Deine Mitmenschen verantwortlich. Es gibt mittlerweile eine reichhaltige Entwurfsmusterliteratur, die ohne MI auskommt, darin kannst Du solche Grundlagen nachlesen.

So das war jetzt fachliche Kritik (nach deiner Definition).

Nexus

thatway schrieb:

Es gibt mittlerweile eine reichhaltige Entwurfsmusterliteratur, die ohne MI auskommt, darin kannst Du solche Grundlagen nachlesen.

Okay, dann einigen wir uns darauf, dass man Mehrfachvererbung einfach nicht braucht. Templates, Operatorüberladung, Const-Correctness oder freie Funktionen braucht man ja auch nicht, siehe Java.

Nexus schrieb:

Okay, dann einigen wir uns darauf, dass man Mehrfachvererbung einfach nicht braucht. Templates, Operatorüberladung, Const-Correctness oder freie Funktionen braucht man ja auch nicht, siehe Java.

Totschlag
http://de.wikipedia.org/wiki/Strohmann-Argument