Aplikasi dunia nyata dari prepromorfisme zygohistomorphic

156

Ya, ini :

{-#LANGUAGE TypeOperators, RankNTypes #-}
import Control.Morphism.Zygo
import Control.Morphism.Prepro
import Control.Morphism.Histo
import Control.Functor.Algebra
import Control.Functor.Extras
import Control.Functor.Fix
import Control.Comonad.Cofree

zygohistomorphic_prepromorphism 
  :: Functor f
  => Algebra f b
  -> GAlgebra f (ZygoT (Cofree f) b) a 
  -> (f :~> f) 
  -> FixF f 
  -> a
zygohistomorphic_prepromorphism f 
  = g_prepro (distZygoT (liftAlgebra f) (distHisto id))

Ya, saya tahu itu lelucon ( HHOS ). Saya mencari contoh dunia nyata untuk nilai retas sederhana dan yang terakhir, tetapi tidak kalah pentingnya, untuk menambahkannya ke wiki yang mengatakan "Ini adalah cara idiomatik untuk mengekspresikan XYZ". Saya akan memberi hadiah jika Anda gagal menemukan solusi. Jika Anda benar-benar bingung dengan apa yang mereka bicarakan, Edward memposting penjelasan singkat tentang reddit.

Jawaban yang Layak harus:

  1. melakukan sesuatu yang setidaknya secara jarak jauh dan bermanfaat secara teori. Yaitu, jawaban yang mengurangi untuk idkeluar.

  2. gunakan semua fitur skema, tidak ada id, atau const, atau yang setara.

  3. tidak sama baiknya diungkapkan dengan lipatan vanilla sederhana atau semacamnya, jadi jangan hanya menerapkan productcara berkelok-kelok.

Poin bonus akan diberikan kepada:

  • Masalah atau algoritma yang terkenal

  • dipecahkan, masing-masing diungkapkan, dengan cara yang tidak biasa yang menguntungkan

  • kejelasan dan / atau kinerja

  • dan / atau nilai retas

  • dan / atau lulz, kira-kira dalam urutan itu, juga

  • jawaban tingkat tinggi (yay demokrasi)

Harap perhatikan juga jawaban Edward di bawah ini. Apa implementasi ZHPM yang Anda gunakan adalah pilihan Anda.

haskell functional-programming category-theory sabun batang
sumber
5
Jika Anda termasuk IOdalam tumpukan Anda, kami bisa menggunakan launchMisslesfungsi terkenal SimonPJ . Tapi saya kira inti dari semua omong kosong abstrak super-murni adalah untuk menghindari kemungkinan hal-hal seperti itu.
Yitz
6
Yah, abisa apa saja, jadi jangan ragu untuk membangun nilai IO yang secara strategis meluncurkan rudal berdasarkan penilaian data input Anda.
barsoap
49
Saya mengklik pertanyaan ini karena saya tidak tahu apa yang sedang Anda bicarakan. +1 Pak, +1
Drew
7
Seseorang yang ingin menggunakan semua komponen akan melakukannya dengan baik untuk secara manual menuliskan apa yang meluas menjadi rekursi prepromorfisme zygohistomorphic, dan kemudian mencari masalah yang membutuhkan semua pola ini; loop imperatif cenderung melakukan pelacakan rumit sewenang-wenang, sehingga mungkin merupakan tempat yang baik untuk melihat.
Edward Z. Yang
3
dan yang lebih penting - Apakah itu berbaur ?! (sangat menyesal, tidak bisa menahan)
n00b

Jawaban:

52

Sharon Curtis dan Shin-Cheng Mu memiliki Mutiara Fungsional menggunakan zygomorphisms untuk menemukan segmen padat maksimal (generalisasi jumlah segmen maksimum). Zygomorphisms tampaknya sangat cocok untuk masalah sliding window begitu Anda terbiasa.

http://www.iis.sinica.edu.tw/~scm/2010/functional-pearl-maximally-dense-segments/

Saya akan mencalonkan penulis untuk kredit tambahan karena mereka telah menghindari penggunaan functor Mu titik tetap.

stephen tetley
sumber
Dari membaca sepintas lalu, saya pikir saya melihat bagaimana mereka menggunakan histo ketika melacak DRSP (dalam arti yang sama seperti yang sederhana foldrdapat melihat daftar yang sudah dibuat), tetapi prepro tidak segera jelas bagi saya. Bisakah Anda menguraikan? (dan, jika mungkin, berikan kode pendek + manis yang bisa kita tempel ke halaman wiki?)
barsoap
3
Kode tersedia dari tautan di bawah errata pada halaman arahan. Definisi aktual zygomorphism ada di file Main.hs - berbeda dengan definisi di koran. Itu adalah "hanya" zygomorphism bukan "prepromorphisms zygohistomorphic" - zygomorphism adalah hal terdekat yang pernah saya lihat dengan penggunaan dunia nyata. Meskipun ada slide oleh Jevgeni Kabanov menggunakan histomorfisme untuk pemrograman dinamis: cs.ioc.ee/~tarmo/tday-viinistu/kabanov-slides.pdf
stephen tetley
39

Catatan, tanda tangan ini telah berubah, karena itu tidak cukup umum, dan saya memasukkannya (sebagai lelucon) dalam paket skema rekursi saya .

zygoHistoPrepro 
  :: (Unfoldable t, Foldable t) 
  => (Base t b -> b) 
  -> (forall c. Base t c -> Base t c) 
  -> (Base t (EnvT b (Stream (Base t)) a) -> a) 
  -> t
  -> a

Implementasinya juga disederhanakan.

zygoHistoPrepro f = gprepro (distZygoT f distHisto)

Dan dari implementasi baru harus jelas bagaimana menerapkan prepromorfisme zygohistomorphic umum , dengan melonggarkan kendala bahwa Anda memiliki (Base t)-Branchingaliran, melalui penggunaan distGHistosebagai gantinya.

Edward KMETT
sumber
2
Ah ya cukup jelas.
Ben Longo