항목이 나는 데이터 유형을 가지고

Question

K 진 트리에 포함되어 있는지 여부를 찾기

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

내가 항목이 포함되어 있는지 여부에 관해서는 참 또는 거짓 반환하는 함수를 작성하고 싶습니다 내 나무.

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

그래서 내가 노드 자체가 항목이며, 다음 재귀 노드 아동을위한 ktreeContains를 호출하지만 각 노드가 많은 아이를 가질 수 있기 때문에이 작업을 수행하는 방법을 이해하지 않습니다 여부를 찾을 필요가 실현.

나는 지금까지 가지고있는 코드가 옳다고 생각하지만 그렇지 않다면 나를 고쳐 주시기 바랍니다.

도움을 주신 데 감사드립니다. 그냥 관심 밖으로

Answer 1

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

Answer 2

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

, Leaf x 및 Node x []의 차이는 무엇인가?

Answer 3

나는 지루했기 때문에 Data.Foldable typeclass를 사용하여 솔루션을 일반화하기로 결정했습니다.

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는 KTree의 순회가 Data.Foldable 클래스에 의해 처리되는 ktreeContainsF 것을 제외하고 동일한 기능을한다. foldMap은 Monoid을 반환하므로 Any 모노 도형을 사용하여 검색 결과를 결합 할 수 있습니다. 그것은 조금 더 나은이를 이해하는 데 도움이된다면

---

는 ktreeContainsF는

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