Soru Haskell: Bir Functor olmayan (ya da Traversable değil) Katlanabilir bir örnek?


bir Foldable örneğin bir çeşit kapsayıcı olabilir ve bu nedenle büyük olasılıkla bir Functor de. Aslında, bu diyor

bir Foldable türü de bir konteynırdır (sınıf teknik olarak gerektirmezse de) Functor, ilginç Foldablehepsi Functors).

Yani bir örnek var Foldable doğal olarak değil Functor ya da Traversable? (belki de Haskell wiki sayfası özledim :-))


44
2017-12-02 16:06


Menşei




Cevaplar:


İşte tam bir parametrik örnek:

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird değil Functor Çünkü a negatif bir pozisyonda oluşur.


50
2017-12-02 16:41



Oh iyi! Bunu düşünmemiştim bile. Herhangi bir varsa merak ediyorum Foldable standart-ish kütüphanelerinde, Functor kontravaryans nedeniyle? - C. A. McCann
Belli uzantılar ve eşanlamlı kelimelerle yapabileceğinizi düşünüyorum. - PyRulez
Ne dersin instance Functor Weird where fmap fn (Weird a aa) = Weird (fn (aa a)) id? - Nikita Volkov
@NikitaVolkov Güzel olan! Ancak, functor yasalarını tatmin etmemektedir. fmap id == id - Sjoerd Visscher
@SjoerdVisscher bağlıdır. Teknik konuşma Free monad yasalarını karşılamıyor w.r.t. tanımsal eşitlik ve aynı şekilde pipesuygun yasaları yalnızca observe prizma. Dolayısıyla, tanımsal eşitlik, en mantıklı / kullanışlı / doğal olanı olmayabilir (örneğin, tanımsal eşitliğin, kullandığınız bir dilin can sıkıcı bir eseri haline geldiği bölümleri kullanın). Şimdi senin Weird çok benziyor Coyoneda. Ve senin foldMap çok benzer ve özel bir semantik var: davranır Weird Tek elemanlı bir konteyner olarak ve her zaman saklanan fonksiyonu uygular. - user3237465


İşte kolay bir örnek: Data.Set.Set. Kendin için gör.

Uzmanlık türlerini incelerseniz, bunun nedeni açık olmalıdır. fold ve map için tanımlanan işlevler Set:

foldr :: (a -> b -> b) -> b -> Set a -> b

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b

Veri yapısı dahili olarak bir ikili arama ağacına dayandığından Ord elemanlar için kısıtlama gereklidir. Functor Örnekler herhangi bir eleman türüne izin vermelidir, bu yüzden geçerli değildir, alas.

Katlama, diğer taraftan, her zaman özet değerini üretmek için ağacı tahrip eder, dolayısıyla katın ara sonuçlarını sıralamaya gerek yoktur. Katlama aslında yeni olsa bile Set, tatmin edici Ord Kısıtlama işlevi, katlamanın kendisine değil, katına geçirilen birikim işlevinin üzerindedir.

Aynı şey tam olarak parametrik olmayan herhangi bir konteyner tipi için geçerli olacaktır. Ve faydaları göz önüne alındığında Data.SetBu, "ilginç" hakkında alıntı yaptığınız bir açıklama yapar. FoldableSanırım biraz şüpheli sanırım!


42
2017-12-02 16:16



Bu gerçekten bir örneğidir. Foldable hangi yapılamaz ki Functor. Ancak, bu, Haskell'in tip sisteminin ifade edemediği gerçeğinden dolayı daha fazla görünüyor ”Set sadece anlamlıdır Ord türleri ve bir şey yapmak Functor sadece tanımlamak gerekiyor fmap Başka bir yerde tanımlandığı gibi, mantıklı olan türler için, Set ve Functor temsil etmek. Her neyse, örnek için teşekkürler. :-) - Prateek
@Prateek: Evet ve hayır. Tam olarak parametrik olmak, neye özgüdür Functor temsil eder. Bununla birlikte, standart Haskell'den (gerçekte GHC tarafından desteklenen tam tip sistem dahil olmak üzere) daha belirgin bir tip sistem, burada istenen türden olan “bazı sınıf tiplerinde tam olarak parametrik” ifade edebilirdi. - C. A. McCann
@Prateek: Daha matematiksel anlamda, Functor sadece belirli türden funktörleri kapsar, tüm Haskell tiplerinin kategorisinden kendisinin uygun bir alt kategorisine. Yalnızca alt kategorilerde çalışan ya da başka bir şekilde mantıklı olabilecek diğer şeyleri ifade edemez. Dedi ki, Sjoerd Visscher'ın örneği benimkilerden daha ilginç ve daha ezoterik kalıyor. :] - C. A. McCann
Eğer yaşamak istiyorsak Set sadece için çalışan şeyler Ord türleri (matematiğin içindeki kümelerin böyle bir kısıtlaması olmamasına rağmen), aynı kusurları tolere etmeye istekli olmalıyız. Functor çok. - Prateek
oldukça eminim Set doğal olarak gerektirmez Ord her zaman, sadece "teftiş" yaptığınız zaman, uzunluğunu kontrol etmek, bir ip olarak göstermek veya minimum / maksimum elementi vb. Set bazı durumlarda (ör. (+) <$> set) yok Ordve o zaman sadece o var ne zaman o var yoğunlaşma ve kendini yeniden düzenlemek Ord Kısıtlama (yani evet, bu standart Haskell'de yapılamaz, ama ben daha çok teorik / matematik açısından düşünüyorum). O zaman sahip olabilirsin Set doğru ol Functorve hatta bir Applicative ve bir Monad. - semicolon


Okuma Güzel katlama  Farkettim ki herhangi Foldable yapılabilir Functor içine sarmak

data Store f a b = Store (f a) (a -> b)

Basit bir akıllı denetçi ile:

store :: f a -> Store f a a
store x = Store x id

(Bu sadece bir varyantıdır. mağaza comonad veri türü.)

Şimdi tanımlayabiliriz

instance Functor (Store f a) where
    fmap f (Store x g)   = Store x (f . g)

instance (F.Foldable f) => F.Foldable (Store f a) where
    foldr f z (Store x g)    = F.foldr (f . g) z x

Bu şekilde, ikisini de yapabiliriz Data.Set.Set ve Sjoerd Visscher'ın Weird Bir functor. (Ancak, yapının değerlerini hatırlamaması nedeniyle, üzerinde kullandığımız işlev çok fazla verimsiz olabilir. fmap karmaşıktır.)


Güncelleştirme: Bu aynı zamanda, bir katlanabilir, ancak katlanabilen bir functor olan bir yapının bir örneğini sağlar. Yapmak Store çaprazlanabilir, yapmamız gerekecek (->) r çaprazlanabiliyorsa. Yani uygulamak zorundayız

sequenceA :: Applicative f => (r -> (f a)) -> f (r -> a)

Hadi alalım Either b için f. O zaman uygulamak zorundayız.

sequenceA' :: (r -> Either b a) -> Either b (r -> a)

Açıkçası, böyle bir işlev yoktur. ecinni). Yani ne fark edemeyiz sequenceA.


22
2017-10-15 13:21



Mağaza veri türü, Coyoneda olarak da bilinen herhangi bir türdeki kurucu üzerinde tam olarak serbest eğridir (hackage.haskell.org/package/kan-extensions-4.2.3/docs/...). - Kris Nuttycombe
@KrisNuttycombe Tam olarak değil. Coyoneda varoluşsal olarak nicelendirilir Store değil. - Carl