如何在haskell的樹上走？

也許問題不是相適應的話題我要去接近如何在haskell的樹上走？

但我會盡力解釋盡我所能：

我有了這種結構的家譜：

data GT = Person Name Father Mother 
     | unknown 
    type Father = GT 
    type Mother = GT 
    type Name = String

我需要找出一個給定名稱的祖父：

祖父::名稱 - > GT - > [名]

這是最好的，我可以這樣做：

grandfathers :: Name -> GT -> [Name] 
grandfathers s (Person x f m) = if (searchgrandson s f 0) then [x] else (grandfathers s f) 
        where 
         searchgrandson s unknown k = False 
         searchgrandson s (Person x f m) k = if s==x && k<2 then True 
                     else searchgrandson s f (k+1)

當然，對於這棵樹它的作品，因爲我的代碼去所有的方式，通過左側，忽略了母親身邊，並只給爺爺

，而不是奶奶對嗎？

$祖父「孫子」（人「爺爺」（人的「兒子」（人「孫子」未知的未知）未知）未知）

[ 「爺爺」]

編輯：

avos_ :: Nome -> AG -> Int 
avos_ s Desconhecida = 0 
avos_ s [email protected](Pessoa x p m) = encontraneto s l 0 
         where 
         encontraneto s Desconhecida k = 0 
         encontraneto s (Pessoa x p m) k = if s==x then k 
                    else encontraneto s p (k+1) + encontraneto s m (k+1)

這給：

繼dfeuer意見後我是孫子所在的樹的深處，尋找雙方。之後這將是簡單的...

謝謝！

來源

2015-02-08 skills

這似乎有點不清楚。你是否想要遍歷整棵樹來尋找某人的名字，然後你可以找到他們的祖父？ – dfeuer 2015-02-08 00:41:07

我需要找到一個給定名字的祖父，現在，我想我可以找到一個祖父。我知道祖父總是在2級以上，這就是爲什麼我用Int 0來搜索那個級別的原因。 – skills 2015-02-08 00:45:37

我強烈建議您編寫兩個完全獨立的函數：一個用於查找樹中對應於特定名稱的節點，另一個用於查找某個節點的祖先。然後把他們兩個放在一起，找到某個名字的人的祖父。 – dfeuer 2015-02-08 00:47:47

解決此問題的一個好方法是將其分解爲兩個函數。其中一個函數將搜索樹中的零個或多個匹配名稱並返回零或多個樹，從匹配發生的地方開始;每棵樹的根將是與名稱匹配的人。另一個函數將簡單地取一棵樹並返回對應於樹根處的人的祖父母的零個，一個，兩個，三個或四個名稱。

類型的第一功能的非常簡單：

searchPerson :: Name -> GT -> [GT]

類型第二功能的也很簡單現在

getGrandparents :: GT -> [Name]

，由於第一函數返回的GT的列表，而不是一個單一的GT，第二個函數應該映射到第一個函數的結果上（或者說，另一種方式，解除對GT列表的操作）：

map getGrandparents (searchPerson x myGenTree)

編寫第二函數（getGrandParents）是平凡的，可與模式匹配來實現，解構GT類型多達嵌套的第二級，但你可能想保存自己的一些打字，並創建一個輔助功能對每位家長進行操作並歸還父母。

第一個函數（searchPerson）也是微不足道的，可以用幾種方法完成。一種方法是簡單地使用遞歸查找名稱上的匹配並返回所有匹配的子樹列表。另一種選擇是簡單地從任何可能的偏移量開始返回該樹中每個可能子樹的列表，並使用過濾器來僅保留那些根目錄匹配的子樹。第二種選擇更「健康」，相當於解決列表中的類似問題（返回所有子列表的函數是尾巴），因此可能會吸引更多人。你可能會認爲第二種方法是浪費的，但是Haskell的不變性和懶惰也會使它非常高效。

我很快將代碼放在我的fpcomplete帳戶中，如果你問我會很樂意在下面的評論中發佈URL，但我不想破壞自己提出解決方案的樂趣。

來源

2015-02-08 14:11:14 fgv

如何在haskell的樹上走？

回答

相關問題