Создать случайные данные из пользовательского типа

Question

У меня определен следующий пользовательский тип

data Tree = Empty | Node Tree Tree

Я хочу создать случайные Tree s с заданным числом узлов n, которые затем я могу передать другой функции, которая вычисляет глубинудерево

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

Какой самый простой способ добиться этого?

РЕДАКТИРОВАТЬ: я попытался с подходом, аналогичным подходу Алек в ответе ниже, который возвращает случайный IO Tree.Однако есть несколько других функций, которым я должен передать эти случайные Tree с, которые я не могу контролировать.Для этого требуется аргумент типа Tree, а не IO Tree, поэтому это решение не совсем подходит для моих целей.

Answer 1

Интересный вопрос!Эту проблему лучше всего решить в двух частях: создание списка Tree s с необходимым количеством узлов, а затем выбор одного значения случайным образом из этого списка.

Мы начнем с первой проблемы:учитывая число n , создайте список всех Tree с n Node с.Но как бы мы это сделали?Давайте попробуем несколько простых случаев для небольших n с.Для n = 0 у нас есть только один выбор: Empty.(С этого момента я буду сокращать Node и Empty как N и E, чтобы уменьшить количество набираемых символов.) Для n = 1 у нас также есть только один выбор: N E E.Для n = 2 у нас есть два случая, которые мы можем сгенерировать из случая n = 1, заменив один E на N E E:

N (N E E) E
N E (N E E)

Для n = 3 мы можем повторить ту же процедуру, заменяя каждый E по очереди в каждом случае на N E E, чтобы найти все возможные места, где мы можем добавить дополнительный узел:

N (N (N E E) E) E
N (N E (N E E)) E
N (N E E) (N E E)
N E (N (N E E) E)
N E (N E (N E E))

Мы можем сделать это с помощью рекурсивной функции:

allWithNum :: Int -> [Tree]
allWithNum 0 = [Empty]
allWithNum n = nub $ concatMap subWithNode (allWithNum $ n-1)
  where
    subWithNode = fmap snd . filter fst . go False
      where
        go False Empty = [(True,Node Empty Empty),(False,Empty)]
        go True  Empty = [(True,Empty)]
        go hasSubdNode (Node x y) = do
            (subdX, newX) <- go hasSubdNode x
            (subdY, newY) <- go subdX y
            return (subdY, Node newX newY)

(Обратите внимание, что здесь используется nub из Data.List, а также требуется Tree для экземпляра Eq.)

Большая часть работы здесь выполняется в go, который перемещается вдоль Tree, подставляя Node Empty Empty в каждый Empty по очереди, отслеживая в своем первом аргументе, имеет ли подстановкасделано еще.

Теперь по второй проблеме: как выбрать случайный элемент из этого списка?Это можно сделать с помощью функций в модуле System.Random из пакета random, с помощью choose (0, length_of_list) для выбора индекса и последующего получения значения по этому индексу с помощью (!!).

Answer 2

QuickCheck ваш друг. Сейчас самое время начать изучать его.

Вы спрашивали о генерации случайных деревьев. В терминах QuickCheck мы генерируем произвольных деревьев, используя класс типов Arbitrary.

class Arbitrary a where
  arbitrary   :: Gen a
  coarbitrary :: a -> Gen b -> Gen b

Gen - это класс типов для генераторов тестовых данных.

Генераторы тестовых данных: Тип Gen

Данные испытаний формируются генераторами данных испытаний. QuickCheck определяет генераторы по умолчанию для большинства типов, но вы можете использовать свои собственные с forAll, и нужно будет определить ваши собственные генераторы для любых новых типы, которые вы вводите.

Генераторы имеют типы вида Gen a; это генератор для значения типа a. Тип Gen - это монада, поэтому Haskell's do Синтаксис и стандартные монадические функции могут быть использованы для определения генераторы.

Генераторы построены поверх функции

choose :: Random a => (a, a) -> Gen a

, который делает случайный выбор значения из интервала с равномерное распределение. Например, чтобы сделать случайный выбор между элементы списка, используйте

do i <- choose (0, length xs-1)
   return (xs !! i)

В своем вопросе вы говорите, что хотите генерировать деревья с определенным количеством узлов. Arbitrary экземпляр для этого

instance Arbitrary Tree where
  arbitrary = sized tree'
    where tree' 0 = return Empty
          tree' n | n > 0 = do
            lsize <- choose (0, n - 1)
            l <- tree' lsize
            r <- tree' (n - lsize - 1)
            return $ Node l r

Этот экземпляр учитывает параметр внешнего размера благодаря sized.

Размер тестовых данных

Генераторы тестовых данных имеют неявный параметр size; быстрая проверка начинается с генерации небольших тестовых случаев и постепенно увеличивает размер по мере тестирования. Различные генераторы тестовых данных интерпретируют параметр размера по-разному: некоторые игнорируют его, а список генератор, например, интерпретирует его как верхнюю границу длины сгенерированных списков. Вы можете использовать его по своему усмотрению. собственные генераторы тестовых данных. Вы можете получить значение размера параметр с использованием

sized :: (Int -> Gen a) -> Gen a

sized g вызывает g, передавая ему текущий размер в качестве параметра. За Например, чтобы сгенерировать натуральные числа в диапазоне от 0 до n, используйте

sized $ \n -> choose (0, n)

Внутренний генератор tree' берет количество оставшихся узлов и создает дерево, создавая Empty, когда параметр равен нулю, или создавая Node, чье левое поддерево имеет размер от 0 до n - 1 ( меньше 1 для учета самого узла) и чье правое поддерево получает остальные элементы.

Скажем, у вас есть функция

nodes Empty = 0
nodes (Node l r) = 1 + nodes l + nodes r

и мы хотим видеть, что он правильно подсчитывает узлы в 10-узловых деревьях. После определения свойства

prop_nodes_count = forAll (resize 10 arbitrary) (\t -> nodes t == 10)

мы успешно протестировали его в GHCi с

λ> quickCheck prop_nodes_count
+++ OK, passed 100 tests.

Приведенный выше код использует resize для определения размера генерируемых деревьев.

Чтобы продемонстрировать, что вы можете создать чистый список деревьев, , т.е. , [Tree], а не IO [Tree], мы будем использовать простой standin.

print_trees :: [Tree] -> IO ()
print_trees = print

В конечном счете, генераторы QuickCheck являются случайными и, следовательно, сохраняют состояние, поэтому генерировать их из вашего действия main очень просто.

main :: IO ()
main = do
  trees <- sample' (resize 0 arbitrary)
  print_trees $ take 1 trees
  trees' <- sample' (resize 1 arbitrary)
  print_trees $ take 1 trees'
  trees'' <- sample' (resize 2 arbitrary)
  print_trees $ take 2 trees''

Выполнение работы здесь sample' с типом Gen a -> IO [a]. То есть при запуске внутри действия IO, sample' создает список того, что вы хотите сгенерировать, произвольные деревья в этом случае. Связанная функция sample имеет тип Show a => Gen a -> IO (), что означает, что она идет вперед и печатает сгенерированные тестовые данные.

Вывод вышеуказанной программы после добавления deriving Show к вашему определению Tree равен

[Empty]
[Node Empty Empty]
[Node (Node Empty Empty) Empty,Node Empty (Node Empty Empty)]

Answer 3

Думайте об этом как о простой рекурсивной проблеме.Единственная сложность заключается в том, что для получения случайного числа требуется либо явная передача через генератор, либо работа в пределах IO.Для простоты я буду придерживаться последнего.

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)