[Haskell-beginners] Traversing generic trees

[Ali Baharev]

Dear All,

I have started learning Haskell recently, and I try to reimplement
interesting algorithms that are challenging to do in other languages.
I would like to ask you for your kind help with a problem that I am
stuck with.

A generic tree is given in the form of nested sequences (nested lists
or nested tuples) and I would like to traverse it in (1) depth-first
order,  (2) lazily and (3) without copying the data into some other
datastructure first. I test the algorithm by pretty printing the tree.
My goal is learning, so Data.Tree is not an option (although I did
look into its implementation).

Here is my first attempt:

data Tree a = Leaf a | Node [Tree a]

tree = Node [Leaf 'a', Node [Leaf 'b', Leaf 'c', Node []], Leaf 'd']

toString :: (Show a) => Tree a -> String
toString (Leaf leaf)  = " " ++ show leaf ++ " "
toString (Node nodes) = " [ " ++ concatMap toString nodes ++ " ] "

main = print $ toString tree

It (more or less) satisfies the above requirements. The pretty
printing is not very pretty but the part that I am really not happy
with is the lot of code duplication in giving the tree. I would like
to enter it as:

tree = ['a', ['b', 'c', []], 'd']

which of course won't work.

Is there a (not too obscure) way to help the compiler so that it
understands that 'a' means Leaf 'a', etc?

I have also tried

tree = ('a', ('b', 'c', ()), 'd')

but then I do not know how to destructure the nested tuples.

Any help is greatly appreciated.

Ali