Уровень порядка в Хаскеле

Question

У меня есть структура для дерева, и я хочу напечатать дерево по уровням.

data Tree a = Nd a [Tree a] deriving Show
type Nd = String
tree = Nd "a" [Nd "b" [Nd "c" [],
                       Nd "g" [Nd "h" [],
                               Nd "i" [],
                               Nd "j" [],
                               Nd "k" []]],
               Nd "d" [Nd "f" []],
               Nd "e" [Nd "l" [Nd "n" [Nd "o" []]],
                       Nd "m" []]]
preorder (Nd x ts) = x : concatMap preorder ts
postorder (Nd x ts) = (concatMap postorder ts) ++ [x]

а как это сделать по уровням? "дерево уровней" должно печатать ["a", "bde", "cgflm", "hijkn", "o"]. Я думаю, что «итерация» была бы подходящей функцией для этой цели, но я не могу придумать решение, как ее использовать. Не могли бы вы помочь мне, пожалуйста?

Answer 1

Полагаю, это домашнее задание. Предполагая, что это так, вот несколько идей о том, как подумать о проблеме, которая может привести вас к ответу:

В preorder сначала «сообщается» текущий элемент, а затем повторяется для всех хвостов этого узла. В postorder эти два шага выполняются в обратном порядке. В обоих случаях рекурсия является «локальной», в том смысле, что ей нужно иметь дело только с одним узлом за раз. Это правда для levelorder? Или спросить это по-другому, когда levelorder рекурсанты, результаты рекурсий взаимодействуют или нет? Если так, то что такое «единица» рекурсии, если не один Tree?

Понимание природы рекурсии (или итерации ...?) levelorder приведет вас к очень простому и элегантному решению. Моя версия длиной всего три строки!

Кстати, было бы неплохо иметь эти служебные функции, чтобы в некоторых местах код был еще понятнее:

element :: Tree a -> a
element (Nd x _) = x
subtrees :: Tree a -> [Tree a]
subtrees (Nd _ s) = s

Или, если вы знакомы с синтаксисом записей в Haskell, вы можете добиться именно этого, изменив исходное определение Tree на:

data Tree a = Nd { element :: a, subtrees :: [Tree a] }
    deriving Show

---

Полное решение:

Ключ понимает, что levelorder требует рекурсии в списке Tree. На каждом шаге извлекаются элементы из каждого Tree, а следующий шаг происходит после объединения поддеревьев:

levelorder :: Tree a -> [a]
levelorder t = step [t]
    where step [] = []
          step ts = map element ts ++ step (concatMap subtrees ts)

Это создает элементы в одном сплюснутом списке, очень похожем на preorder и postorder do, и является обычным определением обхода в ширину.

Если вместо этого вы действительно хотите сгруппировать элементы по уровню, то одно изменение оператора ++ на : приведет к этой версии:

bylevel :: Tree a -> [[a]]
bylevel t = step [t]
    where step [] = []
          step ts = map element ts : step (concatMap subtrees ts)

Примечание: я дал сигнатуры типов для всех функций верхнего уровня. Это действительно хорошая привычка, и вы сэкономите много времени на отладке.

Answer 2

Вам просто нужно вычислить уровни для всех поддеревьев и объединить их все вместе после корня:

levels :: Tree [a] -> [[a]]
levels (Nd a bs) = a : foldr (zipWith' (++)) [] (map levels bs)

К сожалению, zipWith не делает правильных вещей, поэтому мы можем вместо этого использовать:

zipWith' f xs [] = xs
zipWith' f [] xs = xs
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys

Обновление: есть некоторая обеспокоенность (с которой я согласен), что то, что вы изначально просили, немного странно, поскольку это не универсальное дерево в ширину для преобразования списка. То, что вы, вероятно, действительно хотите - это получить результат:

levels' (Nd a bs) = [a] : foldr (zipWith' (++)) [] (map levels' bs)

Answer 3

Вот еще одна версия, которую можно применить к Tree a вместо Tree [a].

levelorder :: Tree a -> [[a]]
levelorder (Nd x ts) = [x]:(ziplist (map levelorder ts))

ziplist :: [[[a]]] -> [[a]]
ziplist l = if null ls then [] else (concat heads):(ziplist tails)
    where
        ls = filter (not.null) l
        heads = map head ls
        tails = map tail ls

Если вы хотите объединить строки в конце, вы можете использовать:

levelorder2 :: Tree [a] -> [[a]]
levelorder2 = (map concat).levelorder

Answer 4

levels :: (Tree a) -> [[a]]
levels (Nd x ts) = [[x]] ++ levelshelper ts

level2 = (map concat).levels

levelshelper :: [Tree a] -> [[a]]
levelshelper [] = []
levelshelper xs = (map (\(Nd x ts) -> x) xs) : (levelshelper (extractl xs))

--get the next level's Nd's 
extractl :: [Tree a] -> [Tree a]
extractl [] = []
extractl ((Nd x ts):xs) = ts ++ (extractl xs)

Мой подход оказался более сдержанным, чем я хотел. Поправьте меня, если я ошибаюсь, поскольку строки представляют собой списки символов, но вы используете полиморфные типы, действительно ли так просто распечатать результаты, как указано в задаче? Этот код создает списки списков строк. *** Подсказка Крису в его более элегантном ответе за напоминание об использовании concat !!