3

バラの木の特定の要素を検索し、その場所を返す関数を作成しようとしています。

私がすでに得たものをあなたに示すとき、それはより明確かもしれません：

定義のあるツリーが与えられた場合：

データツリーテキスト=ノード値[ツリー値]

例えば：

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

関数検索を探しています：

search :: String -> Tree String -> [Integer]

検索1123テスト->[1,2,3]を返す必要があります
-1=11の最初のサブツリー->11= 112の2番目のサブツリー、112=1123の3番目のサブツリー

ツリーを反復処理する方法を知っています。

display (Node v xs) = v ++ concatMap display xs

しかし、サブツリー配列のすべての要素に整数値を割り当て、さらにツリーの上部から下部に再帰的に渡す方法がわかりません。解決策を探す場所/方法を教えてもらえますか？私はHaskellにとても慣れていません。

4

1 に答える 1

4

最も簡単な方法は、最初に関数が目的のデータを含むノードへのすべてのパスのリストを返すようにすることです（ツリーには最大で1つしか存在しないはずですが、それは問題ではありません）。これらの最初：

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"

Daniel Wagnerの疑いが正しく、ツリーが試行された場合、より効率的に検索できますが、原則は同じです。ただし、目的のデータを持つノードが1つあるか、まったくないことがわかったため、結果はより適切になります。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
于 2012-06-02T18:26:44.943 に答える