SML двоичное дерево сокращает функцию

Question

Итак, у меня есть задание в SML, и мне нужна помощь, чтобы начать работу.

Проблема выглядит так

Напишите функцию btree_size типа 'a btree -> int, которая возвращает размер двоичного дерева. (Размер бинарного дерева - это число элементы в двоичном дереве). Например, btree_size (Node (Leaf, 1, Node (Leaf, 2, Leaf))) должен вернуть 2. Ваша функция должна использовать предоставляется функция btree_reduce и должна иметь длину не более 3 строк.

Функция btree_reduce это

(* A reduction function. *)
     (* btree_reduce : ('b * 'a * 'b -> 'b) -> 'b -> 'a tree -> 'b) *)
    fun btree_reduce f b bt =
      case bt of
      Leaf => b
      | Node (l, x, r) => f (btree_reduce f b l, x, btree_reduce f b r)

Как в мире я могу создать функцию btree_size, которая берет btree и использует функцию Reduce, чтобы определить размер дерева?

Answer 1

Поскольку это домашнее задание, я воздержусь от прямых ответов.:)

Я бы поступил следующим образом:

• познакомимся с вычислением размера дерева (написав рекурсивную функцию, соответствующую вашим спецификациям)
• посмотрите, что общего между написанной вами функцией и btree_reduce (или, что может быть абстрагировано от написанной вами функции)

Конечно, это один из многих способов.