Je sais ce que la fonction suivante fait je voudrais juste comme une explication de la façon dont il fonctionne et les calculs qui ont lieu:Explique comment fonctionne une fonction de liste Haskell récursive?
sponge :: Int -> [a] -> [a]
sponge 0 xs = xs
sponge n [] = []
sponge n (x:xs) = sponge (n-1) xs
Il me semble juste avoir perdu le terrain avec tout maintenant :(
Toute aide pour me remettre sur les rails serait très appréciée! :)
C'est une fonction récursive sur deux variables. Vous pouvez le briser ligne par ligne pour comprendre:
sponge :: Int -> [a] -> [a]
Deux arguments, l'un d'une Int, une liste de certains éléments.
sponge 0 xs = xs
Le cas de base. Si l'argument Int est zéro, renvoie simplement l'argument de liste non modifié. Un autre cas de base, si la liste est vide, renvoie immédiatement la liste vide.
sponge n (x:xs) = sponge (n-1) xs
Enfin, l'étape inductive. Si la liste est non vide (c'est-à-dire composée d'au moins un élément et une queue, notée x:xs), le résultat est sponge appelé n-1 et la queue de la liste.
Alors, que va faire cette fonction? Il va retourner la queue de la liste après avoir déposé n éléments. Il est le même que la fonction drop:
> drop 10 [1..20]
[11,12,13,14,15,16,17,18,19,20]
Et
> sponge 10 [1..20]
[11,12,13,14,15,16,17,18,19,20]
En fait, nous pouvons demander QuickCheck confirmer:
> quickCheck $ \n xs -> sponge n xs == drop n xs
*** Failed! Falsifiable (after 7 tests and 5 shrinks):
-1
[()]
Ah! Ils sont différents. Quand n est négatif! Ainsi, nous pouvons modifier la propriété concernant les deux fonctions:
> quickCheck $ \n xs -> n >= 0 ==> sponge n xs == drop n xs
+++ OK, passed 100 tests.
Ainsi, votre fonction se comporte comme goutte, pour les cas où n est positif.
Voici une trace des valeurs intermédiaires de n et xs, obtenu par l'hood debugger:
Cela prend deux paramètres, comme vous pouvez le voir: un Int et une liste. Il correspond à un modèle pour distinguer trois cas: 1) l'Int est nul; 2) la liste est vide; ou, 3) l'Int n'est pas zéro et la liste n'est pas vide.
Dans le cas 1, il renvoie la liste; dans le cas 2, il renvoie la liste vide (ce qui est de toute façon le second paramètre); dans le cas 3, il s'appelle récursivement avec le paramètre Int original moins 1 et la liste originale moins son premier élément.
Cela ressemble beaucoup à "drop" du Prelude.
Vous dites que vous avez perdu l'intrigue et sont sur la bonne voie, mais vous donner aucune idée à ce que vous ne comprenez pas. C'est important, car ce code ne nécessite qu'une compréhension très rudimentaire de Haskell. Alors, y a-t-il une syntaxe que vous ne comprenez pas? –
La question a été éditée d'une manière trompeuse. En ajoutant le mot "récursion", que l'OP n'a pas utilisé, il laisse l'impression que c'est une récursion que l'OP a des problèmes, mais on ne sait pas que l'OP a des problèmes avec la récursivité ... ou même que l'OP sait quelle récursion est ou est consciente que la fonction est récursive. –
@Jim Balter Le mot récursivité a été ajouté afin que nous puissions trouver la réponse plus tard, catégorisée, telle qu'elle est, sous les termes appropriés. Les titres comme "expliquer cette fonction" ne sont pas consultables. –