Ce cărți FP mai citiți?


#21

De-aia nu mi-au plăcut definițiile unityped ale lui Cheplyaka, conduc la confuzii din astea. Și până și el recunoaște în articol că return și bind pot avea tipul U. Eu aș zice că pot avea doar tipul U, iar ăsta e alt motiv pentru care nu-mi place sintagma/perspectiva unityped — e corectă, dar nu ajută absolut deloc.

return :: U
(>>=) :: U

Ceea ce contează, de fapt, e comportamentul la runtime, iar ăla e dictat de legile monadice, care legi nu pot fi verificate static (poate or exista excepții pentru anumite instanțe monadice), ceea ce le face utile și într-un limbaj dinamic.

Am două neînțelegeri legate de ce-ai zis aici.

Din câte știu, Functor și Monad din Haskell nu lucrează la nivelul categoriei Hask. De exemplu, în Hask, Int și String sunt obiecte. Dar un fmap între List Int și List String vorbește despre categoria cu obiecte din Int și categoria cu obiecte din String, nu? Sau poți vedea Functor ca un endomorfism în Hask?

Apoi, dacă -> e din meta-limbaj, e și f din meta-limbaj? Dacă da, descrie f atunci o funcție din limbajul modelat?

Oricum, din nou nu știu la ce ajută. Până la urmă motivul pentru care e considerat util conceptul de monadă în programare e faptul că ne lasă să raționăm despre efecte. Efectele (de la runtime) contează, nu tipurile care descriu funcția. Tipurile sunt utile, sigur, îți ghidează implementarea și te asigură că n-ai făcut mici greșeli, dar nu sunt totul.

Acum, legat de instanțele monadice Church-encoded ale lui Cheplyaka. Sunt faine și o demonstrație clară că n-ai nevoie de tipuri (doh).

O dificultate apare, însă, atunci când vrei să scrii o funcție care depinde de o instanță monadică oarecare, de pildă Traversable.sequence:

sequence :: Monad m => t (m a) -> m (t a)

De abia acum putem vorbi despre type-classes și dicționare. Aici va trebui ca implementarea în lambda calculus să primească un Church-encoded record cu funcțiile monadice ale instanței — lucru care poate fi decis la runtime (spre deosebire de Haskell, unde type-class instance resolution se întâmplă la compile-time, fiind dictată de tipuri). Iar lumea nu vrea să trimită parametri.

Acum, majoritatea limbajelor dinamice sunt și OOP, iar acolo avem deja un dicționar atașat fiecărui obiect, numit uneori vtable și folosit pentru dynamic (virtual în terminologie C++) method dispatch. Deci atunci când avem obiecte, acel vtable poate lua rolul de type-class dictionary. Sunt type-classes pentru care lucrul ăsta merge foarte bine, de pildă Functor. Implementezi pe acel obiect metoda map și orice altă funcție care depind în mod generic de Functor poate apela map, bazându-se pe duck-typing.

Monad impune niște probleme, însă. Să implementezi bind/flatMap/join ca metodă pe obiect, similar cu map, merge ok. Dificultăți apar la return care în Haskell se folosește de return-type polymorphism. Pentru problema asta rezolvarea nu mai e la fel de clară, că return nu aparține unui obiect, ci clasei care a definit acel obiect. În Python un workaround ar putea fi să definești return ca @staticmethod, iar codul client să apeleze instance.__class__.return(a) (ignorând faptul că return e keyword). Dacă n-ai __class__ cum are Python, atunci ai putea cere ca instanța să expună un membru către clasa care o definește: instance.definer.return(a). Sau poți să renunți, să zici ceva gen instance.return(a) și aia e :slight_smile: Haters gonna hate, dar legile sunt respectate.


#22

Ba lucrezi, chiar și în alea statically typed. Church-encoding e un alt nume pentru fold, iar ambele pot fi văzute ca instanțe de Visitor pattern. Pattern pe care știu că l-ai găsit util foarte recent :stuck_out_tongue:

Singura diferență e de sintaxă. Lambda calculus e mai concisă și greu de citit, dar uite. Church-encoded booleans:

true = λt.λf.t
false = λt.λf.f

Smalltalk conditionals:

(x > y) ifTrue: [ x print ]
        ifFalse: [ y print ]

Rezultatului Boolean al evaluării x > y i se trimit/cheamă două mesaje/metode: ifTrue și ifFalse. Ambele primesc un bloc (aka funcție) reprentând continuarea execuției programului, unul pentru cazul true, celălalt pentru cazul false. Care dintre ele e apelat depinde de dynamic dispatch. Dacă rezulatul e obiectul true, atunci mesajul ifTrue evaluează blocul primit, iar mesajul ifFalse, nu. Invers pentru cazul false.

