Pertanyaan Nilai sublist grup berdasarkan jumlah yang setara dengan Haskell


Saya mencoba mempelajari Haskell dan saya mencoba membuat fungsi yang mengambil daftar daftar dan mengelompokkan sublist dengan jumlah yang setara. Ini bukan pekerjaan rumah.

import Data.List
let x = [[1,2],[2,1],[5,0],[0,3],[1,9]]
let groups = groupBy (\i j -> sum i == sum j) x

Saya mendapatkan output ini di GHCi:

[[[1,2],[2,1]],[[5,0]],[[0,3]],[[1,9]]]

saya mendapat [[1,2],[2,1]] mengelompokkan bersama, tetapi tidak dengan [0,3]. Kenapa ini?

Saya kira saya perlu menggunakannya map, tetapi saya tampaknya tidak berhasil.


5
2018-03-30 20:30


asal


Jawaban:


Itu groupBy fungsi mempertahankan urutan input dan dengan demikian dapat dibalik. Jika Anda bersedia membuang informasi itu, Anda dapat menggunakan kode di sepanjang baris

import Data.List (foldl')
import Data.Map (elems,empty,insertWith')

bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]
bucketBy eq = elems . foldl' go empty
  where go m l = insertWith' (++) (eq l) [l] m

Dalam aksi:

* Utama> bucket Jumlah penjumlahan x
[[0,3], [2,1], [1,2]], [[5,0]], [[1,9]]]

Bagaimana itu bekerja

Aplikasi dari elems dari Data.Map memberi petunjuk untuk apa yang terjadi.

elems :: Map κ α -> [α]

Di). Kembalikan semua elemen peta dalam urutan menaik dari kunci mereka.

elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
elems empty == []

Pemetaan

Sebuah Peta mengaitkan nilai-nilai dari beberapa tipe κ dengan nilai-nilai dari tipe α lain yang mungkin berbeda. Dalam contoh dari pertanyaan Anda, Anda mulai dengan x tipe siapa

* Utama>: ketik x
x :: [[Integer]]

Itu adalah, x adalah daftar daftar bilangan bulat. Jenis yang dihasilkan partisi dari x yang kamu inginkan adalah

* Utama>: t [[0,3], [2,1], [1,2]], [[5,0]], [[1,9]]]
[[0,3], [2,1], [1,2]], [[5,0]], [[1,9]]] :: Num τ => [[[τ]]]

atau daftar daftar di mana masing-masing daftar terakhir adalah daftar yang semuanya memiliki jumlah yang sama. Itu Num τ => bit adalah a konteks yang membatasi tipe τ menjadi instance dari typeclass Num. Senang untuk kita, Integer adalah tipe seperti itu:

* Utama>: info Integer
data Integer
...
contoh Num Integer - Ditetapkan dalam GHC.Num
...

Kami tahu bahwa jenis partisi tersebut [[[Integer]]]. Ini omong kosong kotak-kelas mungkin tampak tidak perlu rewel, tetapi kami akan membutuhkan konsep itu lagi hanya dalam beberapa saat. (Untuk memberi Anda gambaran tentang apa yang terjadi, typechecker tidak memiliki cukup informasi untuk memutuskan apakah literal 0, misalnya, adalah tipe Int atau Integer.)

Setiap daftar berisi daftar dengan jumlah yang sama. Dengan kata lain, ada pemetaan dari jumlah ke daftar bilangan bulat. Oleh karena itu, jenis Peta yang digunakan dalam bucketBy harus menyerupai

Map Integer [[Integer]]

Misalnya, dengan jumlah 3 kita kaitkan daftar

[ [0,3]
, [2,1]
, [1,2]
]

Pola rekursi lipat

Lipat adalah pola yang sangat umum. Lipat kiri, foldl dan teman-teman di Haskell memungkinkan Anda "memasukkan" operator di antara elemen-elemen daftar yang dimulai dengan nilai nol di ujung kiri daftar. Misalnya, jumlah dari [5,3,9,1] diekspresikan sebagai lipatan kiri

