--给出两个列表,一个按预序排序,另一个按无序排序。这两个列表来自同一个二叉树。通过这两个列表,二叉树被重建。
-- 我还没有在网上找到"排名"功能。我的教授告诉我们,函数"rank"可以输出列表中一个元素的位置。
错误发生在使用函数"rank"的下一行中。
所以我有两个问题。
- 函数"排名"如何?
- 表达式"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: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]
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
和一些额外的逻辑来解决这个问题。
函数"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)
.相反,你应该使用 (FUNCTION ARGUMENT)
,或者如果参数很复杂,(FUNCTION (ARGUMENT))
。
此外,您不应将函数的参数与函数分开分组:take (length ... LIST)
。这被视为单参数(length ... LIST)
。它们应与函数位于同一括号级别。
因此,您的第一个重建调用宁愿看起来像:
(reconstruct (take (length (fst p)) xs) (fst p))
可能表达式的其余部分也有类似的问题