Картирование по дереву

Question

Я новичок в Haskell, и для практики я выполнял кучу функций (map, length и т. Д.) С использованием foldr и foldl. Теперь я хочу двигаться на деревья!

Моя древовидная структура данных:

data Tree a = Node a [Tree a] deriving (Show) 

Я написал функцию Haskell сложить над деревьями:

treeFold :: (b->a->b) -> b -> Tree a -> b 
treeFold f s (Node a []) = f s a 
treeFold f s (Node a xs) = foldl f (f s a) (dFSList xs) 

где dFSList находится список всех узлов в дереве. Так что делайте что-то вроде:

treeFold (+) 0 (Node 1 [Node 2 [], Node 3 []]) 

возвращается 6. Прохладный.

Теперь я хочу написать функцию Haskell для отображения над деревьями, но я хочу использовать свою функцию treeFold для ее выполнения. Вот то, что я до сих пор:

treeMap f (Node a []) = (Node (f a) []) 
treeMap f (Node a (x:xs)) = (Node (f a) (a list involving foldTree somehow??)) 

Как закончить свою treeMap функцию? Я хочу быть в состоянии сделать

treeMap (+1) (Node 1 [Node 2 [], Node 3 []]) 

и он должен вернуть

(Node 2 [Node 3 [], Node 4 []]) 

Answer 1

Способ разделить деревья, как правило, с разным разнообразием складок (часто называемый катаморфизмом для какой-то теории теории, о которой я не знаю). У вас есть data Tree a = Node a [Tree a], так считать, что друг от друга, вы делаете

cat :: (a -> [b] -> b) -> Tree a -> b 
cat f (Node root children) = f root (map (cat f) children) 

Hokay? Так что теперь (используя стандартный Functor класс вместо специализированного treeMap),

instance Functor Tree where 
    fmap f = cat (Node . f) 

Вы также можете написать линейные складки, как это. Ваш treeFold меня смущает, но вы можете написать, например,

instance Foldable Tree where 
    foldMap f = cat go where 
    go root children = f root `mappend` fold children 

Еще сильнее,

instance Traversable Tree where 
    traverse f = cat go where 
    go root children = Node <$> f root <*> sequenceA children 

Answer 2

Вам не нужно treeFold, чтобы написать что-то вроде treeMap.

treeMap f (Node a xs) = Node (f a) (map (treeMap f) xs) 

Базовые классы, которые соответствуют тем же идей Foldable и Functor. Все в базе Foldable уже есть Functor; естественно иметь возможность определять treeMap независимо от treeFold.