Łączenie fragmentów kodu Haskell, aby uzyskać większy obraz

12

Oto kod, który gdzieś natknąłem, ale chcę wiedzieć, jak to działa:

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

Dane wyjściowe: findIndices (== 0) [1,2,0,3,0] == [2,4] , gdzie pred wynosi (== 0), a xs wynosi [1,2,0,3,0]

Pokażę trochę mojego zrozumienia:

    (zip [0..] xs)

Powyższa linia wprowadza indeksy do wszystkiego na liście. Dla danych wejściowych podanych powyżej wyglądałoby to tak: [(0,1), (1,2), (2,0), (3,3), (4,0)]

    (pred . snd)

Odkryłem, że oznacza to coś w rodzaju pred (snd (x)). Moje pytanie brzmi: czy x jest listą utworzoną z linii zip? Skłaniam się ku tak, ale moje przypuszczenia są wątłe.

Następnie moje rozumienie fst i snd. wiem to

    fst(1,2) = 1 

i

    snd(1,2) = 2

Jak te 2 polecenia mają sens w kodzie?

Rozumiem, że filtr polega na tym, że zwraca listę elementów spełniających warunek. Na przykład,

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

dałby [6,7,8,9,10]

Rozumiem, że mapa ma zastosowanie do każdej pozycji na liście. Na przykład,

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

dałby [4,8,12,16,20]

Jak to ogólnie działa? Wydaje mi się, że byłem wyczerpujący w tym, co wiem do tej pory, ale nie jestem w stanie poskładać całości. Czy ktokolwiek może mi pomóc?

Shreeman Gautam
źródło
7
Chciałbym tylko powiedzieć, że przeczytanie tego pytania było rzadką przyjemnością. Otrzymujemy „jak do cholery działa ten kod?” pytania często, ale rzadko z tym poziomem wyjaśnienia tego, co pytający robi i jeszcze nie rozumie. To sprawia, że ​​naprawdę fajnie jest napisać dobrą, ukierunkowaną odpowiedź na temat dokładnie twoich braków.
Daniel Wagner
Dziękuję Daniel! Spędziłem dużo czasu na tym problemie i dlatego mogłem wskazać, w czym potrzebowałem pomocy.
Shreeman Gautam
Chciałbym dodać, że odpowiedź @WillNess również działa. Jest to znacznie łatwiejsze dla oka i łatwe do zrozumienia.
Shreeman Gautam

Odpowiedzi:

2

W Haskell lubimy mówić: podążaj za typami . Rzeczywiście elementy łączą się jakby drutami przechodzącymi od typu do odpowiedniego typu:

(po pierwsze, skład funkcji to:

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

a regułą wnioskowania o składzie funkcji jest

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

Teraz, )

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]

więc ogólnie

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

Zapytałeś, jak te elementy pasują do siebie?

Oto jak.


Z listami twoja funkcja jest zapisana jako

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

który w pseudokodzie brzmi:

„lista zawiera wynik idla siebie (i,x)w zip [0..] xstaki sposób, że pred xposiada” .

Robi to, obracając n-długie

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

w

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

gdzie [a | True]jest [a]i [a | False]jest [].

Will Ness
źródło
Masz swój głos, człowieku. Dzięki!
Shreeman Gautam
8

Przekonałem się, że to coś takiego pred (snd (x)). Moje pytanie brzmi: czy x jest listą utworzoną z linii zip? Skłaniam się ku tak, ale moje przypuszczenia są wątłe.

Cóż pred . snd, znaczy \x -> pred (snd x). Więc to w zasadzie tworzy funkcję, która mapuje element xna pred (snd x).

Oznacza to zatem, że wyrażenie wygląda następująco:

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

Oto x2-krotność wygenerowana przez zip. Tak, aby wiedzieć, czy (0, 1), (1,2), (2, 0), itd. Są zatrzymywane w wyniku snd xweźmie drugi element tych 2-krotek (tak 1, 2, 0, itd), i sprawdzić, czy predna tha elementu jest usatysfakcjonowany lub nie. Jeśli jest spełniony, zachowuje element, w przeciwnym razie element (2-krotka) zostanie odfiltrowany.

Więc jeśli (== 0)jest predicate, to filter (pred . snd) (zip [0..] xs)będzie zawierać 2-krotki [(2, 0), (4, 0)].

Ale teraz wynikiem jest lista 2-krotek. Jeśli chcemy indeksów, musimy jakoś pozbyć się 2-krotek i drugiego elementu tych 2-krotek. Używamy fst :: (a, b) -> ado tego: to mapuje 2-krotkę na pierwszym elemencie. Tak na listy [(2, 0), (4, 0)], map fst [(2, 0), (4, 0)]powróci [2, 4].

Willem Van Onsem
źródło
1
Hej Willem, co za wspaniałe wytłumaczenie! Teraz zrozumiałem pełny kod. Dziękuję Panu!
Shreeman Gautam