Совокупная сумма списка int
Я реализовал следующие функции для накопительной суммы:
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]
Есть ли способ реализовать это, используя только одну функцию?
![Учебная записка [Medium] Leetcode#22 Generate Parentheses](https://i.imgur.com/Hl2feR7b.png)
Ответы 2
Конечно, вот один из способов, который, я думаю, все еще использует несколько функций, но это просто помощник, чтобы удержать кумулятивную сумму и начать рекурсию с 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
Я бы определил это с точки зрения общей функции 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
Is there any way to implement this using one function only?
Это зависит от того, что вы подразумеваете под «только одной функцией».
Всего одна функция? 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 становится единственной функцией, которую вы объявляете, и для этого вы использовали только одну именованную функцию из стандартной библиотеки. (Если бы это не была функция стандартной библиотеки, вам пришлось бы объявить ее, а затем вы бы объявили две функции.)
Но это становится немного глупо. :-)