040 — Introduction to Recursion Schemes in Haskell


#1

Thank you everyone for attending! The slides are available at here – there’s a literate haskell version that you can load in GHCI to play with!


#2

Salut! Din păcate, luni a trebuit să plec mai deverme de la prezentare și aș mai avea câteva întrebări pe care nu am apucat să le adresez:

  1. Am observat că funcția de “unfold” se numește de unfoldr – bănuiesc că de la “unfold right.” Există și o versiune unfoldl, de “unfold left”? Dacă da, care ar fi implementarea?
  2. Nu mi-e foarte clar care e legătura dintre universal algebra și noțiunea de F-algebra (care apare în teoria categoriilor).
  3. Am observat că la finalul prezentării sunt menționate structuri de date mutual recursive. Aveți ceva resurse care să exemplifice utilizarea de recusion schemes pentru așa ceva?

#3

Salut Dan, si multumesc de intrebari.

  1. Nu cred ca e o problema cu unfoldl (de fapt, sunt cateva pachete in Hackage care ofera foldl)
    Am facut aici un mic exemplu cu cele 2 unfold-uri față in față: https://gist.github.com/traiansf/bef128b424061fbf1e723fcb6e642f33

  2. Poate nu era neapărat să includ slide-ul de algebră universală, dar îmi era mai familiar mie :slight_smile: Părerea mea e că f-algebrele sunt o generalizare categorială a conceptului de algebră universală. În plus, cănd ne gândim practic la f-algebra inițială, cred că ajută să ne gândim la ea ca o algebră de termeni peste o signatură (In Haskell cam asta si sunt).

  3. Din pacate nu prea pot sa spun decat sa cauti pe google:
    https://www.google.com/search?q=mutually+recursive+recursion+schemes

Aici pare sa fie ceva magie, dar recunosc ca inca nu o inteleg:


#4

Salut!

Mulțumesc pentru răspunsuri!

Da, ai dreptate legat unfoldl: așa cum pentru fold, funcția de reducere asociază la stânga sau la dreapta, tot așa pentru unfold putem alege asocieri diferite pentru funcția de combinare: cons sau snoc (adică flip (:)).

Cred că am avea următoarele diagrame de execuții pentru cele patru variante:

Pentru diagrama de mai sus am notat f' = flip f și am folosit o implementare alternativă pentru unfold care sparge funcția de iterare de tipul a → Maybe (a, b) în trei funcții separate:

  • f :: a → b care produce un nou element
  • g :: a → a care produce un nou seed
  • p :: a → Bool care este un predicat care determină oprirea.

O să mă gândesc și la celelalte răspunsuri – mersi încă o dată!