Can the composite pattern be used to generate HTML from a tree and handle the indenting as well, or this inherently not possible?

Question

I watched this video on the composite pattern, where the main example is how to use the pattern as a mean to generate HTML code from a tree structure describing a todo list where each item can be in turn a todo list, and it seems a convenient test-bed, so here it is a target HTML:

[ ] Main
<ul>
  <li>[ ] 1.</li>
  <li>[ ] 2.
    <ul>
      <li>[ ] 2.1</li>
      <li>[ ] 2.2</li>
    </ul>
  </li>
  <li>[ ] 3.</li>
</ul>

(Sorry if the top [ ] Main doesn't make sense, but I don't know HTML; furthermore that's irrelevant to my question, I believe.)

I understand that design patterns are mostly an OOP "thing", however I'm often referring to the article Design Patterns in Haskell to understand how they can be reinterpreted in functional programming, with the aim of understanding them at a deeper level.

As regards the composite pattern, that article essentially reads:

Composite. Recursive algebraic data types. Especially prominent since there's no built-in inheritance.

Therefore I thought it would be easy to try it in Haskell, and I came up with this code:

import Data.List (intercalate)

data Todo = Todo String | TodoList String [Todo] deriving Show

showList' :: Todo -> String
showList' (Todo s) = "[ ] " ++ s
showList' (TodoList s ts) = "[ ] " ++ s
                          ++ "<ul><li>"
                          ++ intercalate "</li><li>" (map showList' ts)
                          ++ "</li></ul>"

which, fed like this

putStrLn $ showList' $ TodoList "Main" [Todo "1.", TodoList "2." [Todo "2.1", Todo "2.2"], Todo "3."]

generates this output

[ ] Main<ul><li>[ ] 1.</li><li>[ ] 2.<ul><li>[ ] 2.1</li><li>[ ] 2.2</li></ul></li><li>[ ] 3.</li></ul>

which is essentially the HTML at the top of my question rendered on a single line: it's clear from my implementation of showList' that once a call to it (at any depth of the recusion) returns a string, that string is not altered in any way, just concateneted with others. So I feel that there's isn't much I can do to make showList' add \n and spaces to reach the nicely formatted HTML.

I've tried a bit, adding spaces and \n, but especially upon reading Composite as a monoid by Mark Seemann I start do be a bit doubtful about the feasibility of what I'm trying to do...

I'm tempted to reach the conclusion that if composite is a monoid, it means that the various items are combined two by two in the same way regardless of their depth in the tree, and so this means that adding space for a nice formatting is not possible because the amount of space to be added depends on the context surrounding the two elements being concatenated, and not just on the two elements.

However, I'm not really sure about my reasoning, hence I'm asking here.

Frowsy

on first glance it seems that not too hard to extend: add a depth parameter to showList', use it for indentation and increase it on the inner/recursive map (showLists' (depth+1)) call – Bookkeeping

Answer 1

This answer is a bit roundabout. (The comments already contain a perfectly valid and more straightforward suggestion.)

We can define this auxiliary type:

data Todo' a = Todo' String 
             | TodoList' String [a] 
             deriving Show

It's like Todo, but in the "recursive" step, instead of another Todo, we have a polymorphic value. We can put anything we wish there, including the original Todo:

peel :: Todo -> Todo' Todo
peel todo = case todo of
    Todo s -> Todo' s 
    TodoList s xs -> TodoList' s xs 

Why on earth would we want to do this? Well, sometimes we want to talk about a single "layer" of a recursive datatype, leaving open the question of what the layers below might contain.

Now we are going to reconstruct showList' in another way. First, this auxiliary function cata:

cata :: (Todo' a -> a) -> Todo -> a
cata f todo  = case peel todo of 
    Todo' s -> f (Todo' s)
    TodoList' s xs -> f (TodoList' s (map (cata f) xs))

