höherer Ordnung Haskell Funktionen Angewandt auf Bäume

Question

Ich habe den Datentyp

data Tree a = Null | Node a {lTree, rTree :: Tree a} 

Ich möchte die folgenden Funktionen höherer Ordnung neu zu schreiben, so dass sie auf Bäume anwenden können.

map :: (a -> b) -> Tree a -> Tree b 

fold :: (a -> b -> a) -> a -> Tree b -> a 

foldl :: (a -> b -> a) -> a -> Tree b -> a 

foldr :: (a -> b -> b) -> b -> Tree a -> b 

filter :: (a -> Bool) -> Tree a -> Tree a 

zip :: Tree a -> Tree b -> Tree (a,b) 

Ich möchte wissen, wie Sie die Funktionen explizit zu schreiben, zum Beispiel weiß ich, dass die Kartenfunktion geschrieben werden kann:

treeMap :: (a ->b) -> Tree a -> Tree b 
treeMap f tree = case tree of 
    Null -> Null 
    Node a Null Null -> Node (f a) Null Null 
    Node a l r -> Node (f a) (treeMap f l) (treeMap f r) 

Answer 1

Hier ist etwas, das Ihnen helfen kann:

Lassen t1 sei dieser Baum (vom Typ Tree String)

 "a" 
    /\ 
    "b" "c" 
/ \ 
"d"  "e" 
     /\ 
     "f" "g" 

F Erstens - wie würden Sie es in Bezug auf Null und Node Konstruktoren schreiben?

Zweitens - was wäre fold (++) t1?

Answer 2

Hier ist ein Schritt-für-Schritt-Ansatz. Wir werden uns nur auf treeFoldr konzentrieren.

Der grundlegende und langweilig Weg

data Tree a = Null | Node (Tree a) a (Tree a) 

Wir von einem grundlegenden Ansatz beginnen treeFoldr zu definieren: wir zuerst Liste konvertieren, dann foldr verwenden.

-- In-order visit 
toList :: Tree a -> [a] 
toList Null = [] 
toList (Node l a r) = toList l ++ [a] ++ toList r 

treeFoldr_1 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_1 f x t = foldr f x $ toList t 

Equational Argumentation zur Rettung

Jetzt verwandeln wir treeFoldr_1 in eine rekursive Definition, die Zwischenliste und den foldr Anruf zu entfernen.

Wir teilen die Definition von treeFoldr_1, durch Fälle auf t.

treeFoldr_2 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_2 f x Null   = foldr f x $ toList Null 
treeFoldr_2 f x (Node l a r) = foldr f x $ toList (Node l a r) 

Wir erweitern toList.

treeFoldr_3 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_3 f x Null   = foldr f x [] 
treeFoldr_3 f x (Node l a r) = foldr f x (toList l ++ [a] ++ toList r) 

Hier nutzen wir eine foldr Eigenschaft:

-- foldr f x (ys ++ zs) = foldr f (foldr f x zs) ys 

treeFoldr_4 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_4 _ x Null   = x 
treeFoldr_4 f x (Node l a r) = 
    foldr f (foldr f x ([a] ++ toList r)) (toList l) 

wieder zu erhalten, wir die gleiche foldr Gleichung gelten.

treeFoldr_5 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_5 _ x Null   = x 
treeFoldr_5 f x (Node l a r) = 
    foldr f (foldr f (foldr f x (toList r)) [a]) (toList l) 

Nach Definition von foldr können wir

-- foldr f z [a] = f a z 

Erhalten

treeFoldr_6 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_6 _ x Null   = x 
treeFoldr_6 f x (Node l a r) = 
    foldr f (f a (foldr f x (toList r))) (toList l) 
       -- ^^^^^^^^^^^^^^^^^^^^^^ 

Jetzt vereinfachen, foldr f x (toList t) ist treeFoldr f x t, so können wir einen rekursiven Aufruf versuchen, dieses Muster zu ersetzen.

treeFoldr_7 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_7 _ x Null   = x 
treeFoldr_7 f x (Node l a r) = 
    foldr f (f a (treeFoldr_7 f x r)) (toList l) 
-- ^^^^^^^...........................^^^^^^^^^^ 

Wieder dasselbe Muster.

treeFoldr_8 :: (a -> b -> b) -> b -> Tree a -> b 
treeFoldr_8 _ x Null   = x 
treeFoldr_8 f x (Node l a r) = 
    treeFoldr_8 f (f a (treeFoldr_8 f x r)) l 

... und wir sind fertig. Keine Listen mehr!

Kleiner Test

test :: Tree Int 
test = Node 
     (Node Null 2 Null) 
     5 
     (Node 
     (Node Null 4 Null) 
     1 
     (Node Null 7 Null)) 

foo :: Int -> String -> String 
foo n s = "(" ++ show n ++ ", " ++ s ++ ")" 

-- *TreeFoldable> treeFoldr_8 foo "X" test 
-- "(2, (5, (4, (1, (7, X)))))"