Kombinieren Sie Fragmente des Haskell-Codes, um ein größeres Bild zu erhalten

12

Dies ist der Code, auf den ich irgendwo gestoßen bin, aber ich möchte wissen, wie das funktioniert:

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

Ausgabe: findIndices (== 0) [1,2,0,3,0] == [2,4] , wobei pred (== 0) & xs [1,2,0,3,0] ist

Ich werde etwas von meinem Verständnis zeigen:

    (zip [0..] xs)

In der obigen Zeile werden Indizes für alle Elemente in der Liste angezeigt. Für die oben angegebene Eingabe würde dies folgendermaßen aussehen: [(0,1), (1,2), (2,0), (3,3), (4,0)]

    (pred . snd)

Ich fand, dass dies so etwas wie pred (snd (x)) bedeutet. Meine Frage ist, ist x die Liste aus der Postleitzahl? Ich neige mich zu Ja, aber meine Vermutung ist schwach.

Als nächstes ist mein Verständnis von fst und snd. ich weiß das

    fst(1,2) = 1 

und

    snd(1,2) = 2

Wie machen diese beiden Befehle im Code Sinn?

Mein Verständnis von Filter ist, dass es eine Liste von Elementen zurückgibt, die einer Bedingung entsprechen. Zum Beispiel,

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

würde geben [6,7,8,9,10]

Mein Verständnis von Map ist, dass es eine Funktion auf jedes Element in der Liste anwendet. Zum Beispiel,

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

würde geben [4,8,12,16,20]

Wie funktioniert das insgesamt? Ich glaube, ich war umfassend in dem, was ich bisher weiß, kann die Teile aber nicht ganz zusammenfügen. Kann mir jemand helfen?

Shreeman Gautam
quelle
7
Ich möchte nur sagen, dass das Lesen dieser Frage ein seltenes Vergnügen war. Wir bekommen "wie zum Teufel funktioniert dieser Code?" Fragen häufig, aber selten mit dieser Erklärungsebene dessen, was der Fragesteller tut und was er noch nicht versteht. Das macht wirklich Spaß, eine gute, zielgerichtete Antwort über genau die Lücken zu schreiben, die Sie haben.
Daniel Wagner
Danke Daniel! Ich habe viel Zeit mit diesem Problem verbracht und konnte deshalb genau bestimmen, bei was ich Hilfe brauchte.
Shreeman Gautam
Ich möchte hinzufügen, dass die @ WillNess-Antwort auch funktioniert. Es ist viel einfacher für das Auge und leicht zu verstehen.
Shreeman Gautam

Antworten:

2

In Haskell möchten wir sagen, folgen Sie den Typen . In der Tat verbinden sich die Teile wie durch Drähte, die vom Typ zum entsprechenden Typ gehen:

(Erstens ist die Funktionszusammensetzung :

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

Die Inferenzregel für den Typ der Funktionszusammensetzung lautet:

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

Jetzt, )

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]

also insgesamt

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

Sie haben gefragt, wie diese Teile zusammenpassen?

Das ist wie.


Mit Listenverständnis wird Ihre Funktion als geschrieben

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

was im Pseudocode lautet:

"Ergebnisliste enthält ifür jeden (i,x)in zip [0..] xsso, dass pred xgilt" .

Dies geschieht durch Drehen der nLänge

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

in

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

wo [a | True]ist [a]und [a | False]ist [].

Will Ness
quelle
Du hast deine Stimme, Mann. Vielen Dank!
Shreeman Gautam
8

Ich fand, dass dies so etwas bedeutet pred (snd (x)). Meine Frage ist, ist x die Liste aus der Postleitzahl? Ich neige mich zu Ja, aber meine Vermutung ist schwach.

Nun pred . snd, bedeutet \x -> pred (snd x). Also diese Konstrukte im Grunde eine Funktion , die ein Element bildet xauf pred (snd x).

Dies bedeutet also, dass der Ausdruck wie folgt aussieht:

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

Hier xwird also ein 2-Tupel von erzeugt zip. Also, um zu wissen , wenn (0, 1), (1,2), (2, 0)etc. werden im Ergebnis beibehalten, snd xnehmen das zweite Element dieser 2-Tupel (so 1, 2, 0, etc.), und prüfen Sie, ob die predauf tha Elemente erfüllt ist oder nicht. Wenn es erfüllt ist, behält es das Element bei, andernfalls wird dieses Element (das 2-Tupel) herausgefiltert.

Wenn (== 0)also das predIce ist, filter (pred . snd) (zip [0..] xs)enthält es die 2-Tupel [(2, 0), (4, 0)].

Aber jetzt ist das Ergebnis eine Liste von 2 Tupeln. Wenn wir die Indizes wollen, müssen wir das 2-Tupel und das zweite Element dieser 2-Tupel irgendwie loswerden. Wir verwenden fst :: (a, b) -> adafür: Dies ordnet ein 2-Tupel seinem ersten Element zu. So finden Sie eine Liste [(2, 0), (4, 0)], map fst [(2, 0), (4, 0)]kehrt [2, 4].

Willem Van Onsem
quelle
1
Hey Willem, was für eine großartige Erklärung! Ich habe jetzt den vollständigen Code verstanden. Danke mein Herr!
Shreeman Gautam