((((0 + 5) + 3) + 9) + 1)

atau

foldl (+) 0 [5,3,9,1]

Artinya, dimulai dengan nilai dasar nol, kami secara berurutan menambahkan elemen daftar dan mengakumulasi jumlahnya.

Ingat kembali definisi bucketBy mengandung

elems . foldl' go empty

Ini berarti hasil lipatan kiri harus bertipe Map Integer [[Integer]], nilai nol untuk lipatan kami adalah Peta kosong dari jenis itu, dan go entah bagaimana menambahkan setiap nilai daftar yang berurutan ke dalam peta.

Perhatikan itu foldl' adalah sepupu ketat dari foldl, tetapi ketatnya berada di luar lingkup jawaban ini. (Lihat juga "Stack overflow" di HaskellWiki.)

Bung, di mana daftar saya?

Mengingat jenisnya foldl'

* Utama>: t foldl '
foldl ':: (a -> b -> a) -> a -> [b] -> a

kita harus memiliki tiga argumen dalam aplikasi, tetapi hanya dua yang ada dalam kode di atas. Ini karena kodenya ditulis gaya bebas titik. Daftar Anda ada secara implisit karena aplikasi parsial dari foldl'.

Pikirkan kembali ke contoh paruh waktu di atas. Jenis aplikasi itu tanpa argumen terakhir

* Utama>: t foldl (+) 0
foldl (+) 0 :: Num b => [b] -> b

Aplikasi parsial memungkinkan kita untuk membuat fungsi baru. Di sini kita mendefinisikan fungsi yang menghitung angka dari beberapa daftar angka. Hmm, terdengar familiar.

* Utama>: jumlah t
sum :: Num a => [a] -> a

Itu . kombinator mengekspresikan komposisi fungsi. Namanya dipilih menyerupai notasi g∘f seperti yang biasa terlihat dalam buku teks matematika yang berarti "lakukan f pertama dan kemudian hitung g dari hasilnya. ”Inilah yang terjadi dalam definisi bucketBy: lipat daftar nilai ke dalam Map dan kemudian dapatkan nilai dari Peta.

Jika ya harus pergi, pergi dengan senyuman

Dalam komentar Anda, Anda bertanya tentang tujuan m. Dengan anotasi tipe eksplisit, kami mungkin mendefinisikan go sebagai

...
  where go :: Map Integer [[Integer]] -> [Integer] -> Map Integer [[Integer]]
        go m l = insertWith' (++) (eq l) [l] m

Mencocokkan variabel dengan tipe, m adalah Peta yang telah kami kumpulkan sejauh ini, dan l adalah yang berikutnya Integer daftar yang ingin kita lemparkan ke keranjang yang sesuai. Ingat itu eq adalah argumen ke luar bucketBy.

Kami dapat mengontrol cara item baru masuk ke peta menggunakan insertWith'. (Berdasarkan konvensi, fungsi yang namanya diakhiri dengan tanda kutip adalah varian yang ketat.)

Itu (++) kombinator menambahkan daftar. Aplikasi eq l menentukan bucket yang sesuai untuk l.

Seandainya kami menulis l daripada [l], hasilnya pasti ingin

* Utama> bucket Jumlah penjumlahan x
[[0,3,2,1,1,2], [5,0], [1,9]]

tetapi kemudian kita kehilangan struktur daftar terdalam.

Kami sudah membatasi jenisnya bucketByhasil menjadi [[[α]]] dan dengan demikian jenis elemen Peta. Ucapkan butir selanjutnya l melipat adalah [1,2]. Kami ingin menambahkan, (++), ke beberapa jenis daftar lainnya [[Integer]], tetapi jenisnya tidak cocok.

* Utama> [[0,3], [2,1]] ++ [1,2]

