Нужна помощь понимание функции продолжения

Question

Это из учебного примера для иллюстрации СУЗ и хвостовую рекурсию:

fun sum [] k = k 0 
    | sum (x::xs) k = sum xs (fn y=>k(x+y)); 

У меня есть проблемы с пониманием того, как анонимная функция fn y=>k(x+y) бы суммировать элементы списка ввода правильно.

Из того, что я понимаю, эта анонимная функция означает новую функцию с одним аргументом y, где тело функции вызывает исходную функцию k с аргументом y+x.

Если я призываю sum [1,2,3,4,5] (fn x=>x); я 15. Если у меня есть sum [1,2,3,4,5] (fn x=>3x); ответ 45. Пользователь функции sum, следовательно, должен был бы сначала понять точные кровавые подробности sum, как только соответствующая версия k будет производить сумму данного списка. Какова реальная цель обеспечения функции, предоставляемой пользователем таким образом?

Если я являюсь автором функции sum, я не могу контролировать, что пользователь будет передавать для k. Другими словами, как я могу точно указать, что будет делать функция точно?

Answer 1

У меня есть проблемы с пониманием того, как [...] бы подытожить элементы списка ввода правильно.

Try и оценить вашу функцию вручную:

sum [1,2,3] id 
sum [2,3] (fn y1=>id(1+y1)) 
sum [3] (fn y2=>(fn y1=>id(1+y1))(2+y2)) 
sum [] (fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3)) 
(fn y3=>(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+y3)) 0 
(fn y2=>(fn y1=>id(1+y1))(2+y2))(3+0) 
(fn y2=>(fn y1=>id(1+y1))(2+y2)) 3 
(fn y1=>id(1+y1))(2+3) 
(fn y1=>id(1+y1)) 5 
id(1+5) 
id(6) 
6 

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

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

Как пишет Берги, пользователю не нужно понимать, как работает функция sum, только если он принимает продолжение в качестве аргумента и разрешает его в своем базовом случае. Как пишет Берги, ему не нужно оценивать k в базовом случае. Альтернатива этой функции будет:

fun sum [] k = k 
    | sum (x::xs) k = sum xs (fn y=>k(x+y)); 

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

fun sumMany [] k = k 
    | sumMany (xs::xss) k = sumMany xss (sum xs k) 

И вы можете оценить его как

val result = sumMany [[1,2,3],[4,5,6],[7,8,9]] (fn x=>x) 0 

Answer 2

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

№ Как и всегда, чтение документов должно быть достаточным, нет необходимости заглядывать в детали реализации. Ваш k - , указанный - точную сумму списка - это все, что важно. Вы должны понимать k как output parameter (хотя без мутации); это в основном callback

Если я писатель функции суммы, я не могу контролировать то, что пользователь будет проходить в течение k. Другими словами, как я могу точно указать, что будет делать функция точно?

Вам не нужно заботиться о том, что пользователь проходит. Вы просто документируете, что делает эта функция: она вызывает поставляемый k с суммой представленного списка xs. Возвращаемое значение не имеет значения.

Какова цель реального использования функции, предоставляемой пользователем таким образом?

Если вы добрались до крайности, вам не нужно когда-либо возвращать какое-либо значение в continuation-passing style - вы просто передаете его обратному вызову. Это делает излишним стек вызовов. С другой стороны, каждая функция заканчивается хвостовым вызовом, который можно оптимизировать, а не возвращать.