Czy ta właściwość funktora jest silniejsza niż monada?

Question

Czy ta właściwość funktora jest silniejsza niż monada?

Zastanawiając się, jak uogólnić monady, wymyśliłem następującą właściwość funktora F:

inject :: (a -> F b) -> F(a -> b)

W 1997 roku, w wyniku przekształcenia, doszło do powstania tzw. " a " i "b".]}

W przypadku braku lepszej nazwy nazywam funktor F bindable jeśli istnieje naturalna transformacja inject pokazana powyżej.

Główne pytanie brzmi, czy ta właściwość jest już znana i ma nazwę, i jak jest ona związana z innymi dobrze znanymi właściwościami funktorów (takimi jak jako, że jest aplikacyjny, monadyczny, spiczasty, trawersowalny itp.)

Motywacja dla nazwy "bindable" pochodzi z następującego rozważania: Załóżmy, że M jest monadą, A F jest funktorem "bindable". Wtedy mamy następujący morfizm naturalny:

fbind :: M a -> (a -> F(M b)) -> F(M b)

Jest to podobne do monadycznego "bind",

bind :: M a -> (a -> M b) -> M b

Z tym, że wynik jest ozdobiony funktorem F.

Ideą fbind było to, że uogólniona operacja monadyczna może dać nie tylko jeden wynik M b ale "funktor-ful" takich wyników. Chcę wyrazić sytuację, gdy operacja monadyczna daje kilka "nici obliczeń", a nie tylko jedną; każda" część obliczeń " jest ponownie obliczeniami monadycznymi.

Zauważ, że każdy funktor F ma morfizm

eject :: F(a -> b) -> a -> F b

, które jest converse do "wstrzyknąć". Ale nie każdy funktor F ma "inject".

Przykłady funkcji, które mają "inject": F t = (t,t,t) lub F t = c -> (t,t) gdzie c jest typem stałym. Funktory F t = c (funktor stały) lub F t = (c,t) nie są " bindable "(tzn. nie mają"inject"). Funkcja kontynuacyjna F t = (t -> r) -> r również nie wydaje się mieć inject.

Istnienie "inject" można sformułować w inny sposób. Rozważmy funktor "reader" R t = c -> t, gdzie c jest typem stałym. (Ten funktor jest aplikacyjny i monadyczny, ale nie o to chodzi.) Właściwość "inject" oznacza wtedy R (F t) -> F (R t), innymi słowy, że r komunikuje się z F. zauważ, że nie jest to to samo, co wymóg, aby f był przemienny; że byłoby F (R t) -> R (F t), który jest zawsze spełniony dla dowolnego funktora F względem R.

Do tej pory udało mi się pokazać, że "inject" oznacza "fbind" dla każdej monady M.]}

Dodatkowo pokazałem, że każdy funktor F, który ma "inject" będzie miał również te dodatkowe właściwości:

jest wskazywany

point :: t -> F t

Jeśli F jest "bindowalne" i aplikatywne, to F jest również monad
Jeśli F I G są "bindowalne" to tak jest funkcja pary F * G (ale nie F + G)
Jeśli F jest "bindowalne", A A jest dowolnym profunktorem, to funktor (pro) G t = A t -> F t jest bindowalny
Funkcja tożsamości jest bindowalna.

Pytania otwarte:

Czy właściwość bycia "bindowalnym" jest równoznaczna z innymi dobrze znanymi właściwościami, czy też jest to nowa właściwość funkcji, która zwykle nie jest brana pod uwagę?
Czy istnieją jakieś inne właściwości funktora "F", które wynikają z istnienia "zastrzyku"?
Czy potrzebne są jakieś przepisy do "zastrzyku", czy to by się przydało? Na przykład możemy wymagać, aby R (F t) był izomorficzny z F (R t) w jednym lub obu kierunkach.

16

haskell functional-programming monads category-theory functor

Author: winitzki, 2016-09-23

Source

1 answers

score 8 · Accepted Answer

Aby poprawić nieco terminologię, proponuję nazwać te funktory " sztywnymi "zamiast"bindowalnymi". Motywacja do powiedzenia "sztywny" zostanie wyjaśniona poniżej.

