问

如何在Haskell Data.Tree中查找节点的路径

嗳沫沫情深发布于 2023-01-30 20:23

tree

import

case

rsa

给定Haskell中的树(由a表示Data.Tree),我如何找到节点的路径？

例如

import Data.Tree

tree = Node 1 [Node 2 [Node 3 []], Node 4 []]



形成一个看起来像的树:

1
|
+- 2
|  |
|  `- 3
|
`- 4


我怎么能做一个pathToNode这样的功能:

pathToNode 0 tree => []
pathToNode 1 tree => [1]
pathToNode 2 tree => [1, 2]
pathToNode 3 tree => [1, 2, 3]
pathToNode 4 tree => [1, 4]


在我的特定情况下,任何给定的值只会在树中出现一次,因此可以接受返回值的路径的解决方案.

到目前为止,我最好的答案是:

pathToNode :: (Eq a) => a -> Tree a -> [a]
pathToNode x (Node y ys) | x == y    = [x]
                         | otherwise = case concatMap (pathToNode x) ys of
                                         [] -> []
                                         path -> y:path


有没有更简洁的写作方式？是否有可能利用Data.Foldable或Data.Traversable避免编写自己的遍历逻辑？



        
        2 个回答
        
                        
                存在称为变形的折叠概念的概括.与折叠允许您"消耗"列表而没有显式递归的方式相同,使用catamorphism可以"消耗"一个树或其他数据类型,而无需显式递归,并以自下而上的方式从叶子开始.与常规折叠不同,它将了解树的结构.

该cata功能可以在包的模块Data.Functor.Foldable(不是Data.Foldable!)中找到recursion-schemes.遗憾的是,它无法正常工作Data.Tree,您必须以间接的两步方式定义等效的数据类型:

{-# LANGUAGE DeriveFunctor #-}

import Data.Functor.Foldable

data Node a b = Node a [b] deriving (Functor,Eq)

type Tree a = Fix (Node a)

tree :: Tree Int
tree = Fix (Node 1 [ Fix ( Node 2 [ Fix (Node 3 []) ]), 
                     Fix ( Node 4 [] ) ])


使用cata,我们可以构建树中所有值的所有路径的列表.注意缺少显式递归:

paths :: Tree a -> [(a,[a])]
paths = cata algebra  
    where
    algebra :: Node a [(a,[a])] -> [(a,[a])]
    algebra (Node a as) = (a,[a]) : map (\(i,is)->(i,a:is)) (concat as) 


从该函数中,我们可以定义pathToNode:

pathToNode :: (Eq a) => a -> Tree a -> [a]
pathToNode a = snd . head . filter ((==a).fst) . paths 


这个解决方案并不是我更害怕的,但是catamorphims是一个有用的工具.

        
                
                    2023-01-30 20:26  回答
                       工程技术公司团委
                
            
                        
                这里不能使用默认值Traversable和Foldable实例,因为它们没有提供足够的上下文信息来维护路径(例如,当在Statemonad中遍历时).它们都按某种顺序访问树的每个元素,因此您无法知道某些先前访问过的值是否属于当前节点的父节点或兄弟节点.

我认为以下功能足够简洁:

pathsToNode :: Eq a => a -> Tree a -> [[a]]
pathsToNode x (Node y ns) = [[x] | x == y] ++ map (y:) (pathsToNode x =<< ns)


它列出了所有副本的路径x,但如果这是您想要的,您可以随时懒洋洋地抓住第一个找到的路径.

        
                
                    2023-01-30 20:28  回答
                       当个谎言家很不错非
                
            
                    
    
    
    
        撰写答案
        
            
                
                    回答问题...



    
    
        今天，你开发时遇到什么问题呢？
        立即提问
    

    
        热门标签