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

Question

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

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

В Scala, здесь есть элементарный способ реализации соответствующего catamorphism:

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-algebras, если интерфейс, представленный в конечном счете кодом, не может выглядеть так же просто, как выше.

EDIT: Похоже, что это может иметь непосредственное отношение: Is it possible to use continuations to make foldRight tail recursive?

Answer 1

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

В вашем примере используется более простой тип данных naturals (и действительно «эффективная» реализация будет использовать машинные целые числа, но мы согласны оставить это в стороне). Что такое обратное одному из ваших натуральных чисел? Просто само число, потому что мы можем рассматривать его как список без данных в каждом узле, поэтому мы не можем отличить его от обратного! И что эквивалентно 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)  
    } 

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

Answer 2

Да, это как раз мотивирующий пример в статье Clowns to the left of me, jokers to the right (Dissecting Data Structures) (обновленная, лучшая, но несвободная версия здесь http://dl.acm.org/citation.cfm?id=1328474).

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

1. Что вы» ve calculuated до сих пор
2. Что у вас осталось делать.

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

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

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