Funktor fnazywa się sztywnym, jeśli ma metodę inject, Jak pokazano. Zauważ, że każdy funktor ma metodę eject.

class (Functor f) => Rigid f where
  inject :: (a -> f b) -> f(a -> b)

  eject :: f(a -> b) -> a -> f b
  eject fab x = fmap (\ab -> ab x) fab

Prawo "nondegeneracy" musi posiadać:

eject . inject = id

Sztywny funktor jest zawsze wskazywany:

instance (Rigid f) => Pointed f where
  point :: t -> f t
  point x = fmap (const x) (inject id)

Jeśli sztywny funktor jest aplikowalny, to jest automatycznie monadyczny:

instance (Rigid f, Applicative f) => Monad f where
  bind :: f a -> (a -> f b) -> f b
  bind fa afb = (inject afb) <*> fa

Właściwość bycia sztywnym nie jest porównywalna (ani słabsza, ani silniejsza) niż właściwość bycia monadycznym: jeśli funktor jest sztywny, nie wydaje się, aby wynikało to z tego, że jest automatycznie monadyczny (chociaż nie znam konkretnych kontrprzykładów w tym przypadku). Jeśli funktor jest monadyczny, to nie wynika z tego, że jest sztywny (istnieją kontrprzykłady).

Podstawowe kontrprzykłady funktorów monadycznych, które nie są sztywne, to Maybe i List. Są to funktory, które mają więcej niż jeden konstruktor: z reguły takie funktory nie są sztywne.

Problem z implementacją inject dla Maybe polega na tym, że inject musi przekształcić funkcję typu a -> Maybe b w Maybe(a -> b), podczas gdy Maybe ma dwa konstruktory. Funkcja typu a -> Maybe b może zwracać różne konstruktory dla różnych wartości a. Mamy jednak skonstruować wartość typu Maybe(a -> b). Jeśli dla pewnej a dana funkcja wytwarza Nothing, to nie mamy b więc nie możemy stworzyć funkcji całkowitej a->b. Tak więc nie możemy zwrócić Just(a->b); jesteśmy zmuszeni zwracać Nothing tak długo, jak dana funkcja wytwarza Nothing nawet dla jednej wartości a. Nie możemy jednak sprawdzić, czy dana funkcja typu a -> Maybe b wytwarza Just(...) dla wszystkich wartości a. Dlatego jesteśmy zmuszeni do powrotu Nothing we wszystkich przypadkach. Nie będzie to spełniało prawa nieegeneracjonizmu.

Możemy więc zaimplementować inject jeśli f t jest kontenerem o "stałym kształcie" (posiadającym tylko jeden konstruktor). Stąd nazwa "sztywny".

[106]}innym wyjaśnieniem, dlaczego sztywność jest bardziej restrykcyjna niż monadyjność, jest rozważenie naturalnie zdefiniowanego wyrażenia [107]}

(inject id) :: f(f a -> a)

Gdzie id :: f a -> f a. To pokazuje, że możemy mieć f-algebrę f a -> a dla dowolnego typu a, o ile jest ona zawinięta wewnątrz f. Nie jest prawdą, że każda monada ma algebrę; na przykład różne "przyszłe" monady, jak również monada IO opisują obliczenia typu f a, które nie pozwalają nam wyodrębnić wartości Typ {[23] } - nie powinniśmy mieć metody typu f a -> a, nawet jeśli jest ona zawinięta wewnątrz f-kontenera. To pokazuje, że monady "przyszłe" i monady IO nie są sztywne.

Właściwością, która jest ściśle silniejsza niż sztywność jest dystrybutywność z jednego z pakietów E. Kmetta. Funktor f jest dystrybutywny, jeśli możemy zamienić kolejność jak w p (f t) -> f (p t) na dowolny funktor p. Sztywność jest taka sama jak możliwość wymiany kolejność tylko w odniesieniu do funkcji "reader" r t = a -> t. Tak więc wszystkie funkcje rozdzielcze są sztywne.

