Haskell: проблемы, полностью определяющие факториал в стиле прохождения продолжения

Question

Я пытался понять функциональное программирование, Haskell и стиль прохождения продолжения в одном большом блобе, и мой структурированный фон / ООП создает мне трудное время.Я понимаю, что следующее должно быть правильным определением факториала в стиле CPS:

factorial n = fact n id where id = \x -> x
    fact 0 cont = cont n
    fact (n+1) cont = fact n * (n + 1)

, но я не уверен насчет части "* (n + 1)" в конце - это правильно?

Answer 1

Это не совсем правильно (и не компилируется для меня); значение n+1 является правильным, но оно используется не совсем корректно. Может быть, вы хотели использовать раздел оператора?

factorial n' = fact n' id
 where
  id = \x -> x
  fact 0 cont = cont 1
  fact (n+1) cont = fact n (cont . (* (n+1)))

Это идентично (но более тупо) следующему

factorial n' = fact n' id
 where
  id = \x -> x
  fact 0 cont = cont 1
  fact (n+1) cont = fact n (\ret -> cont (ret * (n+1)) )

Есть несколько вещей, которые я бы здесь изменил. Во-первых, id - это стандартная функция, поэтому вам не нужно ее переопределять. Во-вторых, эти примеры используют «n + k шаблонов», которые IIRC больше не доступны по умолчанию в GHC. Вместо «n + k pattern» вы можете использовать обычную переменную pattern. Обратите внимание, что я использовал 1 для базового случая; об этом проще рассуждать, если вы ведете обратный отсчет с n, и функция продолжения должна применяться на каждом этапе вычисления (вы отбросили его с этапа индукции). Имея это в виду, вы можете написать

factorial n' = fact n' id
 where
  fact 0 cont = cont 1
  fact n cont = fact (n-1) (cont . (* n))

, который я бы назвал более или менее идиоматическим.

Редактировать: Мне лично не нравятся n + k паттерны, но я подумал, что мне потребуется немного времени, чтобы объяснить их. Мне легче следовать, если вы думаете о математической индукции с базовым случаем и шагом индукции. Базовый случай fact 0 .... Затем вы определяете другие значения, исходя из базового шага: «для любого fact n k определите fact (n+1) k по этому отношению». Это отличается от того, как я думаю о нормальных переменных шаблона, то есть сверху вниз, а не снизу вверх, как здесь, но я думаю, что это объясняет мотивацию и почему некоторым людям нравится стиль.

Причина, по которой мне не нравятся n + k паттерны, состоит в том, что я просто нахожу определения более беспорядочными, но YMMV.