Мне нужно создать функцию haskell, которая возвращает все возможные двоичные деревья, учитывая список целых чисел

Question

Как следует из названия, мне нужно это:

    getAllTrees :: [Int] -> [Tree Int]
    getAllTrees xs = undefined

, где дерево

    data Tree x 
      = Null
      | Leaf x
      | Node (Tree x) x (Tree x)

Я буду признателен за любую помощь, даже самую малую подсказку :) Спасибо

Answer 1

Мне обычно проще всего использовать монаду списка для подобных задач. Мы можем определить getAllTrees, рассуждая следующим образом:

Единственное дерево с нулевыми элементами: Null:

getAllTrees [] = return Null

Существует также только одно дерево одного элемента, а именно Leaf:

getAllTrees [x] = return $ Leaf x

Когда у нас более одного элемента, мы можем разделить список всеми возможными способами, чтобы определить, как мы должны переходить, а затем рекурсивно сгенерировать поддеревья из каждого списка. Допустим, у нас есть функция splits :: [a] -> [([a], [a])], которая возвращает все способы разбиения списка, например:

> splits [1..3]
[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]

Затем мы можем определить окончательный регистр getAllTrees, используя монаду списка. Это позволяет нам писать код, который выглядит так, как будто мы фокусируемся только на одном случае, и монада даст нам все комбинации.

getAllTrees xs = do
  (left, x : right) <- splits xs
  Node <$> getAllTrees left <*> pure x <*> getAllTrees right

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

Во второй строке используется аппликативный синтаксис, чтобы сказать, что мы хотим, чтобы результатом был список узлов, состоящий из всех комбинаций поддеревьев из списка left, фиксированного среднего элемента x и всех вложенных элементов. деревья из списка right.

Осталось только реализовать splits. Глядя на приведенный выше пример, легко понять, что мы можем просто взять inits и tails списка и zip их вместе:

splits xs = zip (inits xs) (tails xs)

Время быстрой проверки работоспособности в переводчике:

> mapM_ print $ getAllTrees [1..3]
Node Null 1 (Node Null 2 (Leaf 3))
Node Null 1 (Node (Leaf 2) 3 Null)
Node (Leaf 1) 2 (Leaf 3)
Node (Node Null 1 (Leaf 2)) 3 Null
Node (Node (Leaf 1) 2 Null) 3 Null
> length $ getAllTrees [1..5]
42

Похоже, мы закончили! Некоторые ключевые уроки:

• Попробуй сначала подумать о маленьких коробочках и отрасти оттуда.
• Монада списка полезна для кода, который должен генерировать все комбинации вещей.
• Вам не нужно делать все сразу. Работа с разделением списка по отдельности сделала код намного проще, чем это было бы в противном случае.