ハスケル：ツリーの子を再帰的に逆にするには

Question

私はhaskellでツリーの子を逆転しようとしています。私は、これは100％に動作するかどうかさえわからない

rev :: Tree v e -> Tree v e 
rev (Node v []) = Node v [] 
rev (Node v xs) = 
    let xs' = (rev'(snd (unzip xs))) 
    in Node v (zip (fst (unzip xs)) (map rev xs')) 


rev' :: [Tree v e] -> [Tree v e] 
rev' [] = [] 
rev' (x:xs) = (rev' xs) ++ [x] 

：私はこの2つの機能でそれを行う現時点で

data Tree v e = Node v [(e,Tree v e)] 

：ツリーは次のようになります。 1つの関数で再帰的に行う方法はありますか？自分の道が非効率的だと感じる。

revRec :: Tree v e -> Tree v e 
revRec (Node v [])  = Node v [] 
revRec (Node v (x:xs)) = Node v (revRec xs ++ [x]) 

Obviosuly私はxsリスト以来xsとrevRecを呼び出すことはできません：私はこのようになります関数を記述しようとしていました。私はちょうど私がそれが難しくないshoudn'tのように感じるにもかかわらず私はちょうどこの問題のまわりで私の頭を包むことができない。

Answer 1

ゼロスは、コードをクリーンアップします。あなたはそれらの多くの括弧を必要とせず、重複計算を避けるべきです。 fstとsndは同じものを2回使用していますか？ Meh。活用のパターンマッチング：

rev :: Tree v e -> Tree v e 
rev (Node v xs) 
    = let (es, cs) = unzip xs 
     xs' = rev' cs 
    in Node v $ zip es (map rev xs') 

rev' :: [Tree v e] -> [Tree v e] 
rev' [] = [] 
rev' (x:xs) = rev' xs ++ [x] 

rev'がすべてで、木々のリストに固有のものではないことをまずノート！ただreverse機能の非効率的な実装です。これはどのリストでも機能します。

第2のでは、このアンジッピング/ジップは少しぎこちない。これは実際にあなたが望むふるまいであると確信していますか？現在、子供のリストを逆転させているだけですが、の要素の順番は同じです。そうでない場合は、あなたがより良い1つの逆と一つのマップでそれをすべて行うだろう：

rev :: Tree v e -> Tree v e 
rev (Node v xs) = Node v . reverse $ map (\(e,c) -> (e, rev c)) xs 

または、でもよりよい、まず

import Control.Arrow 

rev (Node v xs) = Node v . reverse $ map (second rev) xs