Menggabungkan potongan-potongan Kode Haskell untuk mendapatkan gambaran yang lebih besar

12

Ini adalah kode yang saya temukan di suatu tempat tetapi ingin tahu cara kerjanya:

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

Output: findIndices (== 0) [1,2,0,3,0]==[2,4] , di mana predadalah (==0)& xsadalah[1,2,0,3,0]

Saya akan menunjukkan beberapa pemahaman saya:

    (zip [0..] xs)

Apa yang dilakukan oleh baris di atas adalah meletakkan indeks pada semua yang ada dalam daftar. Untuk input yang diberikan di atas, akan terlihat seperti ini: [(0,1),(1,2),(2,0),(3,3),(4,0)].

    (pred . snd)

Saya menemukan bahwa ini berarti sesuatu seperti pred (snd (x)). Pertanyaan saya adalah, apakah xdaftar dibuat dari zipgaris? Saya condong ke arah ya tapi dugaan saya lemah.

Selanjutnya, adalah pemahaman saya tentang fstdan snd. saya tahu itu

    fst(1,2) = 1 

dan

    snd(1,2) = 2

Bagaimana kedua perintah ini masuk akal dalam kode?

Pemahaman saya filteradalah bahwa ia mengembalikan daftar item yang cocok dengan suatu kondisi. Contohnya,

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

akan memberi [6,7,8,9,10]

Pemahaman saya tentang peta adalah bahwa ia menerapkan fungsi untuk setiap item dalam daftar. Contohnya,

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

akan memberi [4,8,12,16,20]

Bagaimana cara kerjanya secara keseluruhan? Saya pikir saya telah komprehensif dalam apa yang saya ketahui sejauh ini tetapi tidak bisa menyatukan potongan-potongan itu. Adakah yang bisa membantu saya?

Shreeman Gautam
sumber
7
Saya hanya ingin mengatakan bahwa membaca pertanyaan ini adalah kesenangan yang langka. Kami mendapatkan "bagaimana sih kode ini bekerja?" pertanyaan sering, tetapi jarang dengan tingkat penjelasan tentang apa yang penanya lakukan dan tidak mengerti. Itu membuatnya sangat menyenangkan untuk menulis jawaban yang tepat dan terarah tentang kesenjangan yang Anda miliki.
Daniel Wagner
Daniel terima kasih! Saya menghabiskan banyak waktu dalam masalah ini dan itulah sebabnya, saya dapat menunjukkan dengan tepat apa yang saya butuhkan bantuan.
Shreeman Gautam
Saya ingin menambahkan bahwa jawaban @WillNess juga berfungsi. Itu jauh lebih mudah di mata dan mudah dimengerti.
Shreeman Gautam

Jawaban:

2

Di Haskell kami ingin mengatakan, ikuti tipenya . Memang potongan-potongan terhubung seolah-olah dengan kabel dari jenis ke jenis yang sesuai:

(pertama, komposisi fungsi adalah:

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

dan aturan inferensi tipe komposisi fungsi adalah:

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

Sekarang, )

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]

jadi, secara keseluruhan,

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

Anda sudah bertanya, bagaimana potongan-potongan ini cocok?

Begini caranya.


Dengan pemahaman daftar , fungsi Anda ditulis sebagai

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

yang dalam pseudocode berbunyi:

+ msgstr "daftar hasil berisi iuntuk masing - masing (i,x)dalam zip [0..] xsyang pred xmenyimpan" .

Ini melakukan ini dengan memutar- npanjang

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

ke

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

di mana [a | True]adalah [a]dan [a | False]adalah [].

Will Ness
sumber
8

Saya menemukan bahwa ini berarti sesuatu seperti pred (snd (x)). Pertanyaan saya adalah, apakah x daftar dibuat dari garis zip? Saya condong ke arah ya tapi dugaan saya lemah.

Ya pred . sndberarti \x -> pred (snd x). Jadi ini pada dasarnya membangun sebuah fungsi yang memetakan elemen xpada pred (snd x).

Ini dengan demikian berarti bahwa ekspresi itu terlihat seperti:

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

Ini xadalah 2-tuple yang dihasilkan oleh zip. Jadi untuk mengetahui apakah (0, 1), (1,2), (2, 0), dll dipertahankan dalam hasil, snd xakan mengambil elemen kedua ini 2-tupel (jadi 1, 2, 0, dll), dan memeriksa apakah predpada elemen tha puas atau tidak. Jika puas, itu akan mempertahankan elemen, jika elemen itu (2-tuple) disaring.

Jadi jika (== 0)adalah predicate, maka filter (pred . snd) (zip [0..] xs)akan berisi 2-tupel [(2, 0), (4, 0)].

Tetapi sekarang hasilnya adalah daftar 2-tupel. Jika kita menginginkan indeks, kita harus menyingkirkan 2-tuple, dan elemen kedua dari 2-tupel ini. Kami menggunakan fst :: (a, b) -> auntuk itu: ini memetakan 2-tuple pada elemen pertama. Jadi untuk daftar [(2, 0), (4, 0)], map fst [(2, 0), (4, 0)]akan kembali [2, 4].

Willem Van Onsem
sumber
1
Hei Willem, penjelasan yang luar biasa! Saya sudah mengerti kode lengkapnya sekarang. Terima kasih Pak!
Shreeman Gautam