ExtEnc.hs

{-
Extension tree-encoding (TATA) or tree currying (elsewhere) is a tricky beast. Understanding
requires a certain focus of mind.
This simple program generates dot representation of hedge- and extension-encoded trees.
This helps to explore certain corner-cases crucial for understanding.
It uses dotgen package for Graphviz handling.
-}
module Main where

import Control.Monad

-- dotgen-0.4.2
import Text.Dot 

data Tree a = Tree a [Tree a] deriving (Eq, Show)

-- tree combinators
t = Tree
l a = Tree a []

-- make dot for hedge tree
dotTree :: Tree Char -> Dot NodeId
dotTree (Tree a hedge) = do    
    root <- node [("label", [a])]
    forM_ hedge $ \t -> do        
        n <- (dotTree t)
        root .->. n
    return root

-- extension-encoded tree a.k.a. binary tree
data Ext a = Ext (Ext a) (Ext a)
           | E a
           deriving (Eq, Show)

ext (Tree a []) = E a
ext (Tree a hedge) =
    Ext (ext $ Tree a (init hedge))
        (ext $ last hedge)

-- make dot for extension-encoded tree
extDot :: Ext Char -> Dot NodeId
extDot (E a) = do
    node [("label",[a])]
extDot (Ext a b) = do
    r <- node [("label","@")]
    a' <- extDot a
    b' <- extDot b
    r .->. a'
    r .->. b'
    return r

main = do
    let tt = t '*' [l 'a', t 'b' [l 'u', l 'v', t 'w' [l 'x', l 'y', l 'z']], l 'c']
    writeFile "dot.gv" . showDot . dotTree $ tt
    writeFile "dot-ext.gv" . showDot . extDot . ext $ tt