無價值樹一 - 在Haskell

Question

>一所以我有一個樹定義爲

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

我知道我可以定義葉是葉一。但我真的只想讓我的節點具有價值。我的問題是，當我做了搜索我型

Tree a -> a 

的返回值函數由於葉子有沒有價值我很困惑怎麼說，如果你遇到一個葉無能爲力。我試過nil," ",' ',[]似乎沒有任何工作。

編輯代碼

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

所以我在這種情況下，解決辦法是使用Maybe和mapMaybe。簡單地說，你會改變treeValue到

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

然後，而不是使用map結合這一點，使用mapMaybe（從Data.Maybe），它會自動剝去了Just，而忽略它，如果它是Nothing。

mapMaybe treeValue xs 

瞧！

Maybe是說「有些事情可能沒有價值」，是剛剛定義這樣的Haskell的方式：

data Maybe a = Just a | Nothing 

它有可空類型的道德等價物。 Haskell只是讓你承認這樣一個事實，即你必須處理它爲「空」的情況。當你需要它們時，Data.Maybe有很多有用的功能，如mapMaybe可用。

Answer 2

在Haskell中，默認情況下類型沒有「空」或nil值。當你有Integer類型的東西，比如你總是有的實際數量和像nil，null或None從來沒有任何東西。

大多數情況下，這種行爲是好的。你永遠不能遇到空指針異常時，你不要指望他們，因爲你永遠不能擁有空當你不希望他們。但是，有時我們確實需要某種Nothing值;你的樹的功能是一個很好的例子：如果我們沒有發現在樹的結果，我們必須以表示不知。

最明顯的方法來添加一個「空」值這個樣子，只是把它包在一個類型：

data Nullable a = Null | NotNull a 

所以，如果你想要一個Integer這也可能是Null，你只需要使用一個Nullable Integer 。您可以輕鬆地自行添加此類型;沒有什麼特別的。

令人高興的是，Haskell的標準庫有類型這樣已經，只是用不同的名稱：

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

您：

data Maybe a = Nothing | Just a 

，你可以在你的樹的功能如下使用這種類型可以通過模式匹配使用包裝在Maybe中的值。所以，如果你有[Maybe a]列表，你想獲得一個[String]出來，你可以這樣做：

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

myList = map showMaybe listOfMaybes 

最後，還有一堆的Data.Maybe模塊中定義的有用的功能。例如，有mapMaybe它映射列表並拋出所有的Nothing值。例如，這可能是您想要用於_breadthFirst功能的。

Answer 3

在這種情況下，你可以簡單地使用，而不是map列表理解和擺脫treeValue：

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

這工作，因爲使用上的<-左側的模式列表中的理解跳過項目與模式不匹配。

Answer 4

此功能treeValue :: Tree a -> a不能爲總功能，因爲並非所有Tree a值實際上都包含a供您回報！ A Leaf類似於空列表[]，它仍然是[a]類型，但實際上並不包含a。

標準庫中的head函數類型[a] -> a，也不能工作，所有的時間：

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

您可以寫treeValue同樣的行爲：

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

但這實際上不會幫助你，因爲現在map treeValue xs會拋出一個錯誤，如果任何xs是Leaf值。

有經驗的Haskellers通常會盡量避免使用head，並且出於這個原因使用類似功能。當然，沒有辦法從任何給定的[a]或Tree a獲得a，但也許你不需要。在你的情況，你真的想從列表Tree得到列表a，你很高興爲Leaf到根本不算什麼有助於列表，而不是拋出一個錯誤。但treeValue :: Tree a -> a不幫你建立。這是錯誤函數來幫助你解決你的問題。

一個函數可以幫助你做任何你需要的將是Tree a -> Maybe a，正如其他一些答案中所解釋的那樣。這允許你後來決定如何處理「缺失」值。當你去使用Maybe a時，如果真的沒有其他的事情可以做，那麼你可以打error然後（或者使用fromJust這正好），或者你可以決定做什麼。但是treeValue聲稱能夠從任何Tree a返回a，然後當它不能否認任何呼叫者能夠決定如果沒有a時該做什麼的能力時調用error。