Smalltalk folosește mesaje pentru treaba asta, dar la fel de bine ar putea ca acele ifTrue și ifFalse să fie named parameters. Sau le poți grupa într-un alt obiect și ai fix Visitor pattern.


#23

Sigur, mă refeream la faptul că limbajele pun la dispoziție unelte mai eficiente pentru descrierea de tipuri.
Și evident că atunci când n-ai de ales, apelezi la Church-encoding.

De exemplu o astfel de situație am văzut să apară în Fantasy-Land, unde tailRecM are nevoie de un Either, dar Either nu-i descris în JS sau Fantasy-Land (scopul proiectului fiind să se pună la dispoziție doar protocolul menit pentru interoperabilitate și nu o implementare concretă). Astfel că semnătura este:

chainRec<A, B>(f: <C>(next: (a: A) => C, done: (b: B) => C, a: A) => F<C>, a: A): F<B>

Asta în loc de:

chainRec<A, B>(f: (a: A) => F<Either<A, B>>, a: A): F<B>

Evident că trebuie să fi masochist să accepți prima variantă în loc de a doua și o faci doar atunci când n-ai de ales.


#24

@igstan In Hask, toate tipurile sunt obiecte (String, Int, List Int, List String, Int -> String, etc). Functorul din Haskell este defapt un Endofunctor in Hask, si are doua componente: constructorii (care sunt morfisme in Hask intre a si List a) si fmap.


#25

Tot vorbind de Fantasy-Land, s-au încăpățânat să descrie map și bind / flatMap (în vocabularul lor chain) ca și metode în loc de funcții pe un dicționar ce conține și return și este absolut oribil.

Motivul este că pentru a introduce tipuri pentru așa ceva ai nevoie de F-bounded polymorphism. Scala o poate face, dar cu costuri mari, tipul de date rezultat fiind aproape inutil pentru cod polimorfic și alte limbaje gen TypeScript (relevant în contextul JS) nu pot. Am mai scris despre asta, vezi aici.

Și cu JavaScript poți zice că nu-ți pasă extraordinar de tare, dar uite că TypeScript și Flow s-au întâmplat. Plus că spec-ul are complexitate extra pentru că introduce conceptul de type representative (aka companion object din Scala) într-un mod foarte superficial de altfel.


#26

Mersi, are sens. Încă nu-mi dau seama cum s-ar aplica pentru un unityped language. Poate că monada unityped descrisă de @dan.oneata e validă, dar nu utilă practic.


#27

Nu imi este clar inca ce assumptions sunt despre limbaj. Ca sa poti scrie a -> a -> a, presupunem ca limbajul untiped are conceptul de aritate macar. Mergem pe premisa asta?

Daca nu, atunci nu are sens sa spunem nici asta, return, bind, join etc au toate acelasi tip: a.

In alta ordine de idei, la fel cum encodam un tip (folosind constructorii), nu am putea encoda si monad? Ma gandesc la ceva de genul:

λmap.λjoin.λa.λf.join (map f a)

#28

Îmi pare rău că am creat atâta confuzie :frowning: Multe din lucrurile acestea nu-mi sunt clare (mai ales partea de type theory) și probabil chiar am “bătut câmpii”. Vă mulțumesc pentru corecții și observații; o să mai citesc, o să mă mai gândesc și sper să-mi mai clarific din nelămuriri.

Eu priveam f ca pe o funcție din limbajul modelat. Poate ar fi trebuit să scriu μ f :: U -> U, unde μ indică interpretarea pe care o dau eu. E corect să facem distincția asta? Să mai considerăm un exemplu:

int f(int x) {
   r = 2;
   return x;
}

Efectiv în limbajul de programare funcția primește un int și returnează un int, dar eu aș vrea să privesc funcția f ca o funcție matematică int -> m int, pentru că vreau să modelez un efect (în acest caz, asignarea unei variabile globale). Are sens să fac așa ceva?

Edit: Cred că idea aceasta e legată de semantica limbajelor de programare, dar știu prea puține pentru a lega lucrurile.


#29

Mi-am amintit de un articol al lui Tomas Petricek, pe care-l aveam pe lista de citit, și care este relevant atât pentru subiectul acestui thread (“ce cărți FP mai citiți?”), cât și pentru discuția despre monade. Articolul se numește, What we talk about when we talk about monads, și explorează conceptul de monade dintr-o perspectivă mai aparte, și anume, contexul istoric, filozofic și sociologic. Sunt câteva pasaje în articol care subliniază diferitele fațete ale ideii de monadă; spre exemplu:

The meaning of a […] monad comprises aspects at three different levels. The first is a mathematical aspect that can be used for formal analysis. The second is an implementation of the concept that is used for some purpose in concrete programs or libraries. Finally, the third is a metaphorical or intuitive understanding what the concept is in terms of general examples or analogies. […] Moggi introduced monads for reasoning about effectful programs, but Wadler uses them to implement effectful programs in a purely functional programming language.