У меня есть структура данных,

datatype 'a tree = Leaf | Branch of 'a tree * 'a * 'a tree

и я хочу написать функцию, которая пересекает это дерево в некотором порядке. Это нене имеет значения, что он делает, так что это может бытьtreefold : ('a * 'b -> 'b) -> 'b -> 'a tree -> 'b, Я могу написать эту функцию так:

fun treefold f acc1 Leaf = acc1
  | treefold f acc1 (Branch (left, a, right)) =
    let val acc2 = treefold acc1 left
        val acc3 = f (a, acc2)
        val acc4 = treefold acc3 right
    in acc4 end

Но поскольку в последнем случае у меня неизбежно есть две ветви, это не хвосто-рекурсивная функция.

Можно ли создать такой, который, учитывая, что сигнатура типа может быть расширена, и какой ценой? Мне также интересно, если этодаже стоит попробовать; то есть дает ли он какие-либо преимущества в скорости на практике?