Haskell新手求助：生成Arbitrary二叉树的更惯用实现方式

嘿，作为Haskell新手能想到这种思路已经很棒啦！你提到的“先生成布尔值再分支”的写法确实有点冗余，Haskell的QuickCheck库早就为这种“随机选择构造器”的场景提供了更优雅的解决方案——用组合子来替代手动的布尔判断，完全贴合函数式编程的风格。

核心思路：用oneof简化二选一逻辑 #

QuickCheck的oneof组合子可以直接从多个生成器中随机挑选一个执行，完美替代你手动生成布尔值再分支的逻辑。先看基础版的实现：

首先假设你的二叉树定义是这样的：

data BinaryTree a = Nil | Node a (BinaryTree a) (BinaryTree a) deriving (Show, Eq)

然后用oneof实现Arbitrary实例：

import Test.QuickCheck

instance Arbitrary a => Arbitrary (BinaryTree a) where
  arbitrary = oneof
    [ return Nil
    , Node <$> arbitrary <*> arbitrary <*> arbitrary
    ]

这里oneof接受一个生成器列表，会等概率地选择其中一个生成器来生成值——要么返回空树Nil，要么用Applicative风格生成一个非空的Node（自动递归生成左右子树）。整个过程完全不需要手动处理布尔值，代码更简洁也更符合Haskell的惯用写法。

进阶：用frequency控制生成概率 #

如果觉得等概率生成空树和非空树会导致生成的树大多偏“小”，可以用frequency组合子来调整权重，让非空树的生成概率更高：

instance Arbitrary a => Arbitrary (BinaryTree a) where
  arbitrary = frequency
    [ (1, return Nil)    -- 1份概率生成空树
    , (3, Node <$> arbitrary <*> arbitrary <*> arbitrary)  -- 3份概率生成非空树
    ]

frequency的参数是权重-生成器的元组，权重数值越大，对应的生成器被选中的概率越高。上面的例子里，生成非空树的概率是空树的3倍，能生成更有代表性的测试用例。

更可控的生成：用sized限制树的大小 #

如果想让生成的树大小随着测试的“规模参数”动态调整（避免生成无限大的树），可以结合sized组合子：

instance Arbitrary a => Arbitrary (BinaryTree a) where
  arbitrary = sized arbitraryBinaryTree

arbitraryBinaryTree :: Arbitrary a => Int -> Gen (BinaryTree a)
arbitraryBinaryTree 0 = return Nil
arbitraryBinaryTree n = frequency
  [ (1, return Nil)
  , (4, Node <$> arbitrary 
             <*> arbitraryBinaryTree (n `div` 2) 
             <*> arbitraryBinaryTree (n `div` 2))
  ]

sized会把当前测试的大小参数传递给我们的自定义生成函数：当大小为0时直接返回空树；当大小大于0时，按权重选择生成空树或拆分大小生成左右子树，这样生成的树会更均匀，也更符合测试的需求。

这些组合子都是QuickCheck为了简化生成器编写而设计的，完全避免了手动处理随机值的分支逻辑，是Haskell社区惯用的写法哦！

内容的提问来源于stack exchange，提问作者danielspaniol