modular pruning with lazy tree

prunetree.hs

{-# LANGUAGE StandaloneDeriving #-}

import Debug.Trace

data BTree a = L
             | N a (BTree a) (BTree a)
          
deriving instance (Show a) => Show (BTree a)

maketree :: Int -> Int -> BTree Int
maketree bound n 
  | n > bound = L 
  | otherwise = trace ("debug:" ++ show n) (N n (maketree bound (n+1)) (maketree bound (n+2)))
  
pruneTree :: Int -> BTree Int -> BTree Int
pruneTree _ L = L 
pruneTree m (N n tr1 tr2) 
  | n > m = L
  | otherwise = N n (pruneTree m tr1) (pruneTree m tr2)

main = do
  let tr = maketree 10 1
  print (pruneTree 2 tr)
  -- checkWith (print tr) 

-- > $ ./prunetree 
-- > debug:1
-- > debug:2
-- > debug:3
-- > debug:4
-- > debug:3
-- > N 1 (N 2 L L) L