This function says that, if we have a way to convert a single Todo' layer carrying some kind of result from the lower layers into a result for the current layer, then we are able to convert an entire Todo value into a result.

showList' can now be written as

showList'' :: Todo -> String
showList'' todo = cata layer todo
  where
  layer :: Todo' String -> String
  layer (Todo' s) = "[ ] " ++ s
  layer (TodoList' s xs) = "[ ] " ++ s
                           ++ "<ul><li>"
                           ++ intercalate "</li><li>" xs
                           ++ "</li></ul>"

Notice that this version doesn't have explicit recursion, cata takes care of it.

Ok. Now, as you mention, the problem with indenting is that the result of one layer depends on the number of layers that are above. The most natural way of expressing such dependency in Haskell is with a function of type Int -> String, where the Int is the number of layers above.

When we wrote showList', me made cata return a String. What if we made it return a function Int -> String instead?

showIndented :: Todo -> String
showIndented todo = cata layer todo 0
  where
  layer :: Todo' (Int -> String) -> Int -> String
  layer todo' indentation = 
    let tabs =  replicate indentation '\t'
     in case todo' of
        Todo' s -> 
            tabs ++  "<li>[ ] " ++ s ++ "</li>\n"
        TodoList' s fs ->
            tabs ++ "[ ] " ++ s ++ "\n" ++
            tabs ++ "<ul>\n" ++ 
            foldMap ($ succ indentation) fs ++ 
            tabs ++ "</ul>\n"

The foldMap ($ succ indentation) xs bit is taking a list of functions, calling all of them with the current level of indentation + 1, and concatenating the resulting strings.

Varsity

The cata function is a "catamorphism" blog.sumtypeofway.com/posts/… Usually the recursive form of the datatype is derived from the single-layer form using a type combinator called Fix but we didn't to that here for simplicity. Catamorphism "destroy" a data structure starting for the leaves; making the catamorphism return a function is a trick in the "folklore" for allowing the downward flow of information (in this case, the indentation level). – Varsity

...why have you gone the open recursion route at all? What part of this answer could not be done or said with the original data type and no extras? (I personally don't see any such part.) – Edging

Answer 2

It seems to me that you're expecting the Monoid or Composite abstraction to do something that it can't do. If there's a way to implement the desired functionality (indentation) using only the Monoid type class, I'm not aware of it...

This would be the same case, I think, with the Composite design pattern. In an object-oriented setting, how would you implement indentation with Composite?

That's not entirely clear to me, but then, I suppose it depends on how you'd want to implement something like the Todo type in object-oriented programming (OOP). In OOP, you typically model behaviour, whereas the Todo type here is a sum type, which can be mapped to a Visitor in OOP. I wonder, however, if this isn't a bit of a distraction.

A Composite is an object that 'makes many objects look like a single object'. If you squint hard enough, that fits the Semigroup and Monoid operations with the type a -> a -> a, or even better, their aggregation functions sconcat and mconcat, of which the latter has the type [a] -> a. Expressed in a more loose way, it enables us to take any number of a values and turn them into a single a - it makes many a look like a single a.

What you seem to be looking for here is rather a function that can digest a data structure into a potentially more compact value. Specifically, you're looking for Todo -> String, but more abstractly a function which in pseudo-Haskell we could attempt to describe as Complex -> Simple.

As danidiaz describes in his or her awesome answer, this looks more like a catamorphism. I'm deeply indebted to danidiaz for the following.

Before I read that answer, I figured that the Todo catamorphism would more naturally look like this:

foldTodo :: (String -> a) -> (String -> [a] -> a) -> Todo -> a
foldTodo leaf    _     (Todo s)       = leaf s
foldTodo leaf list (TodoList s todos) = list s $ foldTodo leaf list <$> todos

As you can tell, I decided to name it foldTodo, since there's a (weak) convention in Haskell that catamorphisms are often named like foldXyz.

That function is the central abstraction. The rest is just rendering functionality, starting with a little helper function to indent text:

indent :: Int -> String
indent n = replicate (2 * n) ' '

This function uses two spaces for each indentation, rather than a tab, as danidiaz does it.

Here's a function to render the leaf node in the Todo sum type:

renderLeaf :: String -> Int -> String
renderLeaf s depth = indent depth ++ "<li>[ ] " ++ s ++ "</li>\n"

And here's the corresponding function to render a (sub)list:

renderList :: String -> [Int -> String] -> Int -> String
renderList s fs depth =
  indent depth ++ "[ ] " ++ s ++ "\n" ++
  indent depth ++ "<ul>\n" ++ 
  foldMap ($ succ depth) fs ++
  indent depth ++ "</ul>\n"

As you can tell, I stole these two functions from danidiaz's layer function. I'd never thought about this myself, by it's a neat trick to use the catamorphism to convert the data structure to a function that takes the depth as input.

We can now use the catamorphism to render a Todo list:

render :: Todo -> String
render todo = foldTodo renderLeaf renderList todo 0

The foldTodo renderLeaf renderList todo part returns a function with the type Int -> String because that's what both renderLeaf and renderList return. This function can then be called with the top-level depth of 0 to return a String.

As far as I can tell, it works as intended:

> putStrLn $ render $ TodoList "Main" [Todo "1.", TodoList "2." [Todo "2.1", Todo "2.2"], Todo "3."]
[ ] Main
<ul>
  <li>[ ] 1.</li>
  [ ] 2.
  <ul>
    <li>[ ] 2.1</li>
    <li>[ ] 2.2</li>
  </ul>
  <li>[ ] 3.</li>
</ul>

To conclude, I still think that my theorem that Composites are monoids holds, but notice that I didn't claim that all monoids are Composites.

The Todo type in the OP isn't a Monoid instance, but as far as I can tell, it could be. I'm still not convinced that this would be sufficient to implement the desired functionality.

Norry

The first paragraph of your answer is the reason why I asked the question. If, as you say, composites are monoids, then one can't expect from a composite to be helpful in a scenario where a monoid isn't, right? So if the a monoid can't handle the indentation when "adding up" elements together (which is kind of clear to me: I'm tempted to reach the conclusion), then the composite pattern surely can't. And so, whatever I do to put elements together and handle the indentation, that's not the composite pattern. Am I summarizing correctly your thought? – Frowsy

@Frowsy Yes, that seems to summarise my thoughts well. FTR, I don't claim that it's impossible to reach the desired goal with a Composite; only that I currently fail to see how that'd be possible. But then again, until a few days ago, I was unaware of danidiaz's beutiful trick... I could be wrong. – Norry

Answer 3

Wow. The other answers are really, really complicated, while it can be completely straightforward. You just implement a helper function that takes the amount of indentation (other answers represented this as an Int, I'll represent it as the String that Int corresponds to, but that's only a surface-level difference), and use the exact same pattern of pattern-matching-and-recursion as in the original code.

I'm going to use printf, but just because I find a lot of string concatenation ugly, not because it's fundamentally needed.

import Text.Printf

data Todo = Todo String | TodoList String [Todo] deriving Show

showList' :: Todo -> String
showList' = printf "<ul>\n%s</ul>" . go "  " where
    go :: String -> Todo -> String
    go indentation (Todo s) = printf "%s<li>[ ] %s</li>\n" indentation s
    go indentation (TodoList s ts) = printf
        "%s<li>[ ] %s\n  %s<ul>\n%s  %s</ul>\n%s</li>\n"
        indentation
        s
        indentation
        (concatMap (go ("    " ++ indentation)) ts) -- concatMap and foldMap are the same thing here, use whichever you like better
        indentation
        indentation

Again, the main two differences here are: my recursive helper go has an extra argument, and instead of intercalate I use concatMap.

Trying it out in ghci, with the same test list as you had:

> putStrLn . showList' $ TodoList "Main" [Todo "1.", TodoList "2." [Todo "2.1", Todo "2.2"], Todo "3."]
<ul>
  <li>[ ] Main
    <ul>
      <li>[ ] 1.</li>
      <li>[ ] 2.
        <ul>
          <li>[ ] 2.1</li>
          <li>[ ] 2.2</li>
        </ul>
      </li>
      <li>[ ] 3.</li>
    </ul>
  </li>
</ul>

Edging

Answer 4

While @MarkSeeman's blog post and answer here are thought-provoking, I'm not convinced that the Composite-as-Monoid approach is particularly helpful in general, even if there's some formal sense in which all Composites can be written monoidally. The original gang-of-four description of Composite is a tree of objects that can be treated uniformly. If Composites were intended to be monoidal, wouldn't this be a list of objects rather than a tree?

Now, there are some cases where, for a particular Composite, the tree structure is incidental and the Composite is naturally monoidal (e.g., maybe serializations or builders). In those cases, recognizing this may lead naturally to a Haskell implementation that's cleaner than the obvious OO implementation. However, where the tree structure is significant (e.g., indented to-do lists), trying to shoehorn it into a Monoid doesn't seem to buy you much.

Getting back to your data type:

data Todo = Todo String | TodoList String [Todo] deriving Show

This seems to be exactly the right recursive data type to represent to-do lists as a Composite.

In particular, an idiomatic OO implementation would involve a TodoItem item class (a "primitive"), a TodoList item class (a "container"), and some separate TodoObject abstract superclass to allow uniform treatment of primitives, containers, and containers of containers.

The usual mapping of class hiearchies like this to Haskell is to map the concrete classes to constructors, and the abstract class to the type for those constructors, and that's exactly what you've done, up to the specific choice of names:

data TodoObject = TodoItem String | TodoList String [TodoObject]

This is why the Haskell Design Patterns link spends all of two sentences on Composites. They are naturally expressed as recursive data types. End of story.

Well, maybe not "end of story". If you want to operate on such Haskell Composites algorithmically (e.g., rendering a Todo with indentation) in an idiomatic way, then you want to use the usual tools for working with recursive data types. These usually involve hand-coded catamorphisms:

myCata :: ToDo -> Result
myCata (Todo x) = ...result for this primitive...
myCata (TodoList x items) = let results = map myCata items in
    ...some result based on `results` for the contents...

where you're allowed to pass "state" through the recursion, using extra arguments for example. One of the advantages of a hand-coded catamorphism over a higher-order foldTodo function is that you don't have to introduce more complex mechanisms to implement basic tasks like indenting some text, like lifting a polymorphic type from Todo Todo to Todo (Int -> Todo) or introducing a Traversable type class and a Reader applicative, or whatever.

In other words, I think @DanielWagner's solution is an appropriate "real world" solution and more likely to be found in the wild than the solutions given in the other answers (which I think were intended to illustrate a point anyway, rather than offer a serious solution for your indentation problem).

My own solution is a little different. You may find it interesting, as it uses the original data type and implements indentation through post-processing of rendered blocks of lines rather than passing indentation as an argument and returning a single, multi-line String. I think this makes it more idiomatic as a functional programming solution, though possibly less performant.

data Todo = Todo String | TodoList String [Todo] deriving Show

render :: Todo -> [String]
render (Todo s) = ["[ ] " ++ s]
render (TodoList s items)
  =  [ "[ ] " ++ s
     , "<ul>" ]
  ++      indent (concat rendered_lis)
  ++ [ "</ul>" ]
  where rendered_lis = make_li . render <$> items

        -- indent a block of lines
        indent = map ("  " ++)
        -- make a block of lines into an <li> item
        --   - case for one line
        make_li [s] = ["<li>" ++ s ++ "</li>"]
        --   - case for multi-line
        make_li (s:ss)
          =  ["<li>" ++ s]
          ++     indent ss
          ++ ["</li>"]

showList' = unlines . render

Mezoff