Нахождение листьев индуктивно заданного дерева

Question

Итак, у меня есть функция типа:

genTree :: Node -> [Nodes]

Для данного узла эта функция генерирует множество дочерних элементов этого узла в дереве. Функция может быть применена снова к этим дочерним элементам для генерации их дочерних элементов, пока в конечном итоге она не сгенерирует узел без дочерних элементов, то есть узел, для которого genTree возвращает [].

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

Какой совет?

Answer 1

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

nodes root  = root : concatMap nodes (genTree root)
leaves root = filter (null . genTree) (nodes root)

Вы также можете объединить эти две функции в одну для непосредственного создания только списка листьев, если вы предпочитаете:

leaves node
   | null children = [node]
   | otherwise     = concatMap leaves children
   where children = genTree node

Answer 2

Давайте немного обобщим:

leaves :: (a -> [a]) -> a -> [a]
leaves tree x = case (tree x) of
                  [] -> [x] 
                  -- the node x has no children and is therefore a leaf
                  xs -> concatMap (leaves tree) xs
                  -- otherwise get list of all leaves for each child and concatenate them

Применение статического преобразования аргумента (http://hackage.haskell.org/trac/ghc/ticket/888), мы получаем

leaves :: (a -> [a]) -> a -> [a]
leaves tree x = leaves' x where
  leaves' x = case (tree x) of
                [] -> [x] 
                xs -> concatMap leaves' xs

Используйте как

leaves genTree root

или, если вы действительно хотите, чтобы он работал только с genTree, вставьте его в определение:

leaves1 root = case (genTree x) of
                 [] -> [x] 
                 xs -> concatMap leaves1 xs

что морально эквивалентно второму ответу sth.

Answer 3

(не совсем ответ на вопрос, но связанный)

Мне нравится представлять деревья как "ListT [] a". (ListT из пакета List во взломе)

Тогда ответом на этот вопрос является использование функции lastL.

"Monad m => ListT m a" - это монадический список, содержащий "a", где попытка получить следующий элемент списка (который может обнаружить, что такого элемента нет) является монадическим действием в "m".

Пример использования для ListT - программа, которая читает числа от пользователя до тех пор, пока пользователь не наберет число и напечатает сумму чисел после каждого ввода:

main =
  execute . joinM . fmap print .
  scanl (+) 0 .
  fmap (fst . head) .
  takeWhile (not . null) .
  fmap reads .
  joinM $ (repeat getLine :: ListT IO (IO String))

Где repeat, scanl и takeWhile от Data.List.Class. Они работают как для обычных, так и для монадических списков.

joinM :: List l => l (ItemM l a) -> l a -- (l = ListT IO, ItemM l = IO)
execute :: List l => l a -> ItemM l () -- consume the whole list and run its actions

Если вы знакомы с Python, итераторы / генераторы python являются "ListT IO" s.

При использовании [] вместо IO в качестве монады монадического списка, получается дерево. Зачем? Представьте себе список, в котором получение следующего элемента является действием в монаде списка - монада списка означает, что есть несколько опций, поэтому существует несколько «следующих элементов», что делает его деревом.

Вы можете создавать монадические списки либо с помощью функций более высокого порядка (как в примере выше), либо с cons, либо с помощью нотации генератора питона (с yield), используя монадный преобразователь GeneratorT из generator упаковка в взломе.

Отказ от ответственности: ListT и GeneratorT никоим образом не используются широко. Я написал их, и я не знаю других пользователей, кроме себя. Есть несколько пользователей эквивалентных ListT s, таких как пользователь из вики Haskell, NondetT и другие.

Answer 4

flatten node = node : concatMap flatten (genTree node)