找到一个项目是否被包含在k元树

我有一个数据类型中找到一个项目是否被包含在k元树

data KTree a = Empty | Leaf a | Node a [KTree a] deriving (Eq, Show)

我想编写一个返回true或false作为一个项目是否被包含在一个功能我的树。

ktreeContains :: Eq a => a -> (KTree a) -> Bool 
ktreeContains _ Empty = False 
ktreeContains y (Leaf x) = (x==y) 
-- code for nodes goes here

于是我意识到我需要找到节点本身是否是该项目，然后递归调用为节点孩子ktreeContains，但我不知道如何做到这一点，因为每个节点可以有许多儿童。

我认为我到目前为止的代码是正确的，但如果没有，请随时纠正我。

任何帮助表示感谢，谢谢。

来源

2009-11-11 chirp

ktreeContains y (Node x ts) = x == y || (any . ktreeContains) y ts

来源

2009-11-11 23:30:11 Apocalisp

应该有（ktreeContains Y）在地图中的第一个参数。 – 2009-11-11 23:34:56

它应该是'any（ktreeContains y）ts' – sth 2009-11-11 23:36:53

也许编辑答案会比在答案更正后添加没有意义的评论更好。 – Apocalisp 2009-11-12 00:11:27

ktreeContains y (Node x ts) = x == y || any (ktreeContains y) ts

只是出于兴趣，什么是Leaf x和Node x []之间的区别？

来源

2009-11-12 01:12:55 dave4420

第一个没有孩子，另一个没有孩子。但是，“Leaf”可以代表一个搜索树的完整解决方案，它本质上无法恢复，“Node”可能代表一个部分解决方案，并且没有孩子意味着无法恢复或者有些方法被修剪。 – yairchu 2009-11-12 14:39:01

我很无聊，所以我决定使用Data.Foldable类型类概括解决方案。

import Data.Monoid 
import Data.Foldable hiding (any) 

data KTree a = Empty | Leaf a | Node a [KTree a] deriving (Ord, Eq, Show) 

ktreeContains :: Eq a => a -> (KTree a) -> Bool 
ktreeContains _ Empty = False 
ktreeContains y (Leaf x) = (x==y) 
-- code for nodes goes here 
ktreeContains y (Node x ts) = x == y || any (ktreeContains y) ts 

example1 = Empty 
example2 = Leaf 1 
example3 = Node 1 [Leaf 2] 
example4 = Node 2 [Leaf 1, Node 4 [Leaf 5, Leaf 3]] 

ktreeContainsF :: Eq a => a -> KTree a -> Bool 
ktreeContainsF y = getAny . foldMap (Any.(==y)) 

instance Foldable KTree where 
    foldMap f (Empty) = mempty 
    foldMap f (Leaf a) = f a 
    -- work out a possible ordering thats better than this 
    -- it works for now since we are only dealing with Equality 
    foldMap f (Node a x) = f a `mappend` (mconcat . map (foldMap f)) x

ktreeContains和ktreeContainsF是除了在ktreeContainsF的KTree的遍历由Data.Foldable类处理相同的功能。由于foldMap返回Monoid，因此可以使用Any monoid组合搜索结果。

如果它有助于更好一点理解这一点，ktreeContainsF是ktreeContainsMonoid更一般化的版本，其定义为

ktreeContainsMonoid y = getAny . Data.Foldable.foldl 
     -- combination function, implicit when using FoldMap 
     (\z x-> z `mappend` Any (x == y)) mempty -- also implicit in foldMap

来源

2009-11-13 13:42:14 barkmadley

找到一个项目是否被包含在k元树

回答

相关问题