data InternalTree a = ILeaf
| IBranch a (InternalTree a) (InternalTree a)
deriving Show
takeTree :: Int -> InternalTree a -> InternalTree a
takeTree 0 _ = ILeaf
takeTree _ ILeaf = ILeaf
takeTree n (IBranch a lt rt) = IBranch a (takeTree (n-1) lt) (takeTree (n-1) rt)
takeTreeWhile :: (a -> Bool) -> InternalTree a -> InternalTree a
takeTreeWhile _ ILeaf = ILeaf
takeTreeWhile p (IBranch a lt rt)
| p a = IBranch a (takeTreeWhile p lt) (takeTreeWhile p rt)
| otherwise = ILeaf
----- some tests -----
t = let t' = IBranch 1 ILeaf ILeaf
in IBranch 2 t' t'
t2 = IBranch 1 -- 1
(IBranch 2 ILeaf ILeaf) -- / \
(IBranch 2 -- 2 2
(IBranch 3 -- / \ / \
(IBranch 4 ILeaf ILeaf) -- - - 3 3
(ILeaf)) -- / \ / \
(IBranch 3 ILeaf ILeaf)) -- 4 - - -
-- / \
-- - -
main = do
putStrLn $ show $ takeTree 0 t
putStrLn $ show $ takeTree 1 t
putStrLn $ show $ takeTree 0 t2
putStrLn $ show $ takeTree 2 t2
putStrLn $ show $ takeTree 4 t2
putStrLn $ show $ takeTree 9 t2
putStrLn $ show $ takeTree (-2) t2
putStrLn $ show $ takeTreeWhile (>0) t2
putStrLn $ show $ takeTreeWhile (<3) t2
putStrLn $ show $ takeTreeWhile (\_ -> True) t2
putStrLn $ show $ takeTreeWhile (\_ -> False) t2
{-
Because the way takeTree definied, if the level argument is negative value,
then the result will be entire tree.
This is because "takeTree 0 _" definition will never be called.
The stop condition will be "takeTree _ ILeaf" definition.
(This means it recurs to all branchs to all leaves.)
We could:
(1) Add new definition:
takeTree n _ | n < 0 = error "Level cannot be negative."
(2) Or use n+k pattern, replace last definition to become:
takeTree (n+1) (IBranch a lt rt) = IBranch a (takeTree n lt) (takeTree n rt)
-}
This entry was posted
on Wednesday, May 23rd, 2007 at 3:35 pm and is filed under Haskell - SOE.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.