Как очистить функцию обхода уровня?

Question

Я имею дело с общей установки дерева, которое определяется следующим образом:

data Tree a = Node a [Tree a] deriving (Eq, Read, Show) 

С помощью этой установки, я создал функцию, которая печатает узлы на определенном уровне дерева (корень уровень 0, немедленная дети корня - уровень 1 и т. д.). Это функция:

level :: Int -> Tree a -> [a] 
level 0 (Node a _) = [a] 
level n (Node _ subtrees) = concatMap (level (n - 1)) subtrees 

Используя эту функцию в качестве основы, я создал вторую функцию, levelorder, которая выводит список всех узлов в дереве в порядке обхода уровня. Эта функция в настоящее время выглядит следующим образом:

levelorder :: Tree a -> [a] 
levelorder tree = level 0 tree ++ level 1 tree ++ level 2 tree ++ level 3 tree 

В то время как это работает для дерева я в настоящее время работаю с, я хотел бы, чтобы очистить его туда, где он будет работать с деревом любого размера. Как вы можете видеть, в настоящее время он работает только с деревом с 4 уровнями (от 0 до 3). Как я мог бы достичь этого, где я все еще могу использовать функцию уровня как базу?

Answer 1

Если вы имели функцию depth :: Tree a -> Int, который рассказал вам, как глубоко дерево, это было бы так просто, как

levelorder tree = concatMap (\lvl -> level lvl tree) [0..depth tree] 

Это не особенно быстрая реализация, хотя, вы в конечном итоге обхода дерева много раз ,

Answer 2

Сначала вам нужна функция глубины, так что вам не нужно фиксировать количество уровней, которые вы объединяете.

depth :: Tree a -> Int 
depth (Node _ [])  = 1 
depth (Node _ r@(x:xs)) = 1 + maximum (map depth r) 

Тогда вместо фиксации количества раз вы используете (++), вы просто concat результатов map ИНГИ функцию уровня по каждому уровню, который вы рисуете из списка [0..depth tree].

levelorder' tree = concatMap (flip level tree) [0..depth tree]

Answer 3

Вы можете пройти уровни succesively, пока не кончатся узлов:

levelorder :: Tree a -> [a] 
levelorder t = concat $ takeWhile (not . null) $ map (`level` t) [0..]