Haskell n-ary cây traversal

Question

Tôi khá mới với Haskell và tôi đang cố gắng để làm việc ra làm thế nào để đi qua một cây n-ary. Khi sản lượng tôi đang tìm cách để có được một danh sách các giá trị lá (như các chi nhánh không có giá trị), do đó cho testtree này sẽ là: 4,5

Định nghĩa của tôi cho đến nay là:

data Tree a = Leaf a | Branch [Tree a] deriving (Show) 

travTree     :: Tree a -> [a] 
travTree (Leaf x)   = [x] 
travTree (Branch (x:xs)) = travTree x : travTree xs 

testtree = Branch [(Leaf "4"), (Leaf "5")] 

Nhưng nó đưa ra lỗi:

Couldn't match expected type `Tree a' 
    against inferred type `[Tree a]' 
In the first argument of `travTree', namely `xs' 
In the second argument of `(:)', namely `travTree xs' 
In the expression: travTree x : travTree xs 

Tôi giả định đây là do xs là danh sách cây và mong đợi một cây kỳ dị. Có cách nào để làm việc này không? Tôi đã cố gắng chức năng bản đồ, dọc theo dòng:

travTree (Branch (x:xs)) = travTree x : map travTree xs 

Nhưng sau đó nó than phiền của:

Occurs check: cannot construct the infinite type: a = [a] 
When generalising the type(s) for `travTree' 

Tôi cũng đã cố gắng thay đổi chữ ký chức năng để:

travTree     :: Tree a -> [b] 

Lỗi này cung cấp cho:

Couldn't match expected type `a' against inferred type `[b]' 
    `a' is a rigid type variable bound by 
     the type signature for `travTree' at Main.hs:149:36 
In the first argument of `(:)', namely `travTree x' 
In the expression: travTree x : map travTree xs 
In the definition of `travTree': 
    travTree (Branch (x : xs)) = travTree x : map travTree xs 

Bất kỳ trợ giúp nào sẽ được đánh giá cao, vì vậy cảm ơn trước ..!

Answer 1

Di chuyển cây có nghĩa là duyệt qua tất cả các subtrees và làm phẳng các danh sách kết quả thành một.

này dịch để

travTree (Branch branches) = concat $ map travTree branches 

Lưu ý rằng thậm chí có những ký hiệu ngắn gọn hơn như branches >>= travTree hoặc concatMap travTree branches cho phía bên tay phải của định nghĩa này, nhưng tôi xem xét một ở trên là rõ ràng nhất.

Edit: pháp chuyển hướng phiên bản danh sách-hiểu vì lợi ích của sự hoàn chỉnh:

travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ] 

Answer 2

Bạn đang ở trên các đường đúng với map, nhưng sau khi đi qua mỗi cây con bạn muốn concat danh sách kết quả lại với nhau . Cũng không có điểm nào phá vỡ phần tử đầu tiên của danh sách với mẫu (x:xs) khi sử dụng map. Tôi muốn viết những dòng này như:

travTree (Branch xs) = concatMap travTree xs 

(Nhưng hãy cẩn thận, tôi đã không kiểm tra mà Tuy nhiên tôi thường thấy của tôi "loại vô hạn a = [a]" vấn đề là do một map nơi concatMap là cần thiết!.)

Answer 3

Khi tôi mới sử dụng Haskell, tôi đã gặp phải vấn đề tương tự. Cuối cùng tôi đã tìm ra cách để giải quyết vấn đề bằng cách làm chậm lại và nhìn vào các loại. (Quay lại khi tôi đã viết rất nhiều Đề án, tôi thay vì bị chậm lại và nhìn vào cặp đầu vào/đầu ra rất đơn giản. Tôi làm điều đó đôi khi trong Haskell, nhưng không phải cho đến khi tôi đã xem xét các loại.)

travTree     :: Tree a -> [a] 
travTree (Leaf x)   = [x] 
travTree (Branch (x:xs)) = travTree x : travTree xs 

Loại của bạn có vẻ đúng: Tree a -> [a] có vẻ như "tất cả lá" với tôi.

travTree (Leaf x) = [x] 

Trường hợp này chuyển đổi đúng Tree a thành [a].

travTree (Branch (x:xs)) = travTree x : travTree xs 

OK, đầu vào chắc chắn là Tree a. Nếu đầu ra là [a] và toán tử đầu tiên là (:) :: a -> [a] -> [a], thì chúng tôi cần travTree x :: a và travTree xs :: [a]. Điều này có hiệu quả không?

Vâng, không thành công vì hai lý do: thực tế, travTree x :: [a] và bạn không thể chống lại một danh sách vào một danh sách khác (bạn cần (++) :: [a] -> [a] -> [a] cho điều đó). Và bạn không thể vượt qua [Tree a] đến travTree :: Tree a -> [a] - bạn đang cung cấp cho nó danh sách cây khi dự kiến ​​một cây duy nhất.

Bạn có thể giải quyết vấn đề thứ hai bằng cách sử dụng map: map travTree xs. Điều này có loại [Tree a] -> [[a]]. May mắn thay, điều này bây giờ phù hợp với travTree x :, do đó

(travTree x : map travTree xs) :: [[a]] 

Bây giờ bạn chỉ có vấn đề mà bạn có [[a]] thay vì [a]. concat giải quyết vấn đề này bằng cách làm phẳng một lần, vì vậy

travTree (Branch (x:xs)) = concat (travTree x : map travTree xs) :: [a] 

mà phù hợp với mong đợi Tree a -> [a].

Các câu trả lời khác là đúng khi nói rằng phá hoại là vô nghĩa ở đây, nhưng tôi hy vọng rằng việc thấy các loại được viết ra giúp bạn hiểu cách bắt chước suy luận kiểu trong đầu của bạn. Bằng cách đó bạn có thể tìm ra những gì đang xảy ra với các vấn đề tương tự khác.