Lernen Haskell Karten, Falten, Schleifen und Rekursion

Question

Ich habe gerade meinen Zeh in die Welt von Haskell getaucht, als Teil meiner Reise der Programmierung der Erleuchtung (von prozedural zu OOP weitergehend zu jetzt funktionierend).

Ich habe versucht, eine Online Haskell Evaluator.

Allerdings bin ich jetzt auf einem Problem nicht:

eine einfache Funktion erstellen, die die Gesamtsumme einer Reihe von Zahlen gibt.

In einer prozeduralen Sprache diesen für mich ist leicht genug, um (unter Verwendung von Rekursion) (C#):

private int sum(ArrayList x, int i) 
{ 
    if (!(x.Count < i + 1)) { 
     int t = 0; 

     t = x.Item(i); 
     t = sum(x, i + 1) + t; 
     return t; 
    } 
} 

Alles sehr fein aber bei Haskell meines gescheiterten Versuch war so:

let sum x = x+sum in map sum [1..10] 

diese führte zu dem folgenden Fehler (von der oben genannten Website):

Occurs check: cannot construct the infinite type: a = a -> t 

Bitte beachten Sie, dass ich Haskell nur für die letzten 30 Minuten verwendet habe!

Ich suche nicht einfach nach einer Antwort, sondern eine Erklärung dafür.

Answer 1

Ich suche nicht einfach auf eine Antwort, sondern ein mehr Erklärung davon.

Auf der linken Seite des = Sie verwenden sum als Funktion x angewendet. Der Compiler kennt den Typ x nicht, daher verwendet der Compiler die Typenvariable a für "den Typ x". An diesem Punkt kennt der Compiler den Ergebnistyp der Funktion sum weder, noch wählt er eine andere Typvariable, diesen Typ t, für den Ergebnistyp aus. Jetzt auf der linken Seite denkt der Compiler, dass der Typ von x 10 ist (Funktion, die a akzeptiert und t zurückgibt).

Auf der rechten Seite des = fügen Sie x und sum hinzu. In Haskell können alle Arten von Zahlen hinzugefügt werden, aber Sie können zwei Zahlen nur hinzufügen, wenn sie den selben Typ haben. Daher nimmt der Compiler hier an, dass sum den gleichen Typ wie x hat, nämlich Typ a.

Aber in Haskell hat eine Kennung einen Typ — vielleicht ein wangdilly komplizierter Typ, aber ein Typ dennoch. Dazu gehören sum, deren Typ sollte gleich auf beiden Seiten des `Zeichen dafür sein, so dass der Compiler versucht, die Gleichung zu lösen

a = a -> t 

Es sind keine Werte für a und t, die diese Gleichung zu lösen. Es ist einfach nicht möglich. Es gibt keine a, so dass a einer Funktion entspricht, die sich selbst als Argument akzeptiert. So entsteht die Fehlermeldung

Selbst mit all der Erklärung ist es nicht so eine große Fehlermeldung, oder?

Willkommen in Haskell :-)

---

P. S. Vielleicht möchten Sie "Helium, um Haskell zu lernen" ausprobieren, was für Anfänger viel bessere Fehlermeldungen liefert.

Answer 2

'sum' nimmt eine Liste von Werten und reduziert sie auf einen einzelnen Wert. Sie können es entweder als explizite Schleife schreiben (denken Sie daran, dass Haskell keine Loop-Schlüsselwörter hat, aber Rekursion verwendet). Beachten Sie, wie die Definition aus zwei Teilen, basierend auf der Form der Liste:

mysum []  = 0 
mysum (x:xs) = x + mysum xs 

Oder effiziente, in einem tail-recursive Stil:

mysum xs = go 0 xs 
    where 
     go n []  = n 
     go n (x:xs) = go (n+x) xs 

Allerdings hat Haskell eine umfangreiche Bibliothek von Steuerstrukturen, die Arbeiten Sie auf faulen Listen. In diesem Fall kann Reduktion einer Liste auf einen einzelnen Wert mit einer Reduce-Funktion erfolgen: a fold.

So kann mySum geschrieben werden als:

mysum xs = foldr (+) 0 xs 

Zum Beispiel:

Prelude> foldr (+) 0 [1..10] 
55 

Ihre Fehler ein Karte zu verwenden war, die eine Liste verwandelt, ein Element zu einem Zeitpunkt, eher als ein falten.

Ich würde vorschlagen, Sie beginnen mit einer Einführung in Haskell, vielleicht "Programming in Haskell", um ein Gefühl für die Kernkonzepte der funktionalen Programmierung zu bekommen. Andere gute einführende Materialien sind beschrieben in this question.

Answer 3

Sie müssen ein gutes Tutorial lesen, es gibt eine Reihe von großen Missverständnissen.

Zuerst werde ich davon ausgehen, dass Sie Listen und nicht Arrays bedeuten. Arrays gibt es in Haskell, aber sie sind nicht auf Anfängerniveau. (Ganz zu schweigen von der Verwendung von [1..10], also einer Liste der Zahlen 1 bis 10).

Die gewünschte Funktion in tatsächlich gebaut wird, und die Summe genannt, so dass wir sonst unsere etwas nennen müssen, new_sum:

new_sum [] = 0 
new_sum (h:t) = h + (sum t) 

Answer 4

Blick Lassen Sie sich auf dem ersten Teil davon:

let sum x = x+sum 

Was wäre die Art der Summe in diesem Fall? Es nimmt eine Zahl und gibt eine Funktion zurück, die eine Zahl zurückgibt, die eine Funktion zurückgibt, die eine Zahl usw. nimmt, wenn Sie es geschrieben hätten let sum x = + x Sie hätten eine Funktion, die eine Zahl nimmt und die Funktion + x zurückgibt . und let Summe = + würde eine Funktion zurückgeben, die zwei ganze Zahlen dauert und fügt sie hinzu.

so jetzt schauen wir uns den zweiten Teil an. in map sum [1..10] Karte nimmt eine Funktion von einem Argument und wendet es auf jedes Element der Liste an.Da ist kein Platz, um einen Akkumulator einzukeilen, also schauen wir uns andere Listenfunktionen an, besonders foldl, foldr. beide nehmen eine Funktion von zwei Argumenten eine Liste und einen Anfangswert. Der Unterschied zwischen foldl und foldr ist auf der Seite, in der sie beginnen. l gelassen werden so 1 + 2 + 3 usw. und r rechts 10 + 9 + 8 usw.

let Summe = (+) in foldl Summe 0 [1..10]