Generating random binary search trees with the Arbitrary typeclass

Question

I am working on a problem set where I must write an arbitrary instance for binary search trees. Here is the code I've written so far:

data Tree e = E | N (Tree e) e (Tree e)

insert :: (Ord e) => e -> Tree e -> Tree e
-- assume this is implemented, so I can use it below

instance (Ord a, Arbitrary a) => Arbitrary (Tree a) where
    arbitrary :: Gen (Tree a)
    arbitrary = sized gen
      where
        gen :: Int -> Gen a
        gen n =
          frequency
            [
              (1, return E),
--                         vvvvvvvvv problematic vvvvvvvvvv
              (n, return $ insert (4::Int) (gen (n `div` 2)))
            ]

I'm unsure of how to get the second line of the frequency list to type check. I can see gen returns a Gen Tree and insert requires a Tree for its second argument, but I'm not sure how to restructure the code with that knowledge. It is required I use the insert function, however. Another problem is I need to get random element values, but I've put that aside for now and made every new element a 4 :: Int.

willeM_ Van Onsem · Accepted Answer · 2022-03-04 23:50:44Z

3

gen (n `div` 2) has type Gen (Tree a), so you should fmap that tree, so:

instance (Ord a, Arbitrary a) => Arbitrary (Tree a) where
    arbitrary = sized gen
      where gen n = frequency [
                (1, return E)
              , (n, insert <$> arbitrary <*> gen (n `div` 2))
              ]

This will thus generate an arbitrary value, then an arbitrary Tree with size n `div` 2, and then return the result of an insert with that arbitrary value for that arbitrary subtree.

answered Mar 4, 2022 at 23:50

willeM_ Van Onsem

482k33 gold badges483 silver badges624 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Generating random binary search trees with the Arbitrary typeclass

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related