Haskell Bản đồ cho Trees

Question

cây của tôi được xác định bởi

data Tree a = Leaf a | Node (Tree a) (Tree a) 
     deriving (Show) 

Tôi cũng tuyên bố một cây thử nghiệm.

myTree = Node (Node (Leaf 1) (Leaf 2)) (Leaf 3) 

Điều tôi muốn làm là tạo một hàm maptree f sẽ hoạt động trên Leaf. Để cụ thể hơn, f x = x +1,

sau đó maptree f myTree sẽ trở lại

Node (Node (Leaf 2) (Leaf 3)) (Leaf 4) 

Giải pháp của tôi là

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr) = Node (maptree xl) (maptree xr) 

nhưng nó sẽ trở lại các lỗi sau

Couldn't match expected type `Tree a' 
     against inferred type `Tree t -> Tree t' 
Probable cause: `maptree' is applied to too few arguments 
In the first argument of `Node', namely `(maptree xl)' 
In the expression: Node (maptree xl) (maptree xr) 

Không, mô-đun được nạp : không ai.

Tuy nhiên, nếu tôi làm

maptree (Leaf a)= Leaf (a + 1) 
maptree (Node xl xr) = Node (maptree xl) (maptree xr) 

nó làm việc ra.

Tôi không thể thấy sự khác biệt giữa hàm đầu tiên và hàm thứ hai. Làm cách nào để tôi gặp lỗi? Cảm ơn.

Answer 1

Một cách ngu ngốc để không quên để vượt qua cùng chức năng như bạn recurse sâu hơn (đối với loại này chức năng bậc cao) là sử dụng một helper:

maptree f (Leaf a)  = Leaf (f a) 
maptree f (Node xl xr) = Node (go xl) (go xr) 
    where go = maptree f 

Hoặc cách khác (và có lẽ phổ biến hơn):

maptree f tree = go tree      -- or eta reduce: maptree f = go 
    where go (Leaf a)  = Leaf (f a) 
      go (Node xl xr) = Node (go xl) (go xr) 

trong ví dụ đầu tiên, tôi sử dụng go loại như một macro cho maptree f. Trong ví dụ thứ hai, tôi tận dụng thực tế là đầu vào maptree của f nằm trong phạm vi bên trong hàm go vì go được khai báo trong mệnh đề where của maptree.

Answer 2

Bạn đang thiếu các chức năng trên các cuộc gọi maptree đệ quy:

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr) = Node (maptree xl) (maptree xr) 

nên

maptree f (Leaf a)= Leaf (f a) 
maptree f (Node xl xr) = Node (maptree f xl) (maptree f xr) 

Answer 3

Các thông báo lỗi về cơ bản sẽ cho bạn biết những gì là sai: bạn không đi qua maptree đủ lý lẽ. Định nghĩa maptree f (Node xl xr) nói rằng maptree lấy hai đối số, một hàm và một cây. Nhưng khi bạn gọi nó là maptree xl, bạn chỉ cho nó một đối số (một cái cây).

Trong phiên bản thứ hai, bạn đã xác định maptree để chỉ lấy một đối số (một cây), đó là lý do tại sao nó không tạo ra lỗi đó.

Bạn có thể khắc phục sự cố của mình bằng cách gọi số maptree f xl thay vì maptree xl.

Answer 4

Lưu ý rằng đây rõ ràng là fmap của phiên bản Functor cho loại Tree của bạn. Do đó, bạn có thể sử dụng phần mở rộng DeriveFunctor để GHC tạo nó cho bạn.

{-# LANGUAGE DeriveFunctor #-} 
data Tree a = Leaf a | Node (Tree a) (Tree a) 
    deriving (Functor, Show) 

Hãy dùng thử.

*Main> fmap (+1) (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3)) 
Node (Node (Leaf 2) (Leaf 3)) (Leaf 4)