Bagaimana "concatMap" dari mono-traversable dapat "menarik" argumen umum?

9

Saya belajar Haskell dan sedang melakukan program DB-seed sederhana untuk Yesod ketika saya menemukan perilaku ini yang sulit saya pahami:

testFn :: Int -> Bool -> [Int]
testFn a b = if b then replicate 10 a else []

Sesi Yesod GHCI:

$ :t concatMap testFn [3]
concatMap testFn [3] :: Bool -> [Int]
$ (concatMap testFn [1,2,3]) True
[1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3]

Entah bagaimana itu bisa "menarik" keluar itu "Bool" kedua dari masing-masing pemetaan menjadi argumen kari tunggal.

Sesi GHCI Pangkalan standar awal menolak untuk mengkompilasi ekspresi ini:

$ :t concatMap testFn [3]
error:
     Couldn't match type 'Bool -> [Int]' with '[b]'
      Expected type: Int -> [b]
        Actual type: Int -> Bool -> [Int]
     Probable cause: 'testFn' is applied to too few arguments
      In the first argument of 'concatMap', namely 'testFn'
      In the expression: concatMap testFn [3]

Ternyata Yesod menggunakan pustaka mono-traversable yang memiliki concatMap:

$ :t concatMap
concatMap
  :: (MonoFoldable mono, Monoid m) =>
     (Element mono -> m) -> mono -> m

Pada tingkat pemahaman Haskell saya saat ini, saya tidak tahu bagaimana tipe didistribusikan di sini. Bisakah seseorang menjelaskan kepada saya (sebanyak mungkin pemula berorientasi) bagaimana trik ini dilakukan? Bagian mana di testFnatas yang sesuai untuk diketik Element mono?

dimsuz
sumber

Jawaban:

6

Kami mulai dengan mendaftar beberapa jenis yang kami tahu. (Kami berpura-pura angka hanya Intuntuk kesederhanaan - ini tidak benar-benar relevan.)

testFn :: Int -> Bool -> [Int]
[1,2,3] :: [Int]
True :: Bool

(concatMap testFn [1,2,3]) Truesama dengan concatMap testFn [1,2,3] True, jadi concatMapharus memiliki tipe yang cocok dengan semua argumen itu:

concatMap :: (Int -> Bool -> [Int]) -> [Int] -> Bool -> ???

dimana ???jenis hasilnya. Perhatikan bahwa, karena aturan associativity, ->kaitkan ke kanan, jadi pengetikan di atas sama dengan:

concatMap :: (Int -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

Mari kita tulis tipe umum di atas yang itu. Saya menambahkan beberapa spasi untuk menandai kesamaan.

concatMap :: (MonoFoldable mono, Monoid m) =>
             (Element mono -> m              ) -> mono  -> m
concatMap :: (Int          -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

Ah-ha! Kami memiliki kecocokan jika kami memilih msebagai Bool -> [Int], dan monosebagai [Int]. Jika kita melakukannya, kita memenuhi batasan MonoFoldable mono, Monoid m(lihat di bawah), dan kita juga punya Element mono ~ Int, jadi semuanya ketikkan cek.

Kami menyimpulkan bahwa ???adalah [Int]dari definisi m.

Tentang kendala: karena MonoFoldable [Int], tidak banyak yang bisa dikatakan. [Int]jelas daftar-seperti jenis dengan Intjenis elemen, dan itu sudah cukup untuk membuatnya menjadi MonaFoldabledengan Intsebagai yang Element.

Sebab Monoid (Bool -> [Int]), itu sedikit lebih rumit. Kami memiliki semua tipe fungsi A -> Badalah monoid jika Badalah monoid. Ini mengikuti dengan melakukan operasi dengan cara yang benar. Dalam kasus khusus kami, kami mengandalkan [Int]monoid dan kami mendapatkan:

mempty :: Bool -> [Int]
mempty = \_ -> []

(<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])
f <> g = \b -> f b ++ g b
chi
sumber
1
Penjelasan hebat! Cara Anda menjelaskan dan menyelaraskan tipe adalah apa yang ingin saya lihat, terima kasih!
dimsuz