Collect data on existing tree data

Question

Say we have tree-like data, and we would like to add depth information for each node. How can we easily achieve this?

Data Tree = Node Tree Tree | Leaf

For each node, we would like to know in constant difficulty how deep it is. We have data from an external module, so we have information as shown above. A real example is an external HTML parser that simply provides an XML tree, and we would like to collect data, for example. how many hyperlinks each node contains.

Functional languages ​​are created for moving trees and collecting data; there should be a simple solution.

The obvious solution will create a parallel structure. Can we do better?

Answer 1

The standard trick that I learned from the wonderful Chris Okasaki, Purely functional data structures , should cache the results of costly operations on each node. for you to build a tree did not have to hurt. For example, when an expensive operation is depth, you can write:

module SizedTree (SizedTree, sizedTree, node, leaf, depth) where

data SizedTree = Node !Int SizedTree SizedTree | Leaf

node l r = Node (max (depth l) (depth r) + 1) l r
leaf = Leaf

depth (Node d _ _) = d
depth Leaf = 0

-- since we don't expose the constructors, we should
-- provide a replacement for pattern matching
sizedTree f v (Node _ l r) = f l r
sizedTree f v Leaf = v

Building SizedTreecosts O (1) additional work in each node (therefore, O (n) works to convert n-node Treeto SizedTree), but the gain is that checking the depth of a SizedTreeor any subtree is an O (1) operation.

Answer 2

, Int s. Tree

data Tree a = Node Tree a Tree | Leaf a

annDepth :: Tree a -> Tree (Int, a)

Tree - Tree () .

---

- , :

{-# LANGUAGE GADTs, DataKinds #-}

data Shape = SNode Shape Shape | SLeaf

data Tree a sh where
    Leaf :: a -> Tree a SLeaf
    Node :: Tree a lsh -> a -> Tree a rsh -> Tree a (SNode lsh rsh)

, , unannotated. .

---

, Haskell ?

Answer 3

- , @DanielWagner, . , : .

, a la carte , . compdata.

, . , stable-memo. , , , .