Haskell Faltung algebraischer Datentypen

Beispiele:

foldr verallgemeinert

data IL = Cons Int IL | Err String | Mt  
  
foldIL :: (Int -> b -> b) -> (String -> b) -> b -> IL -> b   
foldIL f e a (Cons i il) = f i (foldIL f e a il)   
foldIL f e a (Err str)   = e str   
foldIL f e a Mt          = a  

Bool

data Bool = False | True   
  
foldBool :: b -> b -> Bool -> b   
foldBool a1 a2 False = a1   
foldBool a1 a2 True  = a2  

Maybe

data Maybe a = Nothing | Just a   
  
foldMaybe :: b -> (a -> b) -> Maybe a -> b   
foldMaybe b f Nothing  = b   
foldMaybe b f (Just a) = f a  

Binärbäume

data Tree a = Mt | Node a (Tree a) (Tree a)  
  
foldT :: (a -> b -> b -> b)-> b -> Tree a -> b   
foldT f e Mt = e   
foldT f e (Node a l r) = f a (foldT f e l) (foldT f e r)  
  
  
> foldT (\a b c -> a+b+c) 0 (Node 1 (Node 5 Mt Mt) (Node 2 Mt Mt))   
8  

Haskell Foldable

Data.Foldable

class Foldable t where   
	...   
	foldr :: (a -> b -> b) -> b -> t a -> b   
	...  

• Für Datentypen mit zwei Konstruktoren

Beispiel Binärbaum

data Tree a = Leaf a | Node (Tree a) (Tree a)   
  
instance Foldable Tree where   
	foldr f v (Leaf x) = f x v   
	foldr f v (Node l r) = foldr f (foldr f v r) l   
	  
 > foldr (*) 1 (Node (Node (Leaf 2) (Leaf 4)) (Leaf 6))   
 48  

Link to original