Haskell: получить путь от каждого конечного узла до корневого - PullRequest
Новая
       23

Haskell: получить путь от каждого конечного узла до корневого

0 голосов
/ 27 декабря 2011

У меня есть симуляция qwestion Haskell: Получить путь от каждого конечного узла до корня в древовидной структуре Bin .И ответа нет.

(найди путь).ords (2, 2) -> [2, 1, 0] У меня есть дерево, где каждый уровень начинается с 0. 

   0
  / \
 0   1
/ \ / \
0 1 2 3
........

Я написал некоторый код, но он не работает (конечно, ...) 

fromroot 0 _ _ = []
fromroot i j (Node t1 x t2)
   = if (j div (2^(i-1)))
        then x++ (fromroot (i-1) (j-2^(i-1)) t2)
        else x++ (fromroot (i-1) j t1)

tree я взял оттуда нить. 

data Tree a = Node (Tree a) a (Tree a)

myBuild :: Int  -> Tree Int
myBuild n = (Node (myBuild (n*2)) n (myBuild (n*2+1)))

Надеюсь, вы мне поможете.

UPD 1

Ввод > fromroot 3 2 (myBuild 0) и ошибка в функции myBuild. 

    Couldn't match expected type `[a0]' with actual type `Int'
    Expected type: Tree [a0]
      Actual type: Tree Int
    In the return type of a call of `myBuild'
    In the third argument of `fromroot', namely `(myBuild 0)'
Failed, modules loaded: none.

Ответы [ 2 ]

1 голос
/ 27 декабря 2011

Подсказка

Давайте попробуем получить элемент (2,3) [Уровень 2, Элемент № 3 в качестве объяснения используемых здесь координат] из вашего исходного дерева. 

   0
  / \
 0   1
/ \ / \
0 1 2 3

Теперь это то же самое, что извлечь элемент (1,1) из поддерева (что тривиально!) 

 1
/ \
2 3

Теперь подумайте о примере дерева с еще одним уровнем. И сделать трюк рекурсии.

0 голосов
/ 27 декабря 2011

Вы думаете, что написали fromroot, чтобы принять Tree a в качестве третьего аргумента, но вместо этого вы написали, что Tree [a].

Это потому, что вы используете x в качестве списка, вместо добавления его к списку, возвращенному из рекурсивного вызова.

Чтобы добавить один элемент в список, вы используете :. ++ предназначен для объединения двух списков вместе.

(я также думаю, что ваше условие if должно быть 0 /= (j `div` (2^(i-1))) вместо j div (2^(i-1)), потому что (1) для использования именованных функций в качестве оператора они должны быть заключены в обратные черты, а (2) if принимает Bool и не приводится, например, из Int для вас. Но это не то, на что жаловалось сообщение об ошибке, которое вы опубликовали.)

Могут быть и другие ошибки; Я не проверял.

...