Get best of the week

Berapa banyak air yang bocor? Kami memecahkan masalah dengan moonwalk di Haskell

Sebuah tugas menarik berjalan di jaringan, yang diminta saat wawancara di Twitter.
Bayangkan bahwa Anda sedang melihat dinding berbagai ketinggian di profil. Hujan, di suatu tempat air tetap, di suatu tempat mengalir di tepi dinding karena perbedaan ketinggian. Tantangannya adalah untuk menentukan berapa banyak air yang tersisa di antara dinding.


Untuk mewakili urutan dinding, kita dapat menggunakan daftar:

type Height = Int

walls :: [Height]
walls = [2,5,1,2,3,4,7,7,6]

Untuk mengetahui volume air di bagian atas setiap dinding, kita perlu mengetahui tiga hal:

  1. Tinggi dinding saat ini
  2. Ketinggian tembok kiri tertinggi
  3. Ketinggian dinding kanan tertinggi

Kami menemukan dinding mana di bawah ini yang kanan atau kiri, kurangi ketinggian dinding saat ini dari yang tertinggi dan dapatkan volume airnya. Mari kita perhatikan lebih dekat sebuah contoh:



Bayangkan kita perlu menghitung volume air untuk dinding b. Ketinggian dinding kiri tertinggi - a , adalah 3 . Ketinggian dinding kanan tertinggi - s , adalah 2 . Karena dinding kiri yang lebih tinggi, air akan tumpah ke kanan, jadi kami menghitung dari ketinggian dinding kanan. Oleh karena itu, volume air untuk dinding b adalah = tinggi c - tinggi b = 2 - 1 = 1 .

Untuk memecahkan masalah ini dalam satu pass dari daftar tidak akan berhasil, tetapi akan berubah menjadi dua - semuanya adalah menghitung dinding kiri dan kanan atas. ( UPD :roman_kashitsynmenunjukkan bagaimana mungkin untuk satu, hanya tanpa memperoleh informasi tentang volume akumulasi air di setiap dinding)

Kita mulai dengan menghitung dinding kiri tertinggi untuk setiap dinding menggunakan efek negara:

type Volume = Int

--|        
themax :: Height -> State Height Height
themax h = modify (max h) *> get

-- |            
highest_left :: [Height] -> [Height]
highest_left walls = evalState (traverse themax walls) 0



Sekarang kita perlu menghitung dinding kanan tertinggi untuk masing-masing dinding, tetapi dalam hal ini kita perlu memulai penghitungan bukan di sebelah kiri, tetapi di sebelah kanan. Bagaimana bisa dalam hal ini? Balikkan daftar? Seperti yang bisa Anda tebak dari judul artikel ini, ada metode yang lebih menarik.

Fungsi Aplikatif Invers


Tipe yang menarik tinggal di paket transformer (dalam arti kata dan kiasan). Ini memungkinkan Anda untuk menjalankan efek aplikasi dalam urutan terbalik:

newtype Backwards f a = Backwards { forwards :: f a }

Bagaimana itu bekerja? Mari kita lihat lebih dekat contoh kelas Applicative untuk Mundur :

-- |          liftA2  <**>
instance Applicative t => Applicative (Backwards t) where
        pure = Backwards . pure
	Backwards f <*> Backwards x = Backwards ((&) <$> x <*> f)

& adalah aplikasi fungsi yang sama dengan argumen $ , tetapi dengan urutan argumen yang berbeda: pertama argumen, lalu fungsi:

f $ x = x & f

Karena kemalasan, pertama-tama kita menghitung komponen kedua dari rantai perhitungan aplikatif, dan hanya kemudian yang pertama - maka nama untuk jenis ini.

Pada transformer yang sama ada jenis lain yang menarik - Balikkan :

newtype Reverse f a = Reverse { getReverse :: f a }

Ini meluncurkan efek di Traversable secara terbalik menggunakan Mundur .

Dan sekarang kembali ke masalah awal kita dengan tipe ini.

Kami menguasai moonwalk


"Moonwalk" (dari moonwalk Inggris), atau "meluncur mundur", adalah teknik menari ketika seorang penari bergerak mundur, sambil mensimulasikan gerakan kakinya seolah berjalan maju. (Wikipedia).
Untuk menghidupkan trik semacam itu, kami mengambil fungsi yang sama dengan efek negara (seolah-olah kami akan maju, dari kiri ke kanan), yang kami gunakan untuk menghitung dinding kiri tertinggi:

-- |        
themax :: Height -> State Height Height
themax h = modify (max h) *> get

-- |    ,    :
highest_right :: [Height] -> [Height]
highest_right walls = getReverse $ evalState (traverse themax $ Reverse walls)

Sekarang kita memiliki segalanya untuk menghitung volume total air yang terakumulasi. Dari dinding kiri dan kanan tertinggi kami memilih yang terendah dan mengurangi ketinggian dinding dari itu - ini akan menjadi volume akumulasi air:

walls = [2,5,1,2,3,4,7,7,6]
let hls = highest_left walls = [2,5,5,5,5,5,7,7,7]
let hrs = highest_right walls = [7,7,7,7,7,7,7,7,6]
sum $ zipWith3 (\l x r -> min l r - x) hls walls hrs



Jadi, fungsi aplikatif membantu kami abstrak dari efek dan struktur data tertentu. Mereka memiliki beberapa kegunaan yang lebih menarik - kueri pengelompokan , pengurutan .

Kode sumber untuk solusi ini dapat ditemukan di sini . Teka-teki ini memiliki beberapa pendekatan yang lebih menarik yang dapat dilihat di sini .

More articles:


All Articles