找到一個項目是否被包含在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元樹

回答

相關問題