各ノードにアクセス

Question

私は、識別番号を格納するツリーを作成することに関するホビープロジェクトを持っています。私はノードに格納されている数字を使用していました。つまりノードは0です。1 2 3 4 5 6 7 8 9

ツリーを作成した後、ツリーから作成する必要があります。しかし、私は自分の目標を管理するためのアルゴリズムを見つけることができませんでした。私が欲しいもの

：

 "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' 

はあなたが私はそれを行うことができますどのようにアドバイスはありますか？

Answer 1

何

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 

について（アドバイスは、アルゴリズムであることをprefferredされますか）？

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

ノードの子のリストを計算するにはどうすればよいですか？私たちは再帰的に、子のリストの上にそれをマッピングすることによってすべての子にトラバーサル関数（go）を呼び出します。これにより、単一のリストを得るために連結したリストのリストが得られます。 （concatMap f xsだけconcat (map f xs))又はconcat . map fである。）

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

我々は簡潔ところで

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) 

Answer 2

を書くことができるように、我々は

、

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

を補助機能 isMarkedを導入することができます。これも、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)