Nil Giá trị Tree a -> một trong Haskell

Question

Vì vậy, tôi có một cây định nghĩa là

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

Tôi biết tôi có thể xác định lá là lá a. Nhưng tôi thực sự chỉ muốn các nút của tôi có giá trị. Vấn đề của tôi là khi tôi thực hiện tìm kiếm, tôi có chức năng trả về giá trị của loại

Tree a -> a 

Vì lá không có giá trị Tôi nhầm lẫn khi nói rằng bạn gặp phải một chiếc lá không làm gì cả. Tôi đã thử nil, " ", ' ', [] không có gì có vẻ hoạt động.

Sửa Mã

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


breadthFirst :: Tree a -> [a] 
breadthFirst x = _breadthFirst [x] 

_breadthFirst :: [Tree a] -> [a] 
_breadthFirst [] = [] 
_breadthFirst xs = map treeValue xs ++ 
       _breadthFirst (concat (map immediateChildren xs)) 

immediateChildren      :: Tree a -> [Tree a] 
immediateChildren (Leaf)    = [] 
immediateChildren (Node n left right) = [left, right] 

treeValue       :: Tree a -> a 
treeValue (Leaf)    = //this is where i need nil 
treeValue (Node n left right) = n 

test = breadthFirst (Node 1 (Node 2 (Node 4 Leaf Leaf) Leaf) (Node 3 Leaf (Node 5 Leaf Leaf))) 

main = 
    do putStrLn $ show $ test 

Answer 1

Vì vậy, giải pháp của tôi trong trường hợp này sẽ được sử dụng Maybe và mapMaybe. Nói một cách đơn giản, bạn muốn thay đổi treeValue để

treeValue       :: Tree a -> Maybe a 
treeValue (Leaf)    = Nothing 
treeValue (Node n left right) = Just n 

Sau đó, thay vì sử dụng map kết hợp này, sử dụng mapMaybe (từ Data.Maybe) mà sẽ tự động lột bỏ sự Just và bỏ qua nó nếu nó Nothing.

mapMaybe treeValue xs 

Thì đấy!

Maybe là cách Haskell nói "Một cái gì đó có thể không có một giá trị" và được chỉ định nghĩa như thế này:

data Maybe a = Just a | Nothing 

Nó tương đương với đạo đức của việc có một loại Nullable. Haskell chỉ làm cho bạn thừa nhận thực tế rằng bạn sẽ phải xử lý các trường hợp mà nó là "null". Khi bạn cần chúng, Data.Maybe có rất nhiều chức năng hữu ích, như mapMaybe khả dụng.

Answer 2

Trong Haskell, các loại không có giá trị "trống" hoặc nil theo mặc định. Ví dụ: khi bạn có thứ gì đó thuộc loại Integer, bạn luôn là có số thực và không bao giờ giống như số nil, null hoặc None.

Hầu hết thời gian, hành vi này là tốt. Bạn không bao giờ có thể chạy vào các ngoại lệ con trỏ null khi bạn không mong đợi chúng, bởi vì bạn không bao giờ có thể có nulls khi bạn không mong đợi chúng. Tuy nhiên, đôi khi chúng ta thực sự cần có giá trị Nothing của một số loại; chức năng cây của bạn là một ví dụ hoàn hảo: nếu chúng ta không tìm thấy kết quả trong cây, chúng ta phải biểu thị bằng cách nào đó.

Cách rõ ràng nhất để thêm một giá trị "null" như thế này là chỉ cần bọc nó trong một kiểu:

data Nullable a = Null | NotNull a 

Vì vậy, nếu bạn muốn một Integer mà cũng có thể là Null, bạn chỉ cần sử dụng một Nullable Integer . Bạn có thể dễ dàng tự thêm loại này; không có gì đặc biệt về nó.

Happily, các thư viện chuẩn Haskell có một kiểu như thế này rồi, chỉ với một cái tên khác:

data Maybe a = Nothing | Just a 

bạn có thể sử dụng loại này trong chức năng cây của bạn như sau:

treeValue :: Tree a -> Maybe a 
treeValue (Node value _ _) = Just value 
treeValue Leaf    = Nothing 

Bạn có thể sử dụng giá trị được bao bọc trong một mẫu Maybe theo mẫu. Vì vậy, nếu bạn có một danh sách các [Maybe a] và bạn muốn có được một ra [String], bạn có thể làm điều này:

showMaybe (Just a) = show a 
showMaybe Nothing = "" 

myList = map showMaybe listOfMaybes 

Cuối cùng, có một loạt các chức năng hữu ích được định nghĩa trong module Data.Maybe. Ví dụ: có mapMaybe ánh xạ danh sách và ném ra tất cả các giá trị Nothing. Đây có lẽ là những gì bạn sẽ muốn sử dụng cho hàm _breadthFirst của bạn, ví dụ.

Answer 3

Trong trường hợp này, bạn chỉ có thể sử dụng danh sách hiểu thay vì map và thoát khỏi treeValue:

_breadthFirst xs = [n | Node n _ _ <- xs] ++ ... 

này hoạt động bởi vì sử dụng một mô hình ở phía bên tay trái của <- trong một sự hiểu biết danh sách bỏ qua mục không khớp với mẫu.

Answer 4

Chức năng này treeValue :: Tree a -> a không thể là hàm tổng, vì không phải tất cả các giá trị Tree a thực sự chứa a để bạn quay lại! A Leaf tương tự với danh sách trống [], vẫn thuộc loại [a] nhưng không thực sự chứa a.

Các head chức năng từ thư viện chuẩn có loại [a] -> a, và nó cũng không thể làm việc tất cả thời gian:

*Main> head [] 
*** Exception: Prelude.head: empty list 

Bạn thể viết treeValue cư xử tương tự:

treeValue :: Tree a -> a 
treeValue Leaf = error "empty tree" 
treeValue (Node n _ _) = n 

Nhưng điều này sẽ không thực sự giúp bạn, bởi vì bây giờ map treeValue xs sẽ ném một lỗi nếu bất kỳ giá trị xs là Leaf .

Người bán hàng có kinh nghiệm thường cố gắng tránh sử dụng head và các chức năng giống như vậy vì lý do này. Chắc chắn, không có cách nào để nhận được số a từ bất kỳ [a] hoặc Tree a nhất định nào, nhưng có thể bạn không cần. Trong trường hợp của bạn, bạn thực sự đang cố gắng để có được một danh sách của a từ một danh sách của Tree và bạn đang hạnh phúc cho Leaf chỉ đơn giản là không đóng góp gì vào danh sách thay vì ném lỗi. Nhưng treeValue :: Tree a -> a không giúp bạn xây dựng điều đó. Đó là chức năng sai để giúp bạn giải quyết vấn đề của mình.

Một chức năng giúp bạn làm bất cứ điều gì bạn cần là Tree a -> Maybe a, như được giải thích rất rõ trong một số câu trả lời khác. Điều đó cho phép bạn sau đó quyết định việc cần làm về giá trị "thiếu".Khi bạn sử dụng Maybe a, nếu không có gì khác để thực hiện, bạn có thể gọi error rồi (hoặc sử dụng fromJust làm chính xác điều đó) hoặc bạn có thể quyết định những việc cần làm khác. Nhưng treeValue tuyên bố có thể trả lại a từ bất kỳ Tree a và sau đó gọi error khi không thể từ chối bất kỳ người gọi nào có khả năng quyết định việc cần làm nếu không có a.