在Haskell搜索玫瑰树 [英] Searching rose tree in Haskell

问题描述

我试图编写一个函数来搜索玫瑰树中的给定元素并返回它的位置。

当我向你展示我已经得到的东西时，它可能会更清楚：给定一棵具有定义的树：

数据树文本=节点值
[树值]

例如：

  test =节点1[
节点11[
节点111[]，
节点112[
节点1121[]，节点1122[]，节点1123[] 
] 
]，
节点12 [] 
] 
 
 
 1 
 11 12 
 111 112 
 1121 1122 1123 
  
 
 
 
我正在寻找一个函数搜索： 
 
 
  search :: String  - >树字符串 - > [Integer] 
  
搜索1123 test  - >应该返回[1,2,3] 
 
  -  1 = 11的第一个子树 - > 11 = 112的第二个子树，112 = 1123的第三个子树
 
 
我知道如何遍历树， p> 
 
 
  display（Node v xs）= v ++ concatMap display xs 
  
但我不知道如何将整数值分配给子树数组的每个元素，并且还从树的上部到下部递归地传递它。 
您可以指导我在哪里/如何寻找解决方案？我对Haskell很新。
解决方案
最简单的方法是让函数返回所有路径的列表然后使用第一个节点：$ b​​ 
 $ b（需要的数据最多只能有一个在树中，我想，但这并不重要）。 
  searchList ::（Eq a）=> a  - >树a  - > [[Integer]] 
 searchList val（Node dat subs）
 | val == dat = [[]]  - 空路径
 |否则= concat [map（c :)（searchList val t）| （c，t）<  -  zip [1 ..] subs] 
 
 search :: Eq a => a  - >树a  - > [整数] 
搜索值val t = case $ search $ $ b $（p：_） - > p 
 _  - >如果丹尼尔瓦格纳的怀疑是正确的，并且你的树正在尝试，你可以搜索更有效率，但是原理保持不变，但是，因为我们现在知道我们有一个节点具有所需的数据或没有，所以结果更合适一个也许[Integer] ：
 
 
  import Data.List（isPrefixOf）
 import Control.Monad  - 对于Maybe的MonadPlus实例
 
 searchTrie :: String  - >树字符串 - >也许[Integer] 
 searchTrie目标（Node val subs）
 | val == target =只是[] 
 | （'c，t）：_） - > val'isPrefixOf` target = case dropWhile small（zip [1 ..] subs）of 
 fmap（c :) $ searchTrie target t 
 _  - >没有
 |否则= Nothing 
其中
越小（_，节点v_）= v < （长度v）目标
  
 
I'm trying to write a function searching for a given element in a rose tree and returning it's location. 

It may be clearer when I show you what I already got: 

Given a tree with a definition: 

data Tree text = Node value
                       [Tree value]

for example: 
test = Node "1" [
          Node "11" [
               Node "111" [], 
               Node "112" [
                  Node "1121" [], Node "1122" [], Node "1123" []
               ]
          ], 
          Node "12" []
      ]


            1
      11         12
111      112    
     1121 1122 1123   
I'm looking for a function search: 
search :: String -> Tree String -> [Integer]
search 1123 test -> should return [1,2,3]

- first subtree of 1=11 -> 2nd subtree of 11=112, 3rd subtree of 112=1123

I know how to iterate through tree, 
display (Node v xs) = v ++ concatMap display xs
But have no idea how can I assign integer value to every element of subtrees array and  additionally pass it recursively from upper to lower parts of the tree. 
Can you guys direct me where/how to look for a solution? I'm very new to Haskell.. 
解决方案
The easiest way is to let the function return the list of all paths to a node with the desired data (there should only ever be at most one in the tree, I suppose, but that doesn't matter) first, and then use the first of these:
searchList :: (Eq a) => a -> Tree a -> [[Integer]]
searchList val (Node dat subs)
    | val == dat = [[]]  -- empty path
    | otherwise  = concat [map (c:) (searchList val t) | (c,t) <- zip [1 .. ] subs]

search :: Eq a => a -> Tree a -> [Integer]
search val t = case searchList val t of
                 (p:_) -> p
                 _ -> error "Value not found"
If Daniel Wagner's suspicion is correct and your trees are tries, you can search more efficiently, but the principle remains the same, however, since we now know that we either have one node with the desired data or none, the result is more appropriately a Maybe [Integer]:
import Data.List (isPrefixOf)
import Control.Monad -- for the MonadPlus instance of Maybe

searchTrie :: String -> Tree String -> Maybe [Integer]
searchTrie target (Node val subs)
    | val == target = Just []
    | val `isPrefixOf` target = case dropWhile smaller (zip [1 .. ] subs) of
                                  ((c,t):_) -> fmap (c:) $ searchTrie target t
                                  _ -> Nothing
    | otherwise = Nothing
      where
        smaller (_,Node v _) = v < take (length v) target


                        
这篇关于在Haskell搜索玫瑰树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！