CODEWITHSUNDEEP
haskelltree
Anton Harald
Anton Harald

Reputation: 5944

attach the path of each element in a tree

Consider the following tree data structure:

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

and a function which attaches to each element its path in the tree:

withPath :: Tree a -> Tree (a, [a])
withPath t = go [] t where
  go path (Node v xs) = Node (v, p) (map (go p) xs) where
    p = path ++ [v]

withPath (Node 4 [Node 3 [], Node 5 []])
--> Node (4,[4]) [Node (3,[4,3]) [],Node (5,[4,5]) []]

Is this the way to do it? I'm looking for a way to avoid the construction of the path by concatenation.

here is a solution proposed by jberryman.

withPath' :: Tree a -> Tree (a, [a])
withPath' t = go id t where
  go f (Node v xs) = Node (v, f' []) (map (go f') xs) where
    f' = f . (v:)

Upvotes: 1

Views: 132

Answers (1)

danidiaz
danidiaz

Reputation: 27756

Here's another (not necessarily simpler) way to do it, using a recursion scheme called a catamorphism. Data.Tree in the latest version of containers has the function:

foldTree :: (a -> [b] -> b) -> Tree a -> b

Which is a catamorphism on trees (compared to foldr, which is the catamorphism for lists). Given an auxiliary function, it "destroys" the tree starting from the leaves and going upwards to the root.

However, we actually want to go the other way: we want to start at the root and propagate the path information to each subtree.

Turns out that there is a trick for doing this using a catamorphism: instead of making the catamorphism return the path-annotated tree directly, make it return a function that takes a root path and returns the path-annotated tree. Something like:

import Data.Tree
import Data.List.NonEmpty

inherit :: Tree a -> Tree (NonEmpty a)
inherit tree = foldTree algebra tree [] where
    algebra :: a -> [[a] -> Tree (NonEmpty a)] -> [a] -> Tree (NonEmpty a)
    algebra a fs as = Node (a:|as) (fs <*> [a:as])

Here, the result of the catamorphism is of type [a] -> Tree (NonEmpty a). inherit supplies the initial empty path.

A simpler version of this trick is expressing foldl in terms of foldr (if you squint a little, the first element of a list is like the “root” of a linear tree). A beefed-up version of this trick allows calculating inherited attributes in attribute grammars.

The idea that being able to return functions form a catamorphism increases its expressive power is explained in section 5 of the paper "A tutorial on the universality and expressiveness of fold".

Upvotes: 1

Related Questions