<interaktif>: 1: 21:
    Tidak ada instance untuk (Num [t0])
      timbul dari literal `2 '
    Perbaikan yang memungkinkan: tambahkan deklarasi instance untuk (Num [t0])
    Dalam ekspresi: 2
    Dalam argumen kedua `(++) ', yaitu` [1, 2]'
    Dalam ekspresi: [[0, 3], [2, 1]] ++ [1, 2]

Pembungkus l mendapatkan kita

* Utama> [[0,3], [2,1]] ++ [[1,2]]
[[0,3], [2,1], [1,2]]

Generalisasi lebih lanjut

Anda mungkin berhenti dengan

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]
bucketBy eq = elems . foldl' go empty
  where go m l = insertWith' (++) (eq l) [l] m

atau bahkan

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]
bucketBy eq = elems . foldl' go empty
  where go :: Map Integer [[Integer]] -> [Integer] -> Map Integer [[Integer]]
        go m l = insertWith' (++) (eq l) [l] m

dan sangat senang karena menangani kasing dari pertanyaan Anda.

Anggaplah di jalan Anda memiliki daftar yang berbeda y didefinisikan sebagai

y :: [[Int]]
y = [[1,2],[2,1],[5,0],[0,3],[1,9]]

Meskipun definisi hampir identik dengan x, bucketBy tidak ada gunanya y.

* Utama> bucketJumlah total y

<interaktif>: 1: 15:
    Tidak bisa cocok dengan tipe yang diharapkan `Integer 'dengan tipe` Int' yang sebenarnya
    Jenis yang diharapkan: [[Integer]]
      Jenis yang sebenarnya: [[Int]]
    Dalam argumen kedua `bucketBy ', yaitu` y'
    Dalam ekspresi: bucketBy sum y

Anggap saja Anda tidak dapat mengubah jenisnya y untuk beberapa alasan. Anda dapat menyalin-dan-tempel untuk membuat lain berfungsi, katakan bucketByInt, di mana satu-satunya perubahan menggantikan Integer dengan Int dalam jenis anotasi.

Ini akan sangat, sangat tidak memuaskan.

Mungkin nanti Anda memiliki beberapa daftar string yang ingin Anda bucket sesuai dengan panjang string terpanjang di masing-masing. Di surga imajiner ini Anda bisa

* Utama> bucketBy (maksimum. Panjang peta) [["a", "bc"], ["d"], ["ef", "g"], ["hijk"]]
[[["d"]], [["ef", "g"], ["a", "bc"]], [["hijk"]]]]

Apa yang Anda inginkan sepenuhnya masuk akal: keranjang beberapa daftar hal-hal menggunakan kriteria yang diberikan. Namun sayang

* Utama> bucketBy (maksimum. Panjang peta) [["a", "bc"], ["d"], ["ef", "g"], ["hijk"]]

<interaktif>: 1: 26:
    Tidak dapat mencocokkan jenis 'Integer' yang diharapkan dengan tipe aktual `[a0] '
    Tipe yang diharapkan: Integer -> Integer
      Tipe yang sebenarnya: [a0] -> Int
    Dalam argumen pertama `peta ', yaitu` panjang'
    Dalam argumen kedua `(.) ', Yaitu` peta panjang'

Sekali lagi, Anda mungkin tergoda untuk menulis bucketByString, tetapi pada titik ini, Anda siap untuk pindah dan menjadi tukang sepatu sepatu.

Typechecker adalah temanmu. Kembali ke definisi Anda tentang bucketBy itu khusus untuk Integer daftar, cukup komentarkan jenis anotasi dan tanyakan jenisnya.

* Utama>: t bucketBy
bucketBy :: Ord k => (b -> k) -> [b] -> [[b]]

Sekarang Anda bisa mendaftar bucketBy untuk berbagai kasus di atas dan dapatkan hasil yang diharapkan. Anda sudah di surga tetapi tidak mengetahuinya!

