Combiner des fragments du code Haskell pour obtenir une vue d'ensemble

12

Voici le code que j'ai rencontré quelque part, mais je veux savoir comment cela fonctionne:

    findIndices :: (a -> Bool) -> [a] -> [Int]
    findIndices _ [] = []
    findIndices pred xs = map fst (filter (pred . snd) (zip [0..] xs))

Sortie: findIndices (== 0) [1,2,0,3,0]==[2,4] , où predest (==0)& xsest[1,2,0,3,0]

Je vais montrer une partie de ma compréhension:

    (zip [0..] xs)

Ce que la ligne ci-dessus fait est de mettre des indices à tout dans la liste. Pour l'entrée donnée ci - dessus, il ressemblerait à ceci: [(0,1),(1,2),(2,0),(3,3),(4,0)].

    (pred . snd)

J'ai trouvé que cela signifie quelque chose comme pred (snd (x)). Ma question est la suivante: xla liste est-elle établie à partir de la zipligne? Je penche vers oui mais ma supposition est fragile.

Ensuite, est ma compréhension de fstet snd. je le sais

    fst(1,2) = 1 

et

    snd(1,2) = 2

Comment ces deux commandes ont-elles un sens dans le code?

Ma compréhension filterest qu'il renvoie une liste d'articles qui correspondent à une condition. Par exemple,

    listBiggerThen5 = filter (>5) [1,2,3,4,5,6,7,8,9,10]

donnerait [6,7,8,9,10]

Ma compréhension de la carte est qu'elle applique une fonction à chaque élément de la liste. Par exemple,

    times4 :: Int -> Int
    times4 x = x * 4
    listTimes4 = map times4 [1,2,3,4,5]

donnerait [4,8,12,16,20]

Comment cela fonctionne-t-il globalement? Je pense que j'ai été complet dans ce que je sais jusqu'à présent, mais je ne peux pas tout à fait assembler les morceaux. Quelqu'un peut-il m'aider?

Shreeman Gautam
la source
7
Je voudrais juste dire que la lecture de cette question a été un plaisir rare. Nous obtenons "comment diable ce code fonctionne-t-il?" questions fréquemment, mais rarement avec ce niveau d'explication de ce que le demandeur fait et ne comprend pas déjà. Cela rend vraiment amusant d'écrire une bonne réponse ciblée sur exactement les lacunes que vous avez.
Daniel Wagner
Merci Daniel! J'ai passé beaucoup de temps dans ce problème et c'est pourquoi j'ai pu identifier avec quoi j'avais besoin d'aide.
Shreeman Gautam
Je voudrais ajouter que la réponse @WillNess fonctionne également. C'est beaucoup plus agréable à regarder et facile à comprendre.
Shreeman Gautam Il y a

Réponses:

2

À Haskell, nous aimons dire, suivez les types . En effet les pièces se connectent comme par des fils allant du type au type correspondant:

(premièrement, la composition des fonctions est:

   (f >>> g) x  =  (g . f) x  =        g (f x)
   (f >>> g)    =  (g . f)    =  \x -> g (f x)

et la règle d'inférence du type de composition de fonction est:

    f        :: a -> b                   --      x  :: a
          g  ::      b -> c              --    f x  :: b
   -------------------------             -- g (f x) :: c
    f >>> g  :: a ->      c
    g  .  f  :: a ->      c

Maintenant, )

findIndices :: (b -> Bool) -> [b] -> [Int]
findIndices pred  = \xs -> map fst ( filter (pred . snd) ( zip [0..] xs ))
                  =        map fst . filter (pred . snd) . zip [0..]
                  =  zip [0..]  >>>  filter (snd >>> pred)  >>>  map fst
---------------------------------------------------------------------------
zip :: [a] ->          [b]        ->        [(a,  b)]
zip  [0..] ::          [b]        ->        [(Int,b)]
---------------------------------------------------------------------------
        snd           :: (a,b) -> b
                pred  ::          b -> Bool
       ------------------------------------
       (snd >>> pred) :: (a,b)      -> Bool
---------------------------------------------------------------------------
filter ::               (t          -> Bool) -> [t]   -> [t]
filter (snd >>> pred) ::                      [(a,b)] -> [(a,b)]
filter (snd >>> pred) ::                    [(Int,b)] -> [(Int,b)]
---------------------------------------------------------------------------
    fst ::                                   (a,   b) -> a
map     ::                                  (t        -> s) -> [t] -> [s]
map fst ::                                                 [(a,b)] -> [a]
map fst ::                                               [(Int,b)] -> [Int]

donc, dans l'ensemble,

zip  [0..] ::          [b]        ->        [(Int,b)]
filter (snd >>> pred) ::                    [(Int,b)] -> [(Int,b)]
map fst ::                                               [(Int,b)] -> [Int]
---------------------------------------------------------------------------
findIndices pred ::    [b] ->                                         [Int]

Vous avez demandé, comment ces pièces s'assemblent-elles?

C'est ainsi.


Avec les listes de compréhension , votre fonction s'écrit

findIndices pred xs = [ i | (i,x) <- zip [0..] xs, pred x ]

qui en pseudocode se lit comme suit:

« liste de résultats contient ipour chaque (i,x)dans zip [0..] xsce qui pred xtient » .

Il le fait en tournant le n-long

xs = [a,b,...,z] = [a] ++ [b] ++ ... ++ [z]

dans

  [0 | pred a] ++ [1 | pred b] ++ ... ++ [n-1 | pred z]

[a | True]est [a]et [a | False]est [].

Will Ness
la source
8

J'ai trouvé que cela signifie quelque chose comme pred (snd (x)). Ma question est, est-ce que la liste est faite à partir de la tyrolienne? Je penche vers oui mais ma supposition est fragile.

Eh bien pred . snd, ça veut dire \x -> pred (snd x). Donc , ce construit essentiellement une fonction qui un élément xsur pred (snd x).

Cela signifie donc que l'expression ressemble à:

filter (\x -> pred (snd x)) (zip [0..] xs)

Voici xdonc un 2-tuple généré par zip. Ainsi, afin de savoir si (0, 1), (1,2), (2, 0), etc. sont conservés dans le résultat, snd xprendra le deuxième élément de ces 2 triplets (donc 1, 2, 0, etc.), et vérifier si le predsur tha élément est satisfait ou non. S'il est satisfait, il conservera l'élément, sinon cet élément (le tuple 2) est filtré.

Donc, si (== 0)c'est la predglace, alors filter (pred . snd) (zip [0..] xs)contiendra les 2 tuples [(2, 0), (4, 0)].

Mais maintenant, le résultat est une liste de 2 tuples. Si nous voulons les indices, nous devons en quelque sorte nous débarrasser du 2-tuple et du deuxième élément de ces 2-tuples. Nous utilisons fst :: (a, b) -> apour cela: cela mappe un 2-tuple sur son premier élément. Donc, pour une liste [(2, 0), (4, 0)], map fst [(2, 0), (4, 0)]reviendra [2, 4].

Willem Van Onsem
la source
1
Hé Willem, quelle belle explication! J'ai compris le code complet maintenant. Merci Monsieur!
Shreeman Gautam