Обход типа данных с рекурсивным списком двоичных деревьев в функции
Я создал рекурсивное бинарное дерево, в котором может быть неограниченное количество детей:
data Tree a = Leaf a
| Node [Tree a]
Моя проблема заключается в синтаксисе при создании функции для обхода дерева.
Скажем, я хочу сделать что-то простое, например дать аргумент 1, а затем узнать Bool, встречается ли 1 в дереве. У меня проблема с определением функции, когда Node является [Tree a] вместо Node [Leaf root Leaf]. Я не привык к функции, вызывающей список в переменной.
Вот как это будет работать с более простым рекурсивным типом данных:
occs :: Eq a => a -> Tree a -> Bool
occs x (Leaf y) = x == y
occs x (Node left y right) = x == y || occs x left || occs x right
Однако (Node left y right) больше не является правильным, потому что Node теперь является перечисленным деревом [Tree a]. Как вы можете написать перечисленное дерево [Tree a] в качестве переменной для управления?
Ожидаемые результаты будут True или False, если он появится, но проблема в основном заключается в синтаксисе идентификации перечисленных [Tree a] в функции. Я пробовал несколько способов написать его, и он всегда возвращает ошибку.
В Leaf y вы сопоставление с образцом конструктор Leaf a. Допустимые совпадения для вашего конструктора Node [Tree a]: Node _, Node [], Node [x] (или Node (x:[])), Node [x,y] (или Node (x:y:[])) и так далее.
Какое определение для example4?
Ответы 2
Вы просто хотите рекурсивно проверить, содержит ли какая-либо из ветвей (именно так я называю деревья в списке) x. К счастью, в Prelude есть функция Любые, которая упрощает эту задачу:
occs :: Eq a => a -> Tree a -> Bool
occs x (Leaf y) = x == y
occs x (Node branches) = any (occs x) branches
(any тоже очень легко реализовать самому при желании)
Таким образом, вы можете назвать его как хотите, и он просто представляет собой список. Но последний вопрос: как мне создать пример для тестирования. example :: Tree a example = Node [(Leaf 1) (Leaf 7) (Leaf 8)]
это выглядит нормально, хотя тип Tree a Int (вместо Int подойдет любой числовой тип, но на самом деле это не имеет значения).
Кроме того, что вы имеете в виду, что я могу реализовать any, если захочу. Можно ли его определить вместо вызова библиотечной функции?
Да, все, что я пытался сказать, это не какая-то "волшебная" функция, предоставляемая нам стандартной библиотекой - как и большинство библиотечных функций, она существует для удобства, но может быть легко реализована в нескольких строках Haskell, если вам нужно . Поскольку он предоставляется нам, вам никогда не нужно писать его самостоятельно, кроме как в качестве упражнения.
Не могли бы вы показать мне? Было бы очень полезно понять функцию. Большое спасибо, что помогли мне, кстати! Ответ был очевиден, как только я его увидел, но написание примеров для его проверки отняло у меня некоторое время.
в комментарии нет места, чтобы сделать это, конечно, не для того, чтобы правильно изложить это, но я настоятельно рекомендую вам попробовать это самостоятельно, но вот несколько важных советов. Это очень простая рекурсивная функция: базовый случай — any p [] = False, рекурсивный случай — any p (x:xs), вам нужно проверить, является ли p x истинным или ложным, и дать соответствующий результат (один включает рекурсивный вызов any p xs, другой может дать ответ сразу ).
Я создал соответствующую ей функцию, но она не работает в реальной функции, где использовалось any. helper p [] = False helper p (x:xs) | p == x = True | otherwise = helper p xs
Нет, не будет. Подумайте об этом логически. Вы хотите сказать, удовлетворяет ли какой-либо элемент в списке p. Итак, вы тестируете p на первом элементе: если он проходит, нужно ли вам проверять остальную часть списка? Если это не удается, вы хотите дать немедленный ответ «нет»? Это то, что делает ваша функция выше.
Итак, я написал этот новый, и он компилируется, но когда я проверяю его на примере, он выдает ошибку. Код: helper p [] = False helper p (x : xs) | p x = True | otherwise = helper p xs
* No instance for (Eq (Tree2 Int)) arising from a use of occs * В выражении: occs example5` In an equation for it: it = occs example5`
Выкладываю полный код. Он не будет тестировать пример, но он компилируется. Я не уверен, что означает сообщение об ошибке выше.
@Drake Судя по вашей ошибке, у вас есть example5, которое, как я полагаю, является деревом, и вы звоните occs example5 для запуска теста. Но occs принимает два аргумента, а не один. Это должно быть, например. occs 7 example5.
ДУХХХХХ! Я такой идиот, ты совершенно прав. Я был настолько сосредоточен на коде, что забыл, что он делает. Всем большое спасибо, вы все были восхитительны
Поскольку Робин Зигмонд дал ответ на ваш вопрос: «Как вы можете написать перечисленное дерево [Tree a] в качестве переменной для манипулирования?», Я попытаюсь ответить по-другому.
I created a recursive binary tree where there can be unlimited children:
data Tree a = [...]
Тогда он не бинарный, а н-арный.
Этот точный тип уже существует в пакете containers в модуле Data.Tree.
Data.Tree для него определено несколько экземпляров классов типов, и один из них — Foldable, а функция, которую вы пишете, уже находится в Data.Foldable под именем elem и имеет тип:
elem :: (Eq a, Foldable t) => a -> t a -> Bool
Поэтому, если вы выбрали тип данных н-арное дерево, Data.Tree и elem будут правильным выбором.
Если, с другой стороны, вам нужно фактическое двоичное дерево с двумя дочерними узлами, определение этого и создание экземпляра Foldable даст вам elem таким же образом:
{-# LANGUAGE DeriveFoldable #-}
data BinaryTree a
= Leaf
| Node a (BinaryTree a) (BinaryTree a)
deriving (Foldable)
-- now `elem` comes for free
Редактировать: По предложению amalloy вместо этого был получен экземпляр Foldable.
Но поскольку elem ограничен только Eq a, а не Ord a, вы не можете получить поиск О (журнал п), как вы могли бы сделать для двоичного дерева поиск, поэтому вам придется называть его как-то иначе, если вы хотите:
occs :: Ord a => a -> BinaryTree a -> Bool
occs _ Leaf = False
occs x (Node y left right) =
case x `compare` y of
LT -> occs x left
EQ -> True
GT -> occs x right
Написание экземпляров Foldable вручную быстро утомляет. Вместо этого создайте их с помощью DeriveFoldable.
Мы не сможем помочь вам понять, что пошло не так с вашей попыткой, если вы не покажете нам свою попытку. Поэтому включите код, который, по вашему мнению, должен работать, но не работает, вместе с полученным сообщением об ошибке.