0

識別番号を保存するツリーを作成するという趣味のプロジェクトがあります。ノードに格納されている数字を使用しました。つまり、ノードは0 1 2 3 4 5 6 789になります。

ツリーを作成したら、ツリーからリストを作成します。しかし、目標を管理するためのアルゴリズムが見つかりませんでした。

私が欲しいもの：

      "recompose tree"  will return list of numbers. For below tree it should be 

            [ 2, 21, 243, 245, 246, 78, 789 ]  


                               Root 
                           /          \         
                        2*               7
                      /      \             \                  
                   1*         4              8*    
                            / \  \            \         
                           3*  5* 6*           9*

       my data type :  data ID x = ID ( ( x, Mark ), [ ID x ] ) 
                       data Mark = Marked | Unmarked

       EDIT:

       for convenience : * shows it is marked
                         I have stored digit as char, actually not 1, 
                            it is stored as'1'

どうすればそれができるかアドバイスはありますか？（アドバイスはアルゴリズムであることが好ましい）

4

2 に答える 2

3

どうですか

recompose :: Num a => ID a -> [a]
recompose = go 0
  where
    go acc (ID ((n, Marked), ids)) =
      let acc' = 10 * acc + n
      in  acc' : concatMap (go acc') ids
    go acc (ID ((n, Unmarked), ids)) =
      let acc' = 10 * acc + n
      in  concatMap (go acc') ids

？

つまり、ルートからノードへのパスの値を累積しながら、ツリーを走査します。すべてのノードで、パスの値に10を掛け、ノードの値をアキュムレータに追加することにより、アキュムレータを更新します。トラバーサルは、マークされたノードのすべてのアキュムレータ値のリストを生成します。したがって、マークされたノードでアキュムレータ値をリストに追加し、マークされていないノードについては、ノードの子について収集したリストを伝播するだけです。

ノードの子のリストをどのように計算しますか？go子のリストにマッピングすることにより、すべての子に対して走査関数（）を再帰的に呼び出します。これにより、単一のリストを取得するために連結するリストのリストが得られます。（またはconcatMap f xsです。）concat (map f xs))concat . map f

属性文法の用語では、アキュムレータは継承された属性として機能しますが、返されるリストは合成された属性です。

改良として、補助関数を導入することができますisMarked。

isMarked :: Mark -> Bool
isMarked Marked   = True
isMarked Unmarked = False

簡潔に書けるように

recompose :: Num a => ID a -> [a]
recompose = go 0
  where
    go acc (ID ((n, m), ids)) =
      let acc'   = 10 * acc + n
          prefix = if isMarked m then (acc' :) else id
      in  prefix (concatMap (go acc') ids)
于 2012-04-20T10:35:17.723 に答える
2

ところで：これはSQLでも実行できます：

DROP SCHEMA tmp CASCADE;

CREATE SCHEMA tmp ;
SET search_path='tmp';

CREATE TABLE the_tree
        ( id CHAR(1) NOT NULL PRIMARY KEY
        , parent_id CHAR(1) REFERENCES the_tree(id)
        );
INSERT INTO the_tree(id,parent_id) VALUES
 ( '@', NULL)
,( '2', '@')
,( '7', '@')
,( '1', '2')
,( '4', '2')
,( '3', '4')
,( '5', '4')
,( '6', '4')
,( '8', '7')
,( '9', '8')
        ;

WITH RECURSIVE sub AS (
        SELECT id, parent_id, ''::text AS path
        FROM the_tree t0
        WHERE id = '@'
        UNION
        SELECT t1.id, t1.parent_id, sub.path || t1.id::text
        FROM the_tree t1
        JOIN sub ON sub.id = t1.parent_id
        )
SELECT sub.id,sub.path
FROM sub
ORDER BY path
        ;

結果：（postgresql）

NOTICE:  drop cascades to table tmp.the_tree
DROP SCHEMA
CREATE SCHEMA
SET
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "the_tree_pkey" for table "the_tree"
CREATE TABLE
INSERT 0 10
 id | path 
----+------
 @  | 
 2  | 2
 1  | 21
 4  | 24
 3  | 243
 5  | 245
 6  | 246
 7  | 7
 8  | 78
 9  | 789
(10 rows)
于 2012-04-20T10:52:00.020 に答える