haskell BinaryTree Signatur Termalalgebra Рассчитать размер

Question

Мне нужно написать функцию в haskell, которая вычисляет размер бинарного дерева.У меня есть попытка, но я не понимаю, что говорит мне сообщение об ошибке или что-то не так.

Моя попытка:

sizeBintree :: Bintree a -> Int 
sizeBintree  = foldBin $ BinSig {empty_ = 0, 
                              fork = \a left right -> a+sizeBintree left+sizeBintree right}

соответствующие определения:

data Bintree a = Empty | Fork a (Bintree a) (Bintree a)

data BinSig a val = BinSig {empty_ :: val,
                            fork :: a -> val -> val -> val}
foldBin:: BinSig a val -> Bintree a -> val
foldBin alg Empty = empty_ alg
foldBin alg (Fork a left right) = fork alg a (foldBin alg left)
                                             (foldBin alg right)

сообщение об ошибке:

Couldn't match expected type 'Bintree a0' with actual type 'Int' 
In the expression: a+sizeBintree left+sizeBintree right 
In the 'fork'    field of a record 
In the second argument of '($)', namely 'BinSig {empty_ = 0,fork = \a left right -> a+sizeBintree left+sizeBintree right}' 
relevant bindings include 
right::Bintree a0 
left:: Bintree a0

Answer 1

Вы хотите, чтобы ваш fork был таким:

fork = \a left right -> 1 + left + right

Были две проблемы с вашей версией.Сначала вы вычисляете размер, а не складываете элементы дерева.Таким образом, вы не хотите добавлять это a, это может быть даже не то, что вы можете добавить вообще.

 fork = \a left right -> a+sizeBintree left+sizeBintree right
                         ^

Во-вторых, посмотрите на тип вилки:

 fork :: a -> val -> val -> val

он берет элемент дерева, затем два значения (не деревья!) И возвращает другое значение.Эти два значения будут результатами для свертывания левого и правого поддеревьев.

 fork = \a left right -> a+sizeBintree left+sizeBintree right
                           ^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^

Примечание. Форк не должен выполнять какую-либо рекурсию.Схема рекурсии определяется как foldBin.