Scans and reduction functions

Abierto
  • ¿Algo no está bien?
#3,340 1 comentario 2 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
35/100
Tipo de issue
Nueva funcionalidad
Claridad
Necesita aclaración
Estado de actividad
Tranquilo
Stack tecnológico
cpp
Área
backend

Línea de trabajo

Comienza con el issue relacionado #3339; después, revisa la semántica propuesta para fold_left, fold_right, reduce y scan, así como las referencias enlazadas sobre algoritmos paralelos. Antes de la implementación, aclara qué funciones debería admitir Stan y cuáles son sus requisitos de API y evaluación; se considera terminado cuando el alcance esté acordado y las funciones seleccionadas estén implementadas de forma coherente.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

feature new function

Related to #3339, there are also common higher-order functions that return a different type than their input.

Some common options are:

  • fold_left(F, T, ...) => f(f(f(f(T[0], T[1]), T[2]), ...), T[3]) (sometimes, rather than starting at T[0], an extra 'init' argument is passed)
  • fold_right, which is the same idea but with the opposite association f(T[0], f(T[1], ...f(T[N], init)))
  • reduce, which is defined such that it is equivalent to the above when the f is associative but does not explicitly state an order of evaluation. The cool thing about reduce is it can be parallelized, c.f. foldl and foldr Considered Slightly Harmful, and More Fun with Moniods
  • scan, which returns a cumulative evaluation scan(f, T, ...) => [T[1], f(T[1], T[2]), f(f(T[1], T[2]), T3), ...]. Note that scan can also be parallelized when f is associative, c.f. Prefix Sums and their Applications. (Note: even though reduce(f, T, ...) == scan(f, T, ...)[N], the ideal parallelization algorithms actually differ)

There are other functions of questionable value to Stan in this family, like folding_map which returns both a carry and a mapped container (this is, confusingly, what JAX calls scan. Scans a-la Blelloch as described above are called associative_scan in JAX)

Lenguaje dominante
C++
Estrellas
845
Forks
225
Merge medio
3 d 9 h
PR fusionados (30 d)
12

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de stan-dev/math

Todos los issues de stan-dev/math

Issues similares

Más issues de C++

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.