hoạt động gập haskell trên cây

Question

data Tree a = Tree a [Tree a] 

Lưu ý rằng chúng tôi không cho phép cây trống và lá là cây có danh sách phụ đề trống.

treeFold :: (a -> [b] -> b) -> Tree a -> b 
treeFold f (Tree x s) = f x (map (treeFold f) s) 

Với thông tin trên, tôi không hiểu tại sao cây chức năng gấp trả về kết quả một cách đệ quy bằng cách áp dụng các hoạt động gấp đến subtrees, sau đó áp dụng các chức năng để nhãn ở thư mục gốc và kết quả trở về từ các subtrees.

Tôi cũng không nhận được hàm cây gấp chỉ nhận một đối số thay vì 2, khi nó được chuyển làm đối số cho hàm bản đồ và nó vẫn biên dịch và chạy đúng. Ví dụ: chức năng kích thước cây bên dưới, đếm các nút của cây.

treeSize :: Tree a -> Int 
treeSize = treeFold (\x ys -> 1 + sum ys) 

Vì vậy, chạy TreeSize cây nơi tree = Tree 4 [Tree 1 [Tree 2 [], Tree 3 []]] cho kích thước của cây như 4.

Trong chức năng kích thước cây ở trên, chức năng cây lần cũng được thông qua một đối số thay vì hai. Ngoài ra, x được chuyển đến chức năng gấp cây không được sử dụng ở bất cứ đâu, vậy tại sao bạn cần nó ở đó. Loại bỏ nó làm cho chương trình không biên dịch và nó cung cấp thông báo lỗi sau.

Couldn't match type `a' with `[[Int] -> Int]' 
     `a' is a rigid type variable bound by 
      the type signature for treeSize :: Tree a -> Int 
      at treeFold.hs:15:1 
    In the first argument of `sum', namely `ys' 
    In the second argument of `(+)', namely `sum ys' 
    In the expression: 1 + sum ys 

Mọi trợ giúp sẽ được đánh giá cao.

Answer 1

Câu hỏi đầu tiên hơi phức tạp, vì đó là điều có đệ quy ... Như giáo viên nói: "Để hiểu đệ quy, bạn phải học, cách đệ quy hoạt động". :-P Một lời khuyên nhỏ: Hãy thử đi qua các ứng dụng của treeFold với một cây duy nhất hoặc một cây với một cây bên trong và đánh giá nó bằng cách của riêng bạn (trên giấy hoặc như vậy). Tôi nghĩ, sau đó bạn có thể có được một cảm giác về những gì đang xảy ra ... (tất nhiên sử dụng một chức năng đơn giản như một đối số cho treeFold; như thế, mà treeSize của bạn sử dụng).