Wszystkie funktory dystrybutywne muszą być reprezentowalne, co oznacza, że są równoważne funktorowi "reader" c -> t z pewnym ustalonym typem c. Jednak nie wszystkie sztywne funktory są reprezentowalne. Przykładem może być funktor g zdefiniowany przez

type g t = (t -> r) -> t

Funktory g nie są równoważne c -> t ze stałym typem c.

Kolejne przykłady sztywnych funktory, które nie są reprezentowalne (tzn. nie są "dystrybutywne") są funktorami postaci a t -> f t, gdzie a jest dowolnym kontrofunktorem, a f jest funktorem sztywnym. Ponadto iloczyn kartezjański i skład dwóch funkcji sztywnych są ponownie sztywne. W ten sposób możemy wytworzyć wiele przykładów sztywnych funktorów w klasie wykładniczo-wielomianowej funktorów.

Moja odpowiedź na jaki jest ogólny przypadek funkcji promocji QuickCheck? wymienia również konstrukcje sztywnych funktorów.

W końcu znalazłem dwa przypadki użycia dla sztywnych funktorów.

Pierwszy przypadek użycia był pierwotną motywacją do rozważenia funkcji sztywnych: chcielibyśmy zwrócić kilka wyników monadycznych jednocześnie. Jeśli m jest monadą i chcemy mieć {[63] } jak pokazano w pytaniu, musimy f być sztywni. Następnie możemy zaimplementować fbind jako

fbind :: m a -> (a -> f (m b)) -> f (m b)
fbind ma afmb = fmap (bind ma) (inject afmb)

Możemy użyć fbind aby mieć operacje monadyczne, które zwracają więcej niż jeden wynik monadyczny (lub, ogólnie rzecz biorąc, sztywny funktor-ful wyników monadycznych), dla dowolnego monad m.

Drugi przypadek użycia wyrasta z następującego rozważenia. Załóżmy, że mamy program p :: a, który wewnętrznie używa funkcji f :: b -> c. Teraz zauważamy, że funkcja f jest bardzo powolna i chcielibyśmy refaktorować program, zastępując f monadyczną "przyszłością" lub "zadaniem", lub ogólnie strzałką Kleisli f' :: b -> m c dla niektórych monad m. Oczywiście oczekujemy, że program p będzie stać się również monadycznym: p' :: m a. Naszym zadaniem jest refaktor p do p'.

Refaktoryzacja przebiega w dwóch krokach: najpierw refaktoryzujemy program p tak, że funkcja f jest jawnie argumentem p. Załóżmy, że zostało to zrobione, tak że teraz mamy p = q f gdzie

q :: (b -> c) -> a

Po drugie, zamieniamy f na f'. Teraz Zakładamy, że q i f' są podane. Chcielibyśmy skonstruować nowy program q' typu

q' :: (b -> m c) -> m a

Tak, że p' = q' f'. Pytanie brzmi, Czy możemy zdefiniować ogólny kombinator, który refaktoruje q na q',

refactor :: ((b -> c) -> a) -> (b -> m c) -> m a

Okazuje się, że refactor może być skonstruowany tylko wtedy, gdy m jest sztywnym funktorem. Próbując zaimplementować refactor, znajdujemy zasadniczo ten sam problem, jak wtedy, gdy próbowaliśmy zaimplementować inject dla Maybe: otrzymujemy funkcję f' :: b -> m c, która może zwracać różne monadyczne efekty m c dla różnych b, ale musimy skonstruować {98]}, która musi reprezentować tę samą funkcję. efekt monadyczny dla wszystkich b. To nie może działać, na przykład, jeśli m jest monadą z więcej niż jednym konstruktorem.

Jeśli m jest sztywne (i nie musimy wymagać, aby m była monadą), możemy zaimplementować refactor:

refactor bca bmc = fmap bca (inject bmc)

Jeśli m nie jest sztywny, nie możemy refaktorować dowolnych programów. Do tej pory widzieliśmy, że monada kontynuacyjna jest sztywna, ale monady "przyszłościowe" i monada {43] } nie są sztywne. To znowu pokazuje, że sztywność jest w pewnym sensie silniejsza własność niż monadyczność.