Haskellでバイナリツリーが左から右に移動するかどうかを確認します。

Question

次のツリーがあり、これはノードとリーフのInt値にアクセスする方法です。私がしたいのは、ツリーが左から右に横断されるときにノード/リーフの値が増加しているかどうかを調べる関数 "areValuesIncreasing"を書くことです。どんな助けもありがとう。

 4     4 
    / \    / \ 
    2  3    3  2 
/\ /\   /\ /\ 
    1 3 4 5 - True 1 3 5 4 - False 



    data Tree = Node Tree Int Tree | Leaf Int deriving Show 

    treeToInt (Node _ n _) = n 
    treeToInt (Leaf n) = n 

    areValuesIncreasing:: Tree -> Bool 

Answer 1

私は重く

data Tree a = Node (Tree a) a (Tree a) 
      | Leaf a 
      deriving (...) 

にTreeを変更することはお勧めし、私の答えでこれを使用しますが、あなたのTreeにそれを変換することはどこでもa ~ Intを設定し、TreeでTree Intを交換するのと同じくらい簡単です。

各レイヤーの要素のリストを作成し、それらのすべてが並べ替えられていることを確認します。葉が無限に多くの空のレベル

leafCase x = [x] : repeat [] 

そして続いレベルでの単一の要素があるよう

foldTree :: (a -> b) ->   -- Leaf case 
      (b -> a -> b -> b) -> -- Node case 
      Tree a -> b 

葉は、repeat []続いシングルトンリストを含むリストを作成あなたが機能を持っていると仮定すると、

nodeCase l x r = [x] : zipWith (++) l r 

フォールtを：また、上にシングルトンリストにその要素を配置しながら内部ノードは、サブツリーリストサブリストのペアごとを連結します彼以上のレベルのリストを取得し、最後の空でないものの後にそれを遮断するTree：各レベルがソートされていることを

levels = takeWhile (not . null) . foldTree leafCase nodeCase 

はチェック：

sorted = all (uncurry (<=)) . (zip <*> tail) 

一つの機能

にそれをすべてをミックスし recursion-schemesと

sortedTree = all sorted . takeWhile (not . null) . levels 
    where sorted = all (uncurry (<=)) . (zip <*> tail) 
     levels = foldTree (\l -> [l] : repeat []) (\l x r -> [x] : zipWith (++) l r) 

---

同じこと：

makeBaseFunctor ''Tree 
-- data TreeF a b = NodeF b a b | LeafF a 
-- ... 
levelsSorted :: (Recursive t, Foldable (Base t), Ord a) => (Base t [[a]] -> a) -> t -> Bool 
levelsSorted get = all sorted . takeWhile (not . null) . levels 
    where sorted = all (uncurry (<=)) . (zip <*> tail) 
      levels = cata $ \x -> [get x] : foldr (zipWith (++)) (repeat []) x 

levelsSortedTree :: Ord a => Tree a -> Bool 
levelsSortedTree = levelsSorted $ \case { LeafF _ x _ -> x; NodeF x -> x }