реконструировать двоичное дерево с двумя списками после предварительного заказа и по порядку

ProgramBox

реконструировать двоичное дерево с двумя списками после предварительного заказа и по порядку

Post author:admin
Запись опубликована:7 апреля, 2023
Post category:Вопросы по программированию

#haskell

Вопрос:

— Приведены два списка, один отсортирован по предварительному заказу, другой отсортирован по порядку. И два списка из одного и того же двоичного дерева. С двумя списками двоичное дерево -реконструировано.

— Я не нашел функцию «rank» в Интернете. Мой профессор сказал нам, что функция «ранг» может выводить позицию одного элемента в списке.

Ошибка произошла в следующей строке, где использовалась функция «ранг».

Итак, у меня есть два вопроса.

Как работает функция «ранг»?
Правильно ли выражение «реконструировать :: [Int]-> IntTree» ? Я не уверен.

 main :: IO ()    -- This says that main is an IO action.
main = return () -- This tells main to do nothing

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)

reconstruct :: [Int]->IntTree
--  Pattern matching 
reconstruct (x:xs) y = Branch (reconstruct take((rank x y) xs) take ((rank x y) y)) x x (reconstruct drop ((rank x y) 1 xs) drop ((rank x y) 1 y))

после исправления

 import Data.List


main :: IO ()    -- This says that main is an IO action.
main = return () -- This tells main to do nothing

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)

--Two lists are given, one sorted by preorder, the other sorted by inorder. 
-- And the two lists are from the same binary tree. With the two lists the binary tree is reconstructed.

reconstruct :: [Int]->[Int]->IntTree
--  Pattern matching 
reconstruct [] [] = Empty
reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))
    where p = span (x/=) y 

reconstruct _ _ = error "incomplete pattern"

ошибка

 
E:HaskellUebungsblatt_2_Aufgabe_1.hs:15:32: error:
    * Couldn't match expected type `[Int] -> IntTree'
                  with actual type `IntTree'
    * The function `reconstruct' is applied to three arguments,
      but its type `[Int] -> [Int] -> IntTree' has only two
      In the first argument of `Branch', namely
        `(reconstruct take (length (fst p) xs) (fst p))'
      In the expression:
        Branch
          (reconstruct take (length (fst p) xs) (fst p))
          x
          (reconstruct drop (length (fst p) xs) (snd p))
   |
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

   |                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

E:HaskellUebungsblatt_2_Aufgabe_1.hs:15:44: error:
    * Couldn't match expected type `[Int]'
                  with actual type `Int -> [a0] -> [a0]'
    * Probable cause: `take' is applied to too few arguments
      In the first argument of `reconstruct', namely `take'
      In the first argument of `Branch', namely
        `(reconstruct take (length (fst p) xs) (fst p))'
      In the expression:
        Branch
          (reconstruct take (length (fst p) xs) (fst p))
          x
          (reconstruct drop (length (fst p) xs) (snd p))
   |
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

   |                                            ^^^^

E:HaskellUebungsblatt_2_Aufgabe_1.hs:15:50: error:
    * Couldn't match expected type `[Int] -> [Int]'
                  with actual type `Int'
    * The function `length' is applied to two arguments,
      but its type `[Int] -> Int' has only one
      In the second argument of `reconstruct', namely
        `(length (fst p) xs)'
      In the first argument of `Branch', namely
        `(reconstruct take (length (fst p) xs) (fst p))'
   |
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

   |                                                  ^^^^^^^^^^^^^^^^^

E:HaskellUebungsblatt_2_Aufgabe_1.hs:15:81: error:
    * Couldn't match expected type `[Int] -> IntTree'
                  with actual type `IntTree'
    * The function `reconstruct' is applied to three arguments,
      but its type `[Int] -> [Int] -> IntTree' has only two
      In the third argument of `Branch', namely
        `(reconstruct drop (length (fst p) xs) (snd p))'
      In the expression:
        Branch
          (reconstruct take (length (fst p) xs) (fst p))
          x
          (reconstruct drop (length (fst p) xs) (snd p))
   |
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

   |                                                                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

E:HaskellUebungsblatt_2_Aufgabe_1.hs:15:93: error:
    * Couldn't match expected type `[Int]'
                  with actual type `Int -> [a1] -> [a1]'
    * Probable cause: `drop' is applied to too few arguments
      In the first argument of `reconstruct', namely `drop'
      In the third argument of `Branch', namely
        `(reconstruct drop (length (fst p) xs) (snd p))'
      In the expression:
        Branch
          (reconstruct take (length (fst p) xs) (fst p))
          x
          (reconstruct drop (length (fst p) xs) (snd p))
   |
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

   |                                                                                             ^^^^

