Преврати дерево в Хаскель

Question

  data BinaryTree a = Null | Node (BinaryTree a) a (BinaryTree a)
             deriving Show
  data RoseTree a = RoseNode a [RoseTree a]
     deriving Show
  binaryTreeToRose :: BinaryTree a -> RoseTree a
         binaryTreeToRose btree = case btree of
         Node Null a Null -> RoseNode a []
         Node left a Null -> RoseNode a [binaryTreeToRose left]
         Node Null a right -> RoseNode a [binaryTreeToRose right]
         Node left a right -> RoseNode a [binaryTreeToRose left]++[binaryTreeToRose right]

Я пытаюсь написать функцию для преобразования двоичного дерева в розовое дерево на Хаскеле. Но я понятия не имею, как решить эту проблему с помощью рекурсии.

Answer 1

Вы уже решаете это рекурсивно. На самом деле вы звоните binaryTreeToRose на детей left и right. Таким образом, вы определяете binaryTreeToRose в терминах самого себя.

Однако ваша функция не является полной. Поскольку для binaryTreeToRose Null это будет ошибка. Мы можем сделать тип возврата Maybe (RoseTree a):

import Data.Maybe(catMaybes)

binaryTreeToRose :: BinaryTree a -> <b>Maybe</b> (RoseTree a)
binaryTreeToRose Null = Nothing
binaryTreeToRose (Node l a r) = Just (RoseNode a (<b>catMaybes</b> (map binaryTreeToRose [l, r])))

или даже короче:

import Data.Maybe(mapMaybe)

binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose Null = Nothing
binaryTreeToRose (Node l a r) = Just (RoseNode a (<b>mapMaybe</b> binaryTreeToRose [l, r]))

Answer 2

Измените

           [binaryTreeToRose left]++[binaryTreeToRose right]

(в любом случае, это ошибка) в вашей последней строке кода на

           (binaryTreeToRose left ++ binaryTreeToRose right)

, измените тип функции на

binaryTreeToRose :: BinaryTree a -> [RoseTree a]

и соответственно измените другие случаи (также добавив новое предложение для случая Null).

Ваш BinaryTree может быть пустым (представлен Null), но RoseTree не может. Это означает, что мы не можем преобразовать первое в второе, а скорее в список из них.

Библиотека Haskell вызывает тип [RoseTree a] a "Лес" . Таким образом, результатом преобразования будет лес розовых деревьев , содержащий либо одно, либо ноль из них (представляющий случай пустого двоичного дерева).

Наличие пустого дерева похоже надеревьев нет вообще. В любом случае нет фруктов.

Answer 3

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

Например:

  data BT a = BNil | BN (BT a) a (BT a)
             deriving Show
  data RT a = RN a [RT a]
     deriving Show

-- data BTF a f = BNilF | BNF f a f deriving Functor
makeBaseFunctor ''BinaryTree

binaryTreeToRose :: BinaryTree a -> Maybe (RoseTree a)
binaryTreeToRose = cata alg where
  alg BNilF = Nothing
  alg BNF l a y = Just $ RN a $ catMaybes (l ++ r)