Haskell funktora domniemanych prawo

Question

Typeclassopedia mówi.

„Podobne rozumowanie pokazuje również, że każdy przypadek funktora spełniających pierwsze prawo (FMap id = Id) automatycznie spełniają drugie prawo, a W praktyce oznacza to, że tylko pierwsze prawo musi zostać sprawdzone (zwykle poprzez bardzo prostą indukcję), aby upewnić się, że instancja Funktora jest ważna. "

Jeśli tak, to dlaczego wymieniamy nawet drugie prawo dotyczące funktora?

Law 1: fmap id = id 
Law 2: fmap (g . h) = (fmap g) . (fmap h) 

Answer 1

a ja nie mogę dać dowodu, wierzę w to, że mówi się o tym, że z powodu parametricity system typów egzekwuje drugie prawo tak długo, jak obowiązuje pierwsze prawo. Powodem określenia obydwu reguł jest to, że w bardziej ogólnym ustawieniu matematycznym możesz mieć jakąś kategorię C, gdzie jest całkowicie możliwe zdefiniowanie dla siebie "odwzorowania" z siebie (tj. Pary endofunkcji na Obj (C) i hom (C) odpowiednio), która spełnia pierwszą zasadę, ale nie wykonuje się drugą zasadę, a zatem nie stanowią funktora.

Pamiętaj, że Functor s w Haskell są endofunctors od kategorii Hask, a nawet wszystko, że matematycznie być uważane za endofunctor na HASK może być wyrażona w Haskell ... ograniczenia parametrycznych polimorfizmu wykluczać będącego potrafi określić funktor, który nie zachowuje się jednolicie dla wszystkich obiektów (typów), które mapuje.

Na podstawie this thread, ogólna zgoda wydaje się, że drugie prawo wynika z pierwszej dla instancji Haskell Functor.Edward Kmett says,

Biorącfmap id = id, fmap (f . g) = fmap f . fmap gwynika z wolnego twierdzenia o FMapy.

Zostało to opublikowane w formie papierowej dawno temu, ale zapominam, gdzie.

Answer 2

Powiedziałbym drugie prawo nie jest wymienione z powodów ważności, ale raczej jako ważny miejscu:

Pierwsze prawo mówi, że mapowanie funkcji tożsamości na każdej pozycji w pojemniku nie ma żadnego efektu. Drugi mówi, że odwzorowanie składu dwóch funkcji na każdy element w kontenerze to tak samo jak pierwsze odwzorowanie jednej funkcji, a następnie odwzorowanie drugiej. --- Typeclassopedia

(nie mogę zrozumieć, dlaczego ta pierwsza ustawa zakłada drugie prawo, ale nie jestem wykwalifikowanym Haskeller - jego chyba oczywiste, gdy wiesz, co się dzieje)

Answer 3

It wydaje się, że zrealizowano quite recently, że ustawa 2 wynika z prawa 1. Tak więc, kiedy dokumentacja została pierwotnie napisana, prawdopodobnie uważano ją za niezależny wymóg.

(Osobiście jestem nie przekonuje argument, ale ponieważ nie miałem czasu, aby opracować szczegóły siebie, daję mu przywilej wątpliwości tutaj).

Answer 4

Używając seq, możemy napisać instancję, która spełnia pierwszą regułę, ale nie drugą.

data Foo a = Foo a 
    deriving Show 

instance Functor Foo where 
    fmap f (Foo x) = f `seq` Foo (f x) 

Możemy sprawdzić, czy ta spełnia pierwsze prawo:

fmap id (Foo x) 
= id `seq` Foo (id x) 
= Foo (id x) 
= Foo x 

jednak łamie drugie prawo:

> fmap (const 42 . undefined) $ Foo 3 
Foo 42 
> fmap (const 42) . fmap undefined $ Foo 3 
*** Exception: Prelude.undefined 

powiedział, że zwykle ignorują takie patologiczne przypadki.