Накопленная сумма в списке - PullRequest
Новая
       30

Накопленная сумма в списке

0 голосов
/ 17 марта 2019

Я реализовал следующие функции для накопленной суммы: 

fun cumsum_reverse (xs: int list) = 
  if null xs then [0]
  else
    let val tl_cumsum = cumsum_reverse (tl xs)
    in
      hd xs + hd tl_cumsum :: tl_cumsum
    end

fun reverse (first: int list, second: int list) =
  if null first
  then
    second
  else
    reverse (tl first, hd first :: second)

fun cumsum (xs: int list) = 
  tl(reverse(cumsum_reverse(reverse(xs, [])), []))

Контрольный пример: 

val test = cumsum[1,4,20] = [1,5,25]

Есть ли способ реализовать это, используя только одну функцию?

Ответы [ 2 ]

2 голосов
/ 17 марта 2019

Я бы определил это в терминах общей функции scanl.Он похож на foldl, но выдает список промежуточных результатов.Он работает почти как кумулятивная сумма, но с параметризацией оператора + и элемента по умолчанию.Он не доступен в стандартной библиотеке, но с таким же успехом может быть. 

fun scanl _ _ [] = []
  | scanl f y0 (x::xs) =
    let val y1 = f (x, y0)
    in y1 :: scanl f y1 xs
    end

, а затем: 

val cumsum = scanl op+ 0

Есть ли способ реализовать это с помощью одной функциитолько?

Это зависит от того, что вы подразумеваете под «только одна функция».

Только одна функция вообще?cumsum принимает только один список в качестве входных данных, и вам нужен дополнительный аргумент для отслеживания накопленной суммы.Поскольку функция, которая накапливает результат, не может быть cumsum напрямую, вам нужны две функции.Так вы имеете в виду «одну именованную функцию помимо cumsum»?Тогда scanl или внутренняя вспомогательная функция Мэтта решит эту проблему.

Если вы можете определить cumsum только с помощью функций стандартной библиотеки: 

val cumsum = tl o rev o foldl (fn (x, y::ys) => x + y :: y :: ys) [0]

Тогда cumsum становится единственной функциейчто вы объявляете.

И если вы можете определить cumsum только с помощью одной функции стандартной библиотеки, я бы пошел с foldl: 

val cumsum = (fn (_::xs) => xs)  (* tl *)
           o foldl op:: []       (* rev *)
           o foldl (fn (x, y::ys) => x + y :: y :: ys) [0]

Тогда cumsum становитсяединственная функция, которую вы объявляете, и для этого вы использовали только одну именованную функцию стандартной библиотеки.(Если бы это не была функция стандартной библиотеки, вам нужно было бы объявить ее, а затем вы бы объявили две функции.)

Но это становится немного глупо.: -)

1 голос
/ 17 марта 2019

Конечно, вот один способ, который, я думаю, по-прежнему использует несколько функций, но это всего лишь помощник, чтобы удерживать накопленную сумму и начинать рекурсию с 0.

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

fun cumsum (xs : int list) =
  let fun cumsum (x::xs, sum) = let val foo = x + sum in foo::cumsum(xs, foo) end
        | cumsum ([], _) = []
  in cumsum (xs, 0) end
...