Haskell Tree - поиск по дереву

Question

У меня возникли проблемы с моим назначением: я пытаюсь написать код, который составляет список всех значений узлов, которые я ему скажу (например, все узлы со значением 4 в аккуратный список).

я написал следующее:

findValue :: a -> (MyTree a) -> [a] 
findValue x Leaf = [] 
findValue x (Node a l r) 
    |a == x = x++(findValue x l)++(findValue x r) 
    |a /= x = (findValue x l)++(findValue x r) 

Я определил деревья следующим образом:

data MyTree a = Leaf | Node a (MyTree a) (MyTree a) 

Я получаю следующее сообщение об ошибке-сообщение:

Couldn't match expected type ‘[a]’ with actual type ‘a’ 
     ‘a’ is a rigid type variable bound by 
      the type signature for findValue :: a -> MyTree a -> [a] 
      at assignment.hs:10:14 
    Relevant bindings include 
     r :: MyTree a (bound at assignment.hs:12:25) 
     l :: MyTree a (bound at assignment.hs:12:23) 
     a :: a (bound at assignment.hs:12:21) 
     x :: a (bound at assignment.hs:12:11) 
     findValue :: a -> MyTree a -> [a] 
     (bound at assignment.hs:11:1) 
    In the first argument of ‘(++)’, namely ‘x’ 
    In the expression: x ++ (findValue x l) ++ (findValue x r) 

Я был бы очень рад если кто-то объяснил мне сообщение об ошибке. Заранее спасибо!

Answer 1

Тип (++): [a] -> [a] -> [a], но тип x: a. Таким образом, вы можете написать

x : (findValue x l) ++ (findValue x r) (который использует "против" оператор (:) :: a -> [a] -> [a]) или

[x] ++ (findValue x l) ++ (findValue x r) 

Вот как вы должны определить это самостоятельно:

Ошибка говорит Couldn't match exptected type '[a]' with actual type 'a' ... in the first argument of '(++)', namely 'x'

Этот означает, что аргумент x - (++) (в указанной строке) должен тип [a] (это ожидаемый type), но на самом деле есть тип a () type).

Тогда вы должны посмотреть тип подписи для (++), чтобы увидеть, что проблема может быть (например, с помощью hoogle, hayoo или ghci) В вашем случае, проблема заключалась в том, что типы первого и второго аргументов в (++) были не то же самое, но они должны быть.

Answer 2

Подумайте, что вы делаете. findValue имеет тип a -> MyTree a -> [a], что означает, что x имеет тип a.

Однако оператор (++) имеет тип [a] -> [a] -> [a], но вы пишете x ++ (findValue x l) ++ (findValue x r). Следовательно, это дает вам поговорку об ошибке:

Couldn't match expected type ‘[a]’ with actual type ‘a’ 
     ‘a’ is a rigid type variable bound by 
      the type signature for findValue :: a -> MyTree a -> [a] 
      at assignment.hs:10:14 
    Relevant bindings include 
     r :: MyTree a (bound at assignment.hs:12:25) 
     l :: MyTree a (bound at assignment.hs:12:23) 
     a :: a (bound at assignment.hs:12:21) 
     x :: a (bound at assignment.hs:12:11) 
     findValue :: a -> MyTree a -> [a] 
     (bound at assignment.hs:11:1) 
    In the first argument of ‘(++)’, namely ‘x’ 
    In the expression: x ++ (findValue x l) ++ (findValue x r) 

Сообщение об ошибке четко говорит, что Couldn't match expected type ‘[a]’ with actual type ‘a’. Далее сообщается, где проблема, In the first argument of ‘(++)’, namely ‘x’. Он даже говорит вам, где найти это выражение, In the expression: x ++ (findValue x l) ++ (findValue x r).

Сообщения об ошибках Haskell могут выглядеть очень страшно, но на самом деле они довольно информативны и понятны. Не допускайте, чтобы фразы типа ‘a’ is a rigid type variable bound by пугали вас.

Я понимаю, что легко отказаться, когда второе предложение, которое вы читаете, - это то, что вы не понимаете, и я понимаю, что проще задать вопрос об этом на SO. Сделайте себе одолжение и не делайте этого. Узнайте, как понимать сообщения об ошибках.

Дайте человеку рыбу, и он будет есть в течение одного дня. Научите человека ловить рыбу, и он будет есть всю свою жизнь.

---

Кстати, почему вам нужен findValue функцию типа a -> MyTree a -> [a]? Это имело бы больше смысла иметь:

hasValue :: a -> MyTree a -> Bool 
hasValue x Leaf   = False 
hasValue x (Node a l r) 
    | a == x   = True 
    | otherwise   = findValue x l || findValue x r 

numValue :: a -> MyTree a -> Int 
numValue x Leaf   = 0 
numValue x (Node a l r) 
    | a == x   = depth + 1 
    | otherwise   = depth 
    where depth = findValue x l + findValue x r 

Для меня это не имеет никакого смысла иметь findValue функцию, так как данный findValue x t результат:

1. либо пустой список или не- пустой список (False или True соответственно). Следовательно, hasValue.

2. Список только x значения повторяются, и в этом случае имеет значение только длина. Следовательно, numValue.

   findValue :: a -> MyTree a -> [a] 
   findValue x t = replicate (numValue x t) x