Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Enumerating BinTrees by depth
import qualified Control.Monad.WeightedSearch as W
import Data.List (sortBy)
import Data.Ord (comparing)
import Control.Applicative
data BTree = Leaf | Branch BTree BTree deriving (Show, Eq)
-- I can lazily list all the btrees
btrees :: W.T Integer BTree
btrees = pure Leaf <|> W.weight 1 (Branch <$> btrees <*> btrees)
-- Now, let's consider this function
depth :: BTree -> Integer
depth Leaf = 0
depth (Branch b1 b2) = 1 + max (depth b1) (depth b2)
-- I'd like to generate the btrees in an order such that
-- `test btrees == True`, where":
test :: W.T Integer BTree -> Bool
test ts = ls == sortBy (comparing depth) ls
where ls = take 1000 $ W.toList ts
-- that is, trees should be ordered by depth
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.