Suggested way to print a custom quadtree in Haskell?

Question

Using quadtrees in a project like so:

data Node = A | B | C  deriving (Show) 

data QuadTree = Null | Node Node (QuadTree) (QuadTree) (QuadTree) (QuadTree)
  deriving Show

These quadtrees are expected to be of up to depth 5 and as you can imagine it very quickly becomes hard to understand the contents of the tree when just outputting with the derived Show.

At depth 1, using derived Show, I'm already working with something like:

Node A (Node B Null Null Null Null) (Node B Null Null Null Null) (Node C Null Null Null Null) (Node B Null Null Null Null)

My current approach to simplifying this output is to use:

toArray (Node x child1 child2 child3 child4) = [x] ++ toArray child1 ++ toArray child2 ++ toArray child3 ++ toArray child4

... which simplifies things a lot: [A, B, B, C, B] in place of the alternative, but still becomes quickly hard to interpret as the tree grows.

Does anyone have any nifty tricks or tips on this they could please share? Any advice is much appreciated.

Edit: to clarify, I just want to be able to see the contents of the tree as any viewable content in the least most migraine inducing way while debugging the algorithms I'll use on the trees

user_745903 · Answer

If your aim is just to get a well-interpretable graphical view, I recommend not going through plaintext at all but instead generating HTML and let your browser take care for laying it out in a convenient way. A particularly easy library with which to do that is yeamer (warning: it has quite heavy dependencies)

{-# LANGUAGE OverloadedStrings #-}

import Presentation.Yeamer
import GHC.Exts (IsString(..))

data Node = A | B | C  deriving (Show)

data QuadTree = Null | Node Node (QuadTree) (QuadTree) (QuadTree) (QuadTree)
  deriving Show

displayQuadTree :: QuadTree -> Presentation
displayQuadTree Null = "Null"
displayQuadTree (Node x ch₀ ch₁ ch₂ ch₃)
   =        "Node "<>fromString (show x)         -- Note: the ── and │ operators
                          ──                     -- are Unicode Box-Drawing 
      displayQuadTree ch₀ │ displayQuadTree ch₁  -- characters. You can also
                          ──                     -- use === and ||| instead.
      displayQuadTree ch₂ │ displayQuadTree ch₃

main :: IO ()
main = yeamer . displayQuadTree
         $ Node A (Node B Null Null Null Null)
                  (Node B Null Null Null Null)
                  (Node C Null Null Null Null)
                  (Node B Null Null Null Null)

When running this and pointing your browser to http://localhost:14910, you'll see

Readability can be further improved, even for large trees, with some CSS tweaks:

{-# LANGUAGE OverloadedStrings, QuasiQuotes #-}

import Presentation.Yeamer
import GHC.Exts (IsString(..))
import Text.Cassius

data Node = A | B | C  deriving (Show)

data QuadTree = Null | Node Node (QuadTree) (QuadTree) (QuadTree) (QuadTree)
  deriving Show

displayQuadTree :: QuadTree -> Presentation
displayQuadTree Null = "Null"
displayQuadTree (Node x ch₀ ch₁ ch₂ ch₃) = "qt-node-box" #% do
     "Node "<>fromString (show x)
                          ──
      displayQuadTree ch₀ │ displayQuadTree ch₁
                          ──
      displayQuadTree ch₂ │ displayQuadTree ch₃

main :: IO ()
main = yeamer . styling
           ([cassius|
              body
                background-color: black
                color: white
                font-size: 24pt
              .qt-node-box
                border: 1px solid grey
                font-size: 70%
            |]())
        . displayQuadTree
         $ Node A
            (Node A (Node B Null Null Null Null)
                    (Node B Null Null Null Null)
                    (Node C Null Null Null Null)
                    (Node B Null Null Null Null))
            (Node B (Node B Null Null Null Null)
                    (Node B Null Null Null Null)
                    (Node C Null Null Null Null)
                    (Node B Null Null Null Null))
            (Node C (Node B Null Null Null Null)
                    (Node B Null Null Null Null)
                    (Node C Null Null Null Null)
                    (Node B Null Null Null Null))
            (Node A (Node B Null Null Null Null)
                    (Node B Null Null Null Null)
                    (Node C Null Null Null Null)
                    (Node B Null Null Null Null))

Yeamer also makes it easy to interactively hide&expand subtrees: if you change the Node clause to

displayQuadTree (Node x ch₀ ch₁ ch₂ ch₃)
 = "Node "<>fromString (show x) ── do
     "..."
     "qt-node-box" #% (
       displayQuadTree ch₀ │ displayQuadTree ch₁
                           ──
       displayQuadTree ch₂ │ displayQuadTree ch₃
      )

then it'll at first show only

and by clicking on the ellipses you can then expand only the parts that are actually interesting, like first

then

then finally

This feature makes all of it usable even for extremely big trees, where a complete view would be overwhelming.

Suggested way to print a custom quadtree in Haskell?

1 Answers