Dear Elliot, The question is whether there is a (not too obscure) way to eliminate the code duplication, or how the code duplication can be avoided using nested tuples instead. Please try to answer the question. Ali On Wed, Jul 22, 2015 at 11:51 PM, elliot wrote:

In general you don't produce large trees (or any data structure) by hand. It's slightly frustrating to test of course (as you've discovered) but for the most part you'll only need to produce small structures.

-- e: elliot@citrusbytes.net p: +44 751 070 5158 ---- Original Message ---- From: "Ali Baharev" To: beginners@haskell.org Sent: Wed, Jul 22, 2015, 10:24 PM Subject: [Haskell-beginners] Traversing generic trees 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 _______________________________________________ Beginners mailing list Beginners@haskell.org (mailto:Beginners@haskell.org) http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners (http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners)