Обход списка в SML

Question

Я хочу создать функцию, которая обходит список, обрабатывает заголовок, останавливается после K рекурсий, а также создает идентичный список, используя элемент head в каждой рекурсии. Код:

fun trav (0, _, list) = list
  | trav(K, x::xs, list) =
      trav(K - 1, xs, list@[x])

так что если я позвоню trav(4,[1,2,3,4,5,6],[])

Я ожидаю

  list   =[1]       ,K=3
         =[1,2]     ,K=2
         =[1,2,3]   ,K=1
         =[1,2,3,4] ,K=0 

Однако для очень больших входных данных это-> list@[x], кажется, приводит к сбою моей программы (я не уверен, почему), и если я вместо этого использую (x :: list), предоставляя другой (но одинакового размера) список в результате на каждом шаге все работает нормально. Почему это происходит? Как я могу реализовать list@[x] с помощью оператора cons?

Answer 1

list@[x] необходимо пройти через всю совокупность list, а затем скопировать ее, переводя элемент за элементом в [x], что очень неэффективно.

Обычное решение состоит в том, чтобы построить результат в обратном порядке, а затем поменять его на желаемый порядок, когда вы закончите:

fun trav (0, _, list) = List.rev list
  | trav (K, x::xs, list) = trav (K-1, xs, x::list)

Это может показаться неэффективным, но на самом деле это намногоболее эффективен, чем добавляемая версия.
(в этом случае линейная сложность по времени, а не квадратичная, на случай, если это что-то для вас значит).

Answer 2

[...] для очень больших вводов list@[x], кажется, вылетает моя программа [...] , и если я использую x :: list вместо этого, давая другое (но одного размера) в результате на каждом шаге все работает нормально.

Почему это происходит?

list@[x] исчерпывает стековую память вашей программы , поскольку оператор @ не является рекурсивным.

Когда list очень длинный, он создает выражение следующим образом:

   [a,b,c,d,e,f,...] @ z
~> a :: [b,c,d,e,f,g,...] @ z
~> a :: b :: [c,d,e,f,g,...] @ z
~> ...
~> a :: b :: ... :: [] @ z
~> a :: b :: ... :: z :: []

Все эти элементы промежуточного списка хранятся в стеке рекурсивных вызовов, из которого ваша программа в конце концов исчерпает себя. И в довершение всего, это дорогостоящее вычисление повторяется для каждого элемента в списке, так что O (n²) затраты времени.