[Haskell-beginners] Traversing generic trees

[Ali Baharev]

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 <elliot at citrusbytes.net> 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 at citrusbytes.net
> p: +44 751 070 5158
> ---- Original Message ----
>  From: "Ali Baharev"
>  To: beginners at 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 at haskell.org (mailto:Beginners at haskell.org)
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners (http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners)