TreeSearch.hs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

module TreeSearch where

import Data.Tree.Zipper
import Data.Maybe

-- findTree :: PosType t => (a -> Bool) -> TreePos t a -> Maybe (TreePos t a)
findTree :: (a -> Bool) -> TreePos Full a -> Maybe (TreePos Full a)
findTree p loc = if p (label loc)
    then Just loc
    else depthFirst loc >>= findTree p
        
depthFirst :: TreePos Full a -> Maybe (TreePos Full a)
depthFirst loc = case firstChild loc of
    Just x -> Just x
    Nothing -> case next loc of
        Just x -> Just x
        Nothing -> case parent loc of
            Just x -> next x
            Nothing -> Nothing