Определение функции от списков до бинарных и унарных деревьев - PullRequest
Новая
       32

Определение функции от списков до бинарных и унарных деревьев

0 голосов
/ 18 февраля 2019

Рассмотрим двоичные и унарные деревья, определенные следующим типом, и функцию flatten, которая преобразует двоичные и унарные деревья в списки (например, flatten (Node (Leaf 10) 11 (Leaf 20)) is [10,11,20]): 

data Tree a = Leaf a | Node (Tree a) a (Tree a) | UNode a (Tree a) deriving (Show)
flatten :: Tree a -> [a]
flatten (Leaf x) = [x] 
flatten (Node l x r) = flatten l ++ [x] ++ flatten r
flatten (UNode l x) = [l] ++ flatten x

Я пытаюсь определить рекурсивную функцию reverseflatten, которая преобразует списки в двоичные и унарные деревья, в частности , в соответствии со следующим шаблоном , который работает для списков длины <= 7. Iя могу видеть, как будет развиваться шаблон, но не как создать рекурсивную функцию из моего примера: </p> 

reverseflatten :: [a] -> Tree a
reverseflatten [x] = (Leaf x)
reverseflatten [x,y] = UNode x (Leaf y)
reverseflatten [x,y,z] = Node (Leaf x) y (Leaf z)
reverseflatten [x,y,z,x'] = Node (Leaf x) y (UNode z (Leaf x') )
reverseflatten [x,y,z,x',y'] = Node (Leaf x) y ( Node (Leaf x') z (Leaf y'))
reverseflatten [x,y,z,x',y',z'] =  Node (Leaf x) y ( Node (Leaf x') z ( UNode y' (Leaf z')))
reverseflatten [x,y,z,x',y',z',x''] =  Node (Leaf x) y ( Node (Leaf x') z ( Node (Leaf z') y' (Leaf x'')))

Как бы я создал такую ​​рекурсивную функцию, чтобы для любого конечного списка формировалось двоичное деревовид, определенный выше?Ответ ниже не делает этого, так как он не следует описанному выше шаблону.

Редактировать: процедура, которой я следовал для четных списков> 2, должна быть достаточно прозрачной (вы берете дерево, соответствующеенечетный список, а затем вы добавляете унарный узел).Общая процедура, которой я следовал при построении дерева из нечетного списка, заключалась в следующем.reverse flatten[x,y,z] - это Node (Leaf x) y (Leaf z).Затем для следующего нечетного списка вверх, [x, y, z, x', y'], я хотел сохранить z в его предыдущей позиции в случае reverseflatten [x,y,z] (в котором z был последним нижним правым листом), и поэтому позиция z как и в Node (Leaf x') z (Leaf y'), во-вторых, так что дерево для этого случая точно так же, как дерево для reverseflatten [x,y,z], за исключением того, что мы добавляем узлы, окружающие нижний правый лист, z.Затем я хотел, чтобы x 'и y' окружали z в том порядке, в котором они присутствуют в списке, следовательно, Node (Leaf x ') z (Leaf y').Затем для следующего нечетного списка reverseflatten [x,y,z,x',y',z',x''] у меня была похожая идея.Я хотел, чтобы y' оставался на своем месте в reverseflatten [x,y,z,x',y'] и reverseflatten [x,y,z,x',y',z', x'']), чтобы быть построенными, окружая y' z и x в порядке, в котором они присутствуют в списке.

1 Ответ

0 голосов
/ 18 февраля 2019

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

reverseflatten :: [a] -> Tree a
reverseflatten [x] = (Leaf x)
reverseflatten [x,y] = UNode x (Leaf y)
reverseflatten [x,y,z] = Node (Leaf x) y (Leaf z)
reverseflatten (x:y:xs) = revflat2 (x:y:xs)

revflat2 :: [a] -> Tree a
revflat2 [x] = (Leaf x)
revflat2 [x,y] = UNode y (Leaf x)
revflat2 [x,y,z] = Node (Leaf x) y (Leaf z)
revflat2 (x:y:xs) = Node (Leaf x) y (revflat2 ([head $ tail xs] ++ [head xs] ++ tail (tail xs)))
...