Эффективная реализация катаморфизма в Scala

Для типа данных, представляющего натуральные числа:

sealed trait Nat
case object Z extends Nat
case class S(pred: Nat) extends Nat

В Scala приведен простейший способ реализации соответствующего катаморфизма:

  def cata[A](z: A)(l: Nat)(f: A => A): A = l match {
    case Z => z
    case S(xs) => f( cata(z)(xs)(f) )    
  }

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

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

РЕДАКТИРОВАТЬ: Похоже, что это может иметь непосредственное отношение: можно ли использовать продолжения, чтобы сделать хвост foldRight рекурсивным?

Источник

2 ответа

Решение

Если бы вы применяли катаморфизм в списках, это было бы то, что в Хаскеле мы называем foldr, Мы знаем это foldr не имеет хвосто-рекурсивного определения, но foldl делает. Так что, если вы настаиваете на программе с рекурсивной версией, правильнее всего сделать обратный аргумент списка (хвостовой рекурсивно, в линейном времени), а затем использовать foldl вместо foldr,

В вашем примере используется более простой тип данных натуральных данных (и действительно "эффективная" реализация будет использовать машинные целые числа, но мы согласимся оставить это в стороне). Что является обратной стороной одного из ваших натуральных чисел? Только само число, потому что мы можем думать о нем как о списке без данных в каждом узле, поэтому мы не можем сказать разницу, когда оно перевернуто! И что эквивалентно foldl? Это программа (простите за псевдокод)

  def cata(z, a, f) = {
    var x = a, y = z;
    while (x != Z) {
      y = f(y);
      x = pred(x)
    }
    return y
  }

Или как хвостовая рекурсия Scala,

  def cata[A](z: A)(a: Nat)(f: A => A): A = a match {
    case Z => z
    case S(b) => cata( f(z) )(b)(f)    
  }

Будет ли это делать?

Источник

Да, именно этот мотивирующий пример приведен в статье " Клоуны" слева от меня, шутники справа ("Рассеивание структур данных") (обновленная, лучшая, но несвободная версия здесь http://dl.acm.org/citation.cfm?id=1328474).

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

  1. Что вы уже рассчитали
  2. Что тебе осталось сделать.

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

  1. Операция запускается на всех предыдущих значениях.
  2. Список элементов, оставленных для обработки.

Что именно foldl отслеживает, так что это своего рода совпадение foldl а также foldr может быть дано того же типа.

Источник
Другие вопросы по тегам