reconstruct the binary tree with two lists after preorder and inorder

Question

--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.

-- I haven't found the function "rank" online. My professor told us that the function "rank" can output the position of one element in a list.

The error occured in the following line where the function "rank" were used.

So I have two questions.

1. How ist the function "rank"?
2. Is the expression "reconstruct :: [Int]->IntTree" correct ? I am not sure.

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)) 

after correction

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"

the error

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]

Answer 1

The function `reconstruct' is applied to three arguments, but its type `[Int] -> [Int] -> IntTree' has only two

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

You apply the reconstruct functions to 3 arguments, as stated in the error message: take, (length (fst p) xs) and (fst p).

Similar error is with length application: you pass 2 arguments to it.

Maybe you meant to pass FUNCTION(ARGUMENT) as single argumetn to next function. It does not work like this, it would be considered as 2 arguments: FUNCTION and (ARGUMENT). Instead you should use (FUNCTION ARGUMENT), or (FUNCTION (ARGUMENT)) if the ARGUMENT is complex.

Also, you should not group arguments to functions separately from the function: take (length ... LIST). This is considered as single argument (length ... LIST). They should be on same bracket level with the function.

So your first reconstruct call would rather look like:

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

And probably the rest of the expression have similar issues

Answer 2

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"

This seemed to work on the single testcase I tried, and is pretty much what you intended to write (I think). It runs into issues if nodes can have left-descendants with equal contents to themselves (?). I think it might traverse l twice (due to length), you could solve this with a zipand some extra logic if desired.