Попытка построить деревья в Хаскеле - PullRequest
Новая
       16

Попытка построить деревья в Хаскеле

0 голосов
/ 22 сентября 2018

Я пытаюсь использовать функцию развертывания для построения деревьев. 

Tree t = Leaf | Node (Tree t) t (Tree t)

unfoldT :: (b -> Maybe (b, a, b)) -> b -> Tree a
unfoldT f b =
    case f b of
      Nothing -> Leaf
      Just (lt, x, rt) -> Node (unfoldT f lt) x (unfoldT f rt)

Функция построения должна создать дерево с высотой, равной предоставленному числу, а также быть пронумерованным вПо заказу мода.Базовый вариант: сборка 0 = Лист, а следующая сборка 1 = Узел (Лист 0 Лист). 

build :: Integer -> Tree Integer

Моя попытка ее решить: 

build n = unfoldT (\x -> Just x) [0..2^n-2]

Я не совсемуверен, как построить дерево здесь.Хотелось бы, чтобы кто-нибудь указывал мне правильное направление.

Редактировать 1:

Если бы я использовал 2-кортеж, что бы я комбинировал?Мне нужно иметь возможность ссылаться на текущий узел, его левое поддерево и его правое поддерево как-то верно?

Ответы [ 2 ]

0 голосов
/ 22 сентября 2018

Если бы я использовал 2-кортеж, что бы я комбинировал?

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

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

Конечно, мы знаем, потому что дерево, которое мы строим, полностью сбалансировано и полностью заполнено.

Итак, если у нас есть такая функция, как 

-- build2 (depth, startNum)
build2 :: (Int, Int) -> Tree Int

, мы можем использовать ее точно так же , чтобы построить обе половины , например, build [0..14]tree: 

build [0..14] == build2 (4,0) == Node (build2 (3,0)) 7 (build2 (3,8))

Правильно?

Но если мы не хотим связываться с прямыми вычислениями всех участвующих чисел, мы могли бы организовать вышеупомянутую передачу состояний с помощьюПоверните к интерфейсу build2: 

--     depth, startNum    tree, nextNum
build3 :: (Int, Int) -> (Tree Int, Int)

и используйте его как 

build :: Int -> Tree Int                 -- correct!
build depth = build3 (depth, 0)          -- intentionally incorrect

build3 :: (Int, Int) -> (Tree Int, Int)  -- correct!
build3 (depth, start) = Node lt n rt     -- intentionally incorrect
  where
       (lt, n) = build3 (depth-1, start)   -- n is returned
       (rt, m) = build3 (depth-1, n+1)     --  and used, next

Вам нужно настроить выше, чтобы соединить все части вместе ( следуйтетипы! ), конечно, реализуя недостающие фрагменты и заботясь о угловых / базовых случаях.

Сформулировать это как развернутое будет следующим шагом.

0 голосов
/ 22 сентября 2018

Если бы я использовал 2-кортеж, что бы я комбинировал?

Я бы рекомендовал передать оставшуюся глубину, а также смещение слева: 

build = unfoldT level . (0,)
  where
    level (_, 0) = Nothing
    level (o, n) = let mid = 2^(n-1)
                   in ((o, n-1), o+mid-1, (o+mid, n-1))
...