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

Это из учебного примера, иллюстрирующего CPS и хвостовую рекурсию:

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. Другими словами, как мне указать, что именно будет делать функция?


functional-programming sml smlnj
person Old Geezer    schedule 20.10.2015    source источник
comment
Я думаю, что это плохой пример: потребитель не должен знать о таких деталях реализации, как то, что такое k, и что для получения правильного результата в соответствии с контрактом функции он должен передать функцию идентификации. Правильное решение вообще не раскрывает параметр k в подписи sum.   -  person zerkms    schedule 20.10.2015

Ответы (2)


arrow_upward
1
arrow_downward

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

Попробуйте и оцените свою функцию вручную:

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 даст сумму данного списка. Какова реальная цель такой функции, предоставляемой пользователем?

Как пишет Берги, пользователю не нужно понимать, как работает функция суммы, достаточно знать, что она принимает продолжение в качестве аргумента и разрешает его в базовом случае. Как также пишет Берги, ему не нужно оценивать 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
person Simon Shine    schedule 20.10.2015
comment
Спасибо! Ручная оценка ряда анонимных функций была тем, что я искал. Для меня он не интуитивно понятен, его трудно читать и трудно проверить, дает ли он желаемые результаты. Все это кажется противоположным тому, что рекламируется FP. - person Old Geezer; 20.10.2015

arrow_upward
3
arrow_downward

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

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

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

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

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

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

person Bergi    schedule 20.10.2015