在预订和按顺序之后用两个列表重建二叉树

问题描述 投票:0回答:2

- 给出了两个列表,一个按预订排序,另一个按顺序排序。这两个列表来自同一个二叉树。使用这两个列表,二叉树是--reconstructed。

- 我还没有在网上找到“排名”功能。我的教授告诉我们,函数“rank”可以输出列表中一个元素的位置。

在使用函数“rank”的以下行中发生错误。

所以我有两个问题。

  1. 功能如何“排名”?
  2. 表达式“reconstruct :: [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:\Haskell\Uebungsblatt_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:\Haskell\Uebungsblatt_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:\Haskell\Uebungsblatt_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:\Haskell\Uebungsblatt_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:\Haskell\Uebungsblatt_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:\Haskell\Uebungsblatt_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]

haskell
2个回答
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),如果需要,你可以用zipand和一些额外的逻辑来解决这个问题。


0
投票

函数`reconstruct'应用于三个参数,但其类型`[Int] - > [Int] - > IntTree'只有两个

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

您将reconstruct函数应用于3个参数,如错误消息中所述:take(length (fst p) xs)(fst p)

类似的错误是长度应用程序:您传递2个参数。

也许你的意思是将FUNCTION(ARGUMENT)作为单个论证传递给下一个函数。它不像这样工作,它将被视为2个参数:FUNCTION(ARGUMENT)。相反,如果ARGUMENT很复杂,你应该使用(FUNCTION ARGUMENT)(FUNCTION (ARGUMENT))

此外,您不应将函数的参数与函数分开:take (length ... LIST)。这被认为是单个参数(length ... LIST)。它们应与功能位于同一支架级别。

所以你的第一次重建呼叫看起来像:

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

可能表达的其余部分也有类似的问题

© www.soinside.com 2019 - 2024. All rights reserved.