Sekarang, sesuai dengan gaya yang baik, Anda memberikan anotasi untuk definisi tingkat atas bucketBy untuk membantu pembaca yang miskin, mungkin diri Anda sendiri. Perhatikan bahwa Anda harus menyediakan Ord kendala karena penggunaan insertWith', tipe siapa

insertWith' :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a

Anda mungkin ingin sangat eksplisit dan berikan anotasi untuk batin go, tetapi ini membutuhkan penggunaan ekstensi variabel tipe scoped.

{-# LANGUAGE ScopedTypeVariables #-}

import Data.List (foldl')
import Data.Map (Map,elems,empty,insertWith')

bucketBy :: forall a b. Ord b => (a -> b) -> [a] -> [[a]]
bucketBy eq = elems . foldl' go empty
  where go :: Map b [a] -> a -> Map b [a]
        go m l = insertWith' (++) (eq l) [l] m

Tanpa ekstensi dan dengan tipe anotasi

bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]

typechecker akan gagal dengan kesalahan formulir

    Tidak dapat menyimpulkan (b ~ b1)
    dari konteks (Ord b)
      terikat oleh tanda tangan jenis untuk
                 bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]
      di prog.hs: (10,1) - (12,46)
      `b 'adalah variabel tipe kaku yang terikat oleh
          tanda tangan jenis untuk
            bucketBy :: Ord b => (a -> b) -> [a] -> [[a]]
          di prog.hs: 10: 1
      `b1 'adalah variabel tipe kaku yang terikat oleh
           tanda tangan tipe untuk pergi :: Peta b1 [a1] -> a1 -> Peta b1 [a1]
           di prog.hs: 12: 9
    Dalam jenis kembalinya panggilan `eq '
    Dalam argumen kedua `insertWith '', yaitu` (eq l) '
    Dalam ekspresi: insertWith '(++) (eq l) [l] m

Ini karena typechecker memperlakukan b pada anotasi tipe dalam sebagai berbeda dan tipe yang sama sekali tidak berhubungan b1 meskipun pembaca manusia dengan jelas melihat niat bahwa mereka adalah tipe yang sama.

Membaca scoped type variables documentation untuk detailnya.

Satu kejutan kecil terakhir

Anda mungkin bertanya-tanya di mana lapisan luar kurung pergi. Perhatikan bahwa anotasi jenis digeneralisasikan dari

bucketBy :: ([Integer] -> Integer) -> [[Integer]] -> [[[Integer]]]

untuk

bucketBy :: forall a b. Ord b => (a -> b) -> [a] -> [[a]]

Perhatikan itu [Integer] itu sendiri tipe lain, diwakili di sini sebagai a.


5
2018-03-30 21:10



groupBy membagi daftar menjadi potongan-potongan elemen yang berdekatan yang memenuhi predikat yang diberikan. Karena dalam kasus Anda, itu [0,3] dipisahkan dari [1,2] dan [2,1], kelompok pertama hanya mencakup ini. Untuk mengumpulkan semua elemen dari daftar yang memiliki jumlah yang sama ke dalam satu grup, Anda memerlukan beberapa preprocessing, mis. dengan sortBy.

import Data.List
import Data.Function
import Data.Ord

groupBySum :: Num a => [[a]] -> [[[a]]]
groupBySum xss = groups
  where
    ys = map (\xs -> (sum xs,xs)) xss
    sortedSums = sortBy (comparing fst) ys
    groupedSums = groupBy ((==) `on` fst) sortedSums
    groups = map (map snd) groupedSums

4
2018-03-30 20:39



Dari peretasan:

Fungsi grup mengambil daftar dan mengembalikan daftar daftar sehingga penggabungan hasil sama dengan argumen.

groupBy adalah sama, kecuali bahwa Anda dapat menentukan tes kesetaraan Anda. Jadi, sejak di daftar masukan Anda [0,3] tidak bersebelahan dengan [1,2] atau [2,1], itu diletakkan sendiri.


3
2018-03-30 20:39