treeFold được chỉ có một lý lẽ trong cơ thể bản đồ, vì map đòi hỏi một chức năng từ a->b, và treeFold có loại (a -> [b] -> b) -> Tree a -> b., vì vậy nếu bạn sẽ vượt qua nó 2 đối số, bạn sẽ vượt qua để map chỉ một giá trị, gây ra một thất bại. (Ví dụ dễ hiểu: (+) yêu cầu hai đối số.Nếu bạn viết map (+1) [1,2,3] bạn sẽ nhận được [2,3,4] , vì (+1) được áp dụng cho từng phần tử trong danh sách (và (+1) rõ ràng cần thêm một đối số, bạn treeFold f trên)

dụ bạn TreeSize:. nó không đúng, khi bạn nói, mà nó chỉ được một đối số bạn có thể viết

treeSize t = treeFold (\x ys -> 1 + sum ys) t 

thay vì định nghĩa của bạn ở trên x thì không. được sử dụng bởi vì để đếm nó là useless.But, treeFoldn eeds để có một hàm, có hai đối số, vì vậy bạn cho nó x. Đó là lý do duy nhất. Bạn có thể vượt qua bất kỳ giá trị nào khác.

Answer 2

Arguments chưa sử dụng

Thứ nhất, theo cách bạn đánh dấu một cách rõ ràng một biến như là chưa sử dụng là để thay thế các biến với _. Vì vậy, bạn thực sự muốn:

treeFold (\_ ys -> 1 + sum ys) 

Bạn có một lỗi biên dịch vì bạn đã viết:

treeFold (\ys -> 1 + sum ys) 

... mà không phải là điều tương tự.

Folds

Thứ hai, tôi sẽ bàn đánh giá treeSize trên một cây dụ, do đó bạn có thể thấy rằng không có ma thuật xảy ra:

treeSize (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Inline definition of 'treeSize' 
= treeFold (\_ ys -> 1 + sum ys) (Tree 1 [Tree 2 [], Tree 3 []]) 

-- Evaluate treeFold 
= (\_ ys -> 1 + sum ys) 1 (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the anonymous function 
= 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) [Tree 2 [], Tree 3 []]) 

-- Apply the 'map' function 
= 1 + sum [ treeFold (\_ ys -> 1 + sum ys) (Tree 2 []) 
      , treeFold (\_ ys -> 1 + sum ys) (Tree 3 []) 
      ] 

-- Apply both 'treeFold' functions 
= 1 + sum [ (\_ ys -> 1 + sum ys) 2 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , (\_ ys -> 1 + sum ys) 3 (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- Apply the anonymous functions 
= 1 + sum [ 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      , 1 + sum (map (treeFold (\_ ys -> 1 + sum ys)) []) 
      ] 

-- map f [] = [] 
= 1 + sum [ 1 + sum [] 
      , 1 + sum [] 
      ] 

-- sum [] = 0 
= 1 + sum [1 + 0, 1 + 0] 
= 1 + sum [1, 1] 

-- Apply 'sum' 
= 1 + 2 
= 3 

Tuy nhiên, có một cách dễ dàng để nhớ cách treeFold công trinh. Tất cả nó làm nó thay thế mỗi constructor Tree với chức năng mà bạn cung cấp nó.

Vì vậy, nếu bạn có:

Tree 1 [Tree 2 [Tree 3 [], Tree 4[]], Tree 5 [Tree 6 [], Tree 7 []]] 

... và bạn áp dụng treeFold f vào đó, nó sẽ đánh giá để:

f 1 [f 2 [f 3 [], f 4 []], f 5 [f 6 [], f 7 []]] 

treeSum chỉ là trường hợp đặc biệt nơi f = (\_ ys -> 1 + sum ys):

1 + sum [1 + sum [1 + sum [], 1 + sum []], 1 + sum [1 + sum [], 1 + sum []]] 

= 7 

Currying

Điểm cuối cùng là cách thức hoạt động của curry trong Haskell. Khi bạn định nghĩa một hàm như:

foo x y = x + y 

... trình biên dịch thực sự desugars đó để hai hàm lồng nhau:

foo = \x -> (\y -> x + y) 

Đây là lý do tại sao bạn có thể áp dụng một phần chức năng để chỉ một đối số trong Haskell. Khi bạn viết foo 1, nó chuyển thành:

foo 1 

= (\x -> (\y -> x + y)) 1 

= \y -> 1 + y 

Nói cách khác, hàm này trả về hàm mới của một đối số.

Trong Haskell, tất cả các hàm đều lấy chính xác một đối số và chúng tôi mô phỏng các hàm của nhiều đối số bằng cách trả về các hàm mới. Kỹ thuật này được gọi là "currying".

Nếu bạn thích cách tiếp cận đa đối số của nhiều ngôn ngữ chủ đạo truyền thống, bạn có thể mô phỏng nó bằng có chức năng chấp nhận một đối số tuple:

f (x, y) = x + y 

Tuy nhiên, đó không phải là thực sự thành ngữ Haskell, và nó đã giành' t cung cấp cho bạn bất kỳ loại cải thiện hiệu suất nào.