E:HaskellUebungsblatt_2_Aufgabe_1.hs:15:99: error:
    * Couldn't match expected type `[Int] -> [Int]'
                  with actual type `Int'
    * The function `length' is applied to two arguments,
      but its type `[Int] -> Int' has only one
      In the second argument of `reconstruct', namely
        `(length (fst p) xs)'
      In the third argument of `Branch', namely
        `(reconstruct drop (length (fst p) xs) (snd p))'
   |
15 | reconstruct (x:xs) y = Branch (reconstruct take (length (fst p) xs) (fst p)) x (reconstruct drop (length (fst p) xs) (snd p))

   |                                                                                                   ^^^^^^^^^^^^^^^^^
[Finished in 0.5s]

1. Я понятия не имею, что rank такое — это, конечно, не стандартная функция Haskell. Вы должны спросить своего профессора.

2. Тип подписи для reconstruct не соответствует количеству предоставленных аргументов. Если входные данные представляют собой два списка, то, возможно reconstruct :: [Int] -> [Int] -> IntTree . Я думаю, что у вас в голове неправильный приоритет привязки функций — f a (b) c = f a b c нет f (a b) c (примечание f (a) = f a , f (a b) /= f a b ). Из описания, rank это просто стандартный Haskell find . Вам может быть полезно использовать splitAt вместо drop , take .

Ответ №1:

 reconstruct :: [Int] -> [Int] -> IntTree
reconstruct [] [] = Empty
reconstruct (x:xs) y = let (l,_:r) = span (x /=) y
                           (l',r') = splitAt (length l) xs
                       in Branch (reconstruct l' l) x (reconstruct r' r)
reconstruct _ _ = error "incomplete pattern"

Похоже, это сработало в одном тестовом примере, который я пробовал, и это в значительной степени то, что вы намеревались написать (я думаю). Это приводит к проблемам, если узлы могут иметь левых потомков с равным содержимым для себя (?). Я думаю, что это может пройти l дважды (из-за length ), вы могли бы решить это с помощью zip и некоторой дополнительной логики, если это необходимо.

1. Большое спасибо. Я пытаюсь это понять

2. @A Tayler ghci> span (/=4) [1,2,3,4,5,6,7] ([1,2,3],[4,5,6,7]) Я нашел пример функции «span». Но я не понимаю, что означают «(l, : r)» и «» (l, : r)»»? Могу ли я использовать fst и sec для получения списков?

3. (l, _:r) связывает кортеж, вторым элементом которого является непустой список. l становится первым элементом, r становится tail вторым элементом. Вы могли бы написать p = span ... l = fst p r = tail . snd $ p , но, как вы можете видеть, это намного более подробно. _ говорит, что мы игнорируем head список в правой половине кортежа — технически, потому что мы «знаем», что это x , это реплицирует 1 в вашем коде, который удаляет x .

4. Я новичок в Haskell, брат

5. Попробуйте написать, ghci > (l,_:r) = span (/=4) [1,2,3,4,5,6,7] затем изучите значения l , r .

Ответ №2:

Функция `reconstruct’ применяется к трем аргументам, но ее тип `[Int] -> [Int] -> IntTree’ имеет только два

 (reconstruct take (length (fst p) xs) (fst p))

Вы применяете reconstruct функции к 3 аргументам, как указано в сообщении об ошибке: take , (length (fst p) xs) и (fst p) .

Аналогичная ошибка с приложением length: вы передаете ему 2 аргумента.

Возможно, вы хотели передать FUNCTION(ARGUMENT) в качестве единственного аргумента следующей функции. Это не работает так, это будет рассматриваться как 2 аргумента: FUNCTION и (ARGUMENT) . Вместо этого вы должны использовать (FUNCTION ARGUMENT) , или (FUNCTION (ARGUMENT)) , если АРГУМЕНТ сложный.

Кроме того, вы не должны группировать аргументы для функций отдельно от функции: take (length ... LIST) . Это рассматривается как единственный аргумент (length ... LIST) . Они должны быть на одном уровне скобок с функцией.

Итак, ваш первый вызов reconstruct скорее будет выглядеть как:

 (reconstruct (take (length (fst p)) xs) (fst p))

И, вероятно, остальная часть выражения имеет аналогичные проблемы