Foldable and (Co)Recursive


#1

This was started in a different thread, but I figure it’s better to avoid derailing that conversation.

The main idea is that if you look at foldl for example:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

and you compare it with, say, maybe:

maybe :: b -> (a -> b) -> Maybe a -> b

You can see a bit of a pattern here. The main idea is, you provide cases for each constructor of the type. Both have an empty constructor, so they both need a b value for that case. Maybe is simpler since it can only contain at most one value, so we only need a basic function a -> b. List, on the other hand can have multiple values (as demonstrated by its Cons a (List a) constructor.

This works for product types just as well. For example, Tuple can be folded using uncurry :: (a -> b -> c) -> (a, b) -> c.

The common idea is factored out in recursion-schemes via the Base type family (which basically describes the constructors for a type) and the Recursive type class.


Introduction Thread
#2

Nu vreau să deraiez prea mult discuția, dar @alexelcu spui că:

foldRight și Traversable nu sunt generice mai deloc, dar cum listele sunt folosite peste tot în FP, mitul și coafura persistă

Ai putea să elaborezi un pic? Există versiuni datatype-generic de fold și traverse [1, 2]. Te referi că nu e comun modul acesta de programare?

[1] Gibbons J and Oliveira B. The Essence of the Iterator Pattern
[2] Gibbons J. Design patterns as higher-order datatype-generic programs


Introduction Thread
#3

Da, mă refer că traverse și foldr merg atâta timp cât tipul de dată este o Listă sau poate fi encodat cu o Listă (e.g. Maybe, Either).

Orice nu este o listă (e.g. push-based stream, sau variante de ListT care nu sunt stricate), nu pot implementa Traverse.


#4

Sau ca să mă exprim altfel … Traversable descrie tipuri de date pentru care poți descrie o funcție de conversie f: F[A] => List[A].

Ceea ce înseamnă de fapt că Traversable poate descrie tipuri de date care sunt cel mult o Listă :wink:

Este interesant pentru că în Scala cel puțin, foldLeft este operația mai generică, din cauză că loop-ul de consum, evaluarea propriu zisă, rămâne în controlul producătorului (al structurii de date) și nu al consumatorului. Fără posibilitate de scurt-circuitare, nu ai probleme la finalizare, și din cauză că semnătura nu admite resultat “lazy”, nici nu ai nevoie de o decompoziție eficientă head/tail — în Haskell lucrurile stau altfel evident, datorită modelului de evaluare.


#5

@alexelcu Din câte înțeleg, articolele pe care le-am menționat definesc fold și traverse generic, pentru orice tip de date recursiv (care poate fi implementat cu Fix). Ca exemple sunt listele, dar și diferite tipuri de arbori, binary sau rose. Nu știu dacă la asta te referi și tu când zici “tip care poate fi encodat cu o listă”. Peste ce alte tipuri de date ai vrea ca fold și traverse să fie generice?

Ceea ce înseamnă de fapt că Traversable poate descrie tipuri de date care sunt cel mult o Listă

Ce înțelegi prin “mai mult” în contextul comparării a două tipuri de date? De exemplu, ai zice că un arbore e “cel mult” o listă?


#6

Eu cred că Alex se leagă fix de semnătura Foldable așa cum există ea astăzi în Haskell și așa cum a fost copiată și în Scala. Ceea ce zice Dan e, într-adevăr, o variantă generică care merge pentru orice data type, indiferent de numărul de data constructors. Ce are Haskell e limitat la o structură similară listelor.


#7

Mersi pentru clarificări Ionuț!

Secțiunea 12.5 din Typeclassopedia explică bine confuzia și faptul că eu și Alex vorbeam de lucruri diferite:

The generic term “fold” is often used to refer to the more technical concept of catamorphism. Intuitively, given a way to summarize “one level of structure” (where recursive subterms have already been replaced with their summaries), a catamorphism can summarize an entire recursive structure. It is important to realize that Foldable does not correspond to catamorphisms, but to something weaker. In particular, Foldable allows observing only the left-right traversal order of elements within a structure, not the actual structure itself. Put another way, every use of Foldable can be expressed in terms of toList. For example, fold itself is equivalent to mconcat . toList.

This is sufficient for many tasks, but not all. For example, consider trying to compute the depth of a Tree: try as we might, there is no way to implement it using Foldable. However, it can be implemented as a catamorphism.


#8

Așa cum ziceam, operațiile de fold oglindesc forma constructorilor de date. La asta se referă “catamorphism”-ul.

Idea că poți defini un fold în funcție de ADT-ul pe care-l ai nu te încălzește prea tare, că n-o să fie un fold refolosibil prea tare. E.g. dacă ai încerca să refolosești fold-ul lui Maybe pentru Either, ai pierde informație în caz de rezultat “Left”.

Foldable din Haskell este practic proiectat pentru List. Se întâmplă să fie refolosibil pentru chestii de genul Maybe / Either, dar asta pentru că privind șașiu poți considera Maybe ca o listă de un element și Left-ul din Either îl ignori pentru binele comun.

Despre arbori, apropo, orice arbore poate fi descris ca o listă printr-o traversare a arborelui, fie în lățime, fie în adâncime. Pierzi informație evident, așa că ori definești un fold pe structura arborelui, fie te mulțumești cu fold-ul listei ce nu-ți mai descrie structura arborescentă.

N-am citit acele lucrări. Sper să o fac într-o zi, o s-o pun la teancul de “technical debt” care-l am :stuck_out_tongue_winking_eye:


#9

Încă ceva …

orice tip de date recursiv (care poate fi implementat cu Fix)

Mă îndoiesc că pot fi implementate pentru Observable care are darul de a fi push-based (cu back-pressure) și deci nu prea este o structură de date recursivă :wink:


#10

Puzzle 1. Typeclassopedia menționează:

Consider trying to compute the depth of a Tree: try as we might, there is no way to implement it using Foldable. However, it can be implemented as a catamorphism.

  1. Implementați o funcție fold' pentru un arbore binar astfel încât să-o puteți folosi pentru a defini funcția depth, care calculează adâncimea arborelui.
  2. Cum diferă semnătura lui fold' față de semnătura lui foldr (impusă de typeclass-ul Foldable)?
  3. Cum ați implementa foldr pentru a defini instanța de Foldable pentru arborele binar?
  4. Implementați funcția depth folosind fold-ul generic, cata, din librăria recursion-schemes.

Puteți considera următorul tip pentru arborele binar:

data Tree a = Leaf a
            | Node (Tree a) (Tree a) 
    deriving Show

P.S.: Ideea de puzzle-uri mi-a venit de la cursul lui John C. Baez, Applied Category Theory, unde apar frecvent puzzle-uri de la cititori :slight_smile: