如何在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的树上走？

回答

相关问题