Signatures de type explicite pour les types polymorphes. Partie II

Question

Ceci est a follow up to a previous question: I got an answer I didn't really understand and accepted. Je vais donc demander à nouveau:

Je ne comprends toujours pas comment cela est logique:

type Parse a b = [a] -> [(b,[a])] 
build :: Parse a b -> (b -> c) -> Parse a c 
build p f inp = [ (f x, rem) | (x, rem) <- p inp ] 

Maintenant, évidemment, p se fixe au premier argument de type Parse a b. Et, évidemment, f se lie au deuxième argument (b -> c). Ma question reste: à quoi correspond inp?

Si Parse a b est synonyme de type pour [a] -> [(b,[a])] je pensais à la dernière question que je pouvais le remplacer:

build :: [a] -> [(b,[a])] -> (b -> c) -> [a] -> [(c,[a])] 

Cependant, je ne vois pas que aucun sens soit à la définition:

build p f inp = [ (f x, rem) | (x, rem) <- p inp ] 

Quelqu'un pease aide à expliquer les synonymes de type.

Answer 1

Maintenant, évidemment, p se lie au premier argument de type Parse a b. Et, évidemment, f se lie au second argument (b -> c). Ma question reste à quoi se lient inp?

L'argument de type [a]

Si Parse ab est synonyme de type pour [a] -> [(b, [a])] Je pensais à la dernière question que je pourrait juste le remplacer :

build :: [a] -> [(b,[a])] -> (b -> c) -> [a] -> [(c,[a])] 

Presque; vous devez parenthésée les substitutions:

build :: ([a] -> [(b,[a])]) -> (b -> c) -> ([a] -> [(c,[a])]) 

Parce que -> est associatif à droite, vous pouvez supprimer les parenthèses à la fin, mais pas au début, de sorte que vous obtenez:

build :: ([a] -> [(b,[a])]) -> (b -> c) -> [a] -> [(c,[a])] 

Ceci devrait évident pourquoi inp a le type [a].

Answer 2

Si vous remplacez

type Parse a b = [a] -> [(b,[a])] 

dans

build :: Parse a b -> (b -> c) -> Parse a c 

vous

build :: ([a] -> [(b,[a])]) -> (b -> c) -> [a] -> [(c,[a])] 

Rappelez-vous que x -> y -> z est un raccourci pour x -> (y -> z) qui est très différent de (x -> y) -> z. La première est une fonction qui prend deux arguments x, y et renvoie z [il prend précisément un argument x et renvoie une fonction, qui prend y et renvoie z]; le second est quelque chose qui prend une fonctionx -> y et renvoie z.

Answer 3

La chose importante à retenir ici est que la flèche -> dans les signatures de type est associative droite. Le type a -> (b -> c) est identique au type a -> b -> c.

Ainsi, le type

Parse a b -> (b -> c) -> Parse a c 

décide de

([a] -> [(b,[a])]) -> (b -> c) -> ([a] -> [(c,[a])]) 

Par associativité, vous pouvez supprimer les derniers parens, mais pas la première. Cela vous donne

([a] -> [(b,[a])]) -> (b -> c) -> [a] -> [(c,[a])] 

qui vous permet d'écrire une formule pour build avec 3 arguments.

Answer 4

Vous pouvez remplacer - mais n'oubliez pas de fixer! Cela devrait être:

build :: ([a] -> [(b,[a])]) -> (b -> c) -> ([a] -> [(c,[a])]) 

Parce que la flèche de fonction est associatif à droite, vous pouvez vider l'ensemble de droite de crochets, mais fondamentalement vous ne pouvez pas ignorer les nouvelles sur la gauche:

build :: ([a] -> [(b,[a])]) -> (b -> c) -> [a] -> [(c,[a])] 

Alors maintenant, quand vous avez la ligne build p f inp, vous pouvez voir que:

p :: ([a] -> [(b,[a])]) 
f :: (b -> c) 
inp :: [a] 

alors nous pouvons voir que:

f inp :: [(b, [a])] 

Et ainsi:

x :: b 
rem :: [a] 

Et:

f x :: c 
(f x, rem) :: (c, [a]) 

Et donc toute la compréhension de la liste est de type [(c, [a])] - qui correspond parfaitement ce que build devrait revenir. J'espère que cela pourra aider!