Рассмотрим две функции: let rec f ~acc = function |

Question

Рассмотрим две функции: let rec f ~acc = function |

[] -> List.rev acc
| x :: xs -> f ~acc:((x * 2) :: acc) xs
;;

let rec f ~acc = function
| [] -> acc []
| x :: xs -> f ~acc:(fun xs -> (x * 2) :: acc xs) xs
;;

первая функция это обычный accumulate-and-reverse. вторая функция это то же самое, только acc тут выступает как функция. из-за потока исполнения мы под конец просто вызываем acc [] без надобности в List.rev. в отличие от первой f, вторая не требует промежуточной структуры данных.

почему чаще используют первый подход, нежели второй? неужели производительность второго подхода считается хуже (я ещё не проверял)?

#programming #reasonml #russian

0

30.07.2024

9 ответов

45 просмотров

hirrolot Автор вопроса

конкретно в этом случае можно сделать просто tail_mod_cons, но есть случаи, когда рекурсивный вызов просто не выступает в позиции конструктора, а элементы списка всё равно накапливать надо

0

3 месяца назад

hirrolot Автор вопроса

Alex Gryzlov
второе это difference list, частный случай моноида...

понял, то есть всё-таки используется: > This implementation is typically used in functional programming languages such as Haskell, although it could be used in imperative languages as well. https://en.wikipedia.org/wiki/Difference_list в окамле просто не видел особо...

0

3 месяца назад

Dika

второе это ведь CPS-трансформация. и вторая функция наверняка медленнее

0

3 месяца назад

Alex Gryzlov

Dika
второе это ведь CPS-трансформация. и вторая функци...

зависит от того что с ней делать

0

3 месяца назад

hirrolot Автор вопроса

Dika
второе это ведь CPS-трансформация. и вторая функци...

обе функции и так tail-recursive, CPS материализует контекст, он тут пустой

0

3 месяца назад

hirrolot Автор вопроса

Dika
второе это ведь CPS-трансформация. и вторая функци...

побенчмаркал потехи ради. первая версия, список 50 миллионов элементов (с List.rev): real 0m10.048s user 0m8.778s sys 0m1.249s вторая версия: real 0m10.596s user 0m8.990s sys 0m1.600s

0

3 месяца назад

Dika

hirrolot
побенчмаркал потехи ради. первая версия, список 50...

есть код? это без флямбды?

0

3 месяца назад

TOV_MULTIMASSO

В неленивой реализации промежуточный список всё равно создаётся, только в виде цепочки вывзовов получившегося [DList](https://hackage.haskell.org/package/dlist-1.0/docs/Data-DList.html#t:DList)

0

3 месяца назад

Alex Gryzlov · Accepted Answer

Alex Gryzlov

второе это difference list, частный случай моноида Кэли

0

3 месяца назад

169 похожих чатов

Рассмотрим две функции: let rec f ~acc = function |

9 ответов

Похожие вопросы