Quelqu'un pourrait-il expliquer ces fonctions Haskell me?

Question

J'ai tâté avec Haskell dans le passé, et a récemment obtenu de nouveau dans sérieux, et je lis monde réel haskell. Certains des exemples qu'ils ont brillé, je n'ai pas encore à comprendre. Telle est celui-ci:

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

Je ne vois pas comment cela fonctionne, ce qui est vraiment 1 être ajouté aussi? Comment quelque chose récursion de retour qui peut être ajouté à? Je ne comprends pas.

Et nous avons celui-ci:

splitLines [] = []
splitLines cs =
       let (pre, suf) = break isLineTerminator cs
       in  pre : case suf of 
                   ('\r':'\n':rest) -> splitLines rest
                   ('\r':rest)      -> splitLines rest
                   ('\n':rest)      -> splitLines rest
                   _                -> []

isLineTerminator c = c == '\r' || c == '\n'

Comment ce travail, ce qui est pré vraiment être attaché aussi? Je ne vois pas comment le résultat de l'expression de cas est quelque chose qui peut être pré concaténer. Peut-être que j'ai juste besoin de quelqu'un pour expliquer l'évaluation de ces fonctions dans les détails. Je dois manquer quelque chose très important.

Merci d'avance!

EDIT: Je sais, ce fut un copier-coller échouez. Désolé.

EDIT 2: Il semble ma confusion était avec ce que ces fonctions étaient en fait / retour / je l'ai travaillé tout maintenant. Merci pour les réponses les gars, il a finalement cliqué! Je l'apprécie!

Answer 1

En ce qui concerne le premier, il est un moyen très simple de récursivité. Cependant, il semble manquer une partie:

myLength [] = 0

Il fonctionne en écaillage un élément au moment de la liste et en ajoutant un au résultat. Pour visualiser, pensez à l'appel

myLength [1,2,3]

qui évaluera à:

1 + myLength [2,3]
1 + 1 + myLength [3]
1 + 1 + 1 + myLength []
1 + 1 + 1 + 0

qui est 3.

En ce qui concerne le second, eh bien, vous avez déjà divisé la chaîne à la rupture de la ligne suivante en deux parties: avant et suf. Maintenant, suf va commencer avec soit un \ n ou un \ r, ou \ r \ n. Nous voulons supprimer. Nous utilisons donc pattern matching. Voyez comment la variable reste est essentiellement la variable suf moins le caractère de saut de ligne initiale (s).

Nous avons donc pré, qui est la première ligne, et de repos, ce qui est le reste du texte. Ainsi, afin de continuer le repos de séparation en lignes que nous appelons sur récursivement lignes de division et concaténer le résultat à l'avance.

Pour visualiser, que vous avez la chaîne "foo \ nbar \ r \ nbaz".

Ainsi, lors de l'appel, le résultat sera:

[ pre => foo, suf => \nbar\r\nbaz, rest => bar\r\n\baz ]
foo : splitLines bar\r\nbaz

puis est appelé à nouveau lignes de division, et le résultat est étendu à:

[ pre => bar, suf => \r\nbaz, rest = baz ]
foo : bar : splitLines baz

puis une fois encore:

[ pre => baz, suf => [], rest = [] ]
foo : bar : baz

qui est le résultat final.

Answer 2

Je pense que la définition de myLength rate le cas où la liste est vide:

myLength [] = 0
myLength (x:xs) = 1 + myLength (xs)

Avec cette définition, la myLength d'une liste vide est 0. Le patten (x:xs) décompresse une liste dans le premier élément, a, et une liste avec le reste des éléments, xs. Si la liste a un élément, puis xs est une liste vide, donc le résultat est 1 + 0. Et ainsi de suite.

La récursivité est plus facile à comprendre quand on regarde le cas de base en premier lieu, puis voir comment chaque niveau de récursivité se base sur le résultat. (Le cas de base est le cas où la fonction ne se remet pas. Si une fonction récursive ne dispose pas d'un cas de base, la sortie sera infinie.)

Dans le deuxième exemple, le cas de base (le dernier cas dans le cas statment) est également une liste vide. Donc, avant sera toujours jointe à une liste, ce qui donnera une nouvelle, plus longue, liste.

Answer 3

Re: myLength (x:xs) = 1 + myLength (xs) - c'est « la moitié » de la définition de myLength, il est dit, par correspondance de motif, que si l'argument a une tête et une queue, le résultat est un plus que l'appel de la queue récursive sur la queue - il doit y avoir une autre moitié pour dire que le résultat est 0 lorsque l'argument ne peut pas correspondre x:xs, à savoir, lorsque l'argument est une liste vide

.

Dans le second cas, la possibilité de mise en correspondance des motifs différents est juste fait un peu plus epxlicit via case.

BTW, la paresse est pas une question clé ici - ML, avec une évaluation, mais désireux ltrage beaucoup comme Haskell, fonctionnerait de façon très similaire. On dirait que la recherche de motifs est ce que vous avez vraiment besoin de se brosser environ.

Answer 4

D'abord le premier exemple devrait être comme ça ( modifier il semble que vous fixe maintenant):

myLength []     = 0
myLength (x:xs) = 1 + myLength (xs)

Il fonctionne comme ceci: dire que je donne une liste avec trois articles, il renvoie une plus la longueur de la queue (ce qui est un plus la longueur de la queue (ce qui est un plus la longueur de la queue (qui est [] à ce point), qui est 1), qui est w), qui est 3 (la réponse finale). Peut-être entre parenthèses imbriquées vous aider à le comprendre. ; -)

Answer 5

Il est intéressant de regarder ce que les signatures de type des fonctions seraient. Ils pourraient être:

myLength :: [a] -> Int

myLength, 1 est ajouté à la suite de l'appel récursif à myLength, qui est un Int, ce qui entraîne à son tour dans un Int.

splitLines :: [Char] -> [[Char]]

Dans splitLines, pre (un [Char]) est préfixé au résultat de l'instruction de cas qui, de regarder les cas, est soit le résultat d'un appel récursif à splitLines, qui est [[Char]]; ou une liste vide. Dans les deux cas, préfixer pre (un [Char]) entraînera une [[Char]] à son tour.