从自定义类型创建随机数据 [英] Create random data from custom type

问题描述

我定义了以下自定义类型

I have the following custom type defined

data Tree = Empty | Node Tree Tree

我想用给定数量的节点n创建随机的Tree，然后可以将其传递给另一个计算树的深度的函数

I want to create random Trees with a given number of nodes n that I can then pass to another function which calculates the depth of the tree

depth :: Tree -> Int
depth Empty = 0
depth Node t1 t2 = (maximum [depth t1, depth t2]) + 1

哪种方法最容易实现?

我在下面的答案中尝试了与Alec类似的方法，该方法返回一个随机IO Tree.但是，还有其他一些函数需要将此随机Tree传递给它们，而我无法控制这些函数.这些要求使用类型为Tree而不是IO Tree的参数，因此该解决方案对于我的目的并不完全有效.

I have tried with an approach similar to that of Alec in an answer below, which returns a random IO Tree. However, there are several other functions I need to pass this random Trees to, over which I have no control. These require an argument of type Tree, not IO Tree so this solution doesn`t quite work for my purposes.

推荐答案

将其视为简单的递归问题.唯一的麻烦是，获取随机数需要显式地通过生成器进行线程化，或者需要在IO中进行.为了简单起见，我会坚持使用后者.

Think of it as a simple recursive problem. The only complication is that getting a random number requires either threading through explicitly a generator, or working within IO. For simplicity, I'll stick with the latter.

import System.Random

data Tree = Empty | Node Tree Tree

-- | Generate a tree of the given size
arbitraryTree :: Int -> IO Tree
arbitraryTree treeSize
  | treeSize <= 1 = pure Empty  -- base case, tree of size 1
  | otherwise = do
      leftSize <- randomRIO (0,treeSize - 1)
      let rightSize = treeSize - 1 - leftSize

      leftSubtree <- arbitraryTree leftSize
      rightSubtree <- arbitraryTree rightSize

      pure (Node leftSubtree rightSubtree)

这篇关于从自定义类型创建随机数据的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！