Traversing generic trees

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

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
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]> 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: [hidden email]
> p: +44 751 070 5158
> ---- Original Message ----
>  From: "Ali Baharev"
>  To: [hidden email]
>  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
> [hidden email] (mailto:[hidden email])
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners (http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners)
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Imants Cekusins
In reply to this post by Ali Baharev
how about this:


data Tree a = L a | N [Tree a] deriving Show


l::a -> Tree a
l = L

n::a -> Tree a
n x = N [L x]

m::(a->Tree a) ->[a]-> Tree a
m f list = N $ f <$> list


run it like this:
m l [2,3]
m n [2,3]

any good?
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Ali Baharev
Dear Imants,

Thanks. Unfortunately, I am not sure I get it. It seems to me that it
generates a homogeneous list of either nodes with single leaver or
just leaves. Or how would the

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

input look like, when using your proposed approach?

Ali

On Thu, Jul 23, 2015 at 1:10 AM, Imants Cekusins <[hidden email]> wrote:

> how about this:
>
>
> data Tree a = L a | N [Tree a] deriving Show
>
>
> l::a -> Tree a
> l = L
>
> n::a -> Tree a
> n x = N [L x]
>
> m::(a->Tree a) ->[a]-> Tree a
> m f list = N $ f <$> list
>
>
> run it like this:
> m l [2,3]
> m n [2,3]
>
> any good?
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Joel Williamson

Ali,

Nested lists with different nesting depths cannot be properly typed. You could probably get around this with a heterogenous collection (https://wiki.haskell.org/Heterogenous_collections), but the mechanisms proposed there strike me as overkill for this problem. QuasiQuoters could definitely do it, by defining a new grammar construct. That would be quite advanced, and would teach you more about meta-programming than about trees, algorithms or functional programming.

Using Imants' suggestion, you would write:

n [l 'a', n [l 'b', l 'c', n []], l 'd']

This is just as much boiler plate as you had in your initial definition of tree, but it uses shorter identifiers.


Joel


On Wed, 22 Jul 2015 19:27 Ali Baharev <[hidden email]> wrote:
Dear Imants,

Thanks. Unfortunately, I am not sure I get it. It seems to me that it
generates a homogeneous list of either nodes with single leaver or
just leaves. Or how would the

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

input look like, when using your proposed approach?

Ali

On Thu, Jul 23, 2015 at 1:10 AM, Imants Cekusins <[hidden email]> wrote:
> how about this:
>
>
> data Tree a = L a | N [Tree a] deriving Show
>
>
> l::a -> Tree a
> l = L
>
> n::a -> Tree a
> n x = N [L x]
>
> m::(a->Tree a) ->[a]-> Tree a
> m f list = N $ f <$> list
>
>
> run it like this:
> m l [2,3]
> m n [2,3]
>
> any good?
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Thomas Koster
In reply to this post by Ali Baharev
Hi Ali,

On 23 July 2015 at 07:24, Ali Baharev <[hidden email]> wrote:
> 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.
...
> 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 ++ " ] "
...
> 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?

On Wed, Jul 22, 2015 at 11:51 PM, elliot <[hidden email]> wrote:
> In general you don't produce large trees (or any data structure) by hand.

I am a Haskell novice myself, so don't take my advice as expert
opinion, but it sounds like you may have the wrong expectation about
what Haskell offers regarding "shorter", "cleaner", "purer" code. I
think Elliot was right to question your question.

You seem to want a more concise way to define a constant without
having to repeatedly type the data constructor names, hoping that the
compiler offers some nifty syntax for saving a few characters of
duplicated text. The answers by others seem to agree that "there isn't
any".

I think you should not focus so hard on trying to save a few
characters in the definition of "tree". The way I see it, the
"conciseness" aspect of functional programming is not really about
saving a few characters in the small. It is more about saving
thousands of lines of code in the large. You do this by using modular,
composable abstractions, and, in Haskell's case, exploiting laziness.
Focus instead on writing a higher-order traversal function that can be
used to write "toString" and all your other tree-traversing functions
as simple one-liners.

To get started, you should read this influential article by J. Hughes
[1][2]. The first third of the article demonstrates these ideas with
lists and trees. The article is well-suited to imperative programmers
learning their first functional language. You don't need a doctorate
to understand it. This should give you some hints on how to exploit
Haskell better in your own list and tree implementations. (Hughes'
tree data type is slightly different from yours; his has labels on all
the nodes, not just the leaves, but the lesson is still perfectly
relevant.)

[1] Hughes, J. "Why Functional Programming Matters", The Computer
Journal 32 (2), pp. 98-107, 1989.
[2] http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html

--
Thomas Koster
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Imants Cekusins
.. on the other hand, if facing this problem:
- import large trees from concise human-readable representation as string

, it is probably possible to write a parser which does just that.

After all json parser works somehow ;)

Just saying that you could do this in Haskell, given enough interest.
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Ali Baharev
Dear All,

I used to work at the University. Whenever a student asked me a
question, I first focused on the question and tried to answer it.
Sometimes the question was tough, maybe because there wasn't any easy
solution to the problem. In those situations I used to say to my
students: “Problem well spotted, unfortunately I cannot give you an
answer / there is no easy solution to this problem.” However, I have
never started questioning the questions of my students, especially
when I could not give them an answer.

According to the Wiki on [hidden email]: "Here, there is no
such thing as a 'stupid question.'" If you start questioning my
question, then I really do not know where to go...

You might as well say: The whole question is pointless, just use
Data.Tree and be done with it!

It is really not part of the original question, and I sooo not want to
get into a discussion over this: It is important to have language
support for helping humans to input data, without a full-blown parser.
Examples would be user-defined implicit type conversions and
user-defined literals in other statically typed languages.

OK, let's get back to the original question.

Apparently, there is no easy way to solve it with nested lists.
However, no one has touched the nested tuples so far. How can I write
a toString function that works similarly to mine but destructures
arbitrarily nested tuples?

Thanks,

Ali

On Thu, Jul 23, 2015 at 9:41 AM, Imants Cekusins <[hidden email]> wrote:

> .. on the other hand, if facing this problem:
> - import large trees from concise human-readable representation as string
>
> , it is probably possible to write a parser which does just that.
>
> After all json parser works somehow ;)
>
> Just saying that you could do this in Haskell, given enough interest.
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Bob Ippolito
You should not try and use the built-in lists or tuples to represent a tree data structure. That's not what they're good at. You probably could make tuples work and write functions using GHC.Generics to work with it as a tree data structure, but it definitely won't be easy or elegant. If you want a more economic syntax for expressing the tree you can provide shorter names for Leaf and Node (one char isn't too bad), or else you're stuck with using a parser. You may not have to write a parser though, perhaps JSON or YAML would work fine for this. If it needs to go in the source file, there's always TemplateHaskell and QuasiQuotes.

On Thu, Jul 23, 2015 at 9:48 AM, Ali Baharev <[hidden email]> wrote:
Dear All,

I used to work at the University. Whenever a student asked me a
question, I first focused on the question and tried to answer it.
Sometimes the question was tough, maybe because there wasn't any easy
solution to the problem. In those situations I used to say to my
students: “Problem well spotted, unfortunately I cannot give you an
answer / there is no easy solution to this problem.” However, I have
never started questioning the questions of my students, especially
when I could not give them an answer.

According to the Wiki on [hidden email]: "Here, there is no
such thing as a 'stupid question.'" If you start questioning my
question, then I really do not know where to go...

You might as well say: The whole question is pointless, just use
Data.Tree and be done with it!

It is really not part of the original question, and I sooo not want to
get into a discussion over this: It is important to have language
support for helping humans to input data, without a full-blown parser.
Examples would be user-defined implicit type conversions and
user-defined literals in other statically typed languages.

OK, let's get back to the original question.

Apparently, there is no easy way to solve it with nested lists.
However, no one has touched the nested tuples so far. How can I write
a toString function that works similarly to mine but destructures
arbitrarily nested tuples?

Thanks,

Ali

On Thu, Jul 23, 2015 at 9:41 AM, Imants Cekusins <[hidden email]> wrote:
> .. on the other hand, if facing this problem:
> - import large trees from concise human-readable representation as string
>
> , it is probably possible to write a parser which does just that.
>
> After all json parser works somehow ;)
>
> Just saying that you could do this in Haskell, given enough interest.
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Ali Baharev
Dear Bob,

Thanks. OK, so you are saying that there is no easy way of doing it
with nested tuples either. Well, that's disappointing. :(

The custom parser is violating the third requirement ("without copying
the data into some other datastructure first").

It is a learning exercise: I am trying to understand how to achieve
certain things things in Haskell. I deliberately picked this exercise
because it is very challenging to do it in certain statically typed
languages, and I was curious how difficult it would be to solve it in
Haskell.

In my opinion, you can learn a lot about programming languages in
general by re-implementing algorithms in them and comparing the
difficulties you encountered on the way.

Best wishes,

Ali

On Thu, Jul 23, 2015 at 9:38 PM, Bob Ippolito <[hidden email]> wrote:

> You should not try and use the built-in lists or tuples to represent a tree
> data structure. That's not what they're good at. You probably could make
> tuples work and write functions using GHC.Generics to work with it as a tree
> data structure, but it definitely won't be easy or elegant. If you want a
> more economic syntax for expressing the tree you can provide shorter names
> for Leaf and Node (one char isn't too bad), or else you're stuck with using
> a parser. You may not have to write a parser though, perhaps JSON or YAML
> would work fine for this. If it needs to go in the source file, there's
> always TemplateHaskell and QuasiQuotes.
>
> On Thu, Jul 23, 2015 at 9:48 AM, Ali Baharev <[hidden email]> wrote:
>>
>> Dear All,
>>
>> I used to work at the University. Whenever a student asked me a
>> question, I first focused on the question and tried to answer it.
>> Sometimes the question was tough, maybe because there wasn't any easy
>> solution to the problem. In those situations I used to say to my
>> students: “Problem well spotted, unfortunately I cannot give you an
>> answer / there is no easy solution to this problem.” However, I have
>> never started questioning the questions of my students, especially
>> when I could not give them an answer.
>>
>> According to the Wiki on [hidden email]: "Here, there is no
>> such thing as a 'stupid question.'" If you start questioning my
>> question, then I really do not know where to go...
>>
>> You might as well say: The whole question is pointless, just use
>> Data.Tree and be done with it!
>>
>> It is really not part of the original question, and I sooo not want to
>> get into a discussion over this: It is important to have language
>> support for helping humans to input data, without a full-blown parser.
>> Examples would be user-defined implicit type conversions and
>> user-defined literals in other statically typed languages.
>>
>> OK, let's get back to the original question.
>>
>> Apparently, there is no easy way to solve it with nested lists.
>> However, no one has touched the nested tuples so far. How can I write
>> a toString function that works similarly to mine but destructures
>> arbitrarily nested tuples?
>>
>> Thanks,
>>
>> Ali
>>
>> On Thu, Jul 23, 2015 at 9:41 AM, Imants Cekusins <[hidden email]> wrote:
>> > .. on the other hand, if facing this problem:
>> > - import large trees from concise human-readable representation as
>> > string
>> >
>> > , it is probably possible to write a parser which does just that.
>> >
>> > After all json parser works somehow ;)
>> >
>> > Just saying that you could do this in Haskell, given enough interest.
>> > _______________________________________________
>> > Beginners mailing list
>> > [hidden email]
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Bob Ippolito
Well, you've picked the wrong beginner project :) This isn't really an algorithm that you're implementing, you're trying to reuse Haskell syntax to do something that it's not intended to do. Implementing algorithms in Haskell is a breeze if you are using a sane representation, but you need to use the right tools.

On Thu, Jul 23, 2015 at 2:11 PM, Ali Baharev <[hidden email]> wrote:
Dear Bob,

Thanks. OK, so you are saying that there is no easy way of doing it
with nested tuples either. Well, that's disappointing. :(

The custom parser is violating the third requirement ("without copying
the data into some other datastructure first").

It is a learning exercise: I am trying to understand how to achieve
certain things things in Haskell. I deliberately picked this exercise
because it is very challenging to do it in certain statically typed
languages, and I was curious how difficult it would be to solve it in
Haskell.

In my opinion, you can learn a lot about programming languages in
general by re-implementing algorithms in them and comparing the
difficulties you encountered on the way.

Best wishes,

Ali

On Thu, Jul 23, 2015 at 9:38 PM, Bob Ippolito <[hidden email]> wrote:
> You should not try and use the built-in lists or tuples to represent a tree
> data structure. That's not what they're good at. You probably could make
> tuples work and write functions using GHC.Generics to work with it as a tree
> data structure, but it definitely won't be easy or elegant. If you want a
> more economic syntax for expressing the tree you can provide shorter names
> for Leaf and Node (one char isn't too bad), or else you're stuck with using
> a parser. You may not have to write a parser though, perhaps JSON or YAML
> would work fine for this. If it needs to go in the source file, there's
> always TemplateHaskell and QuasiQuotes.
>
> On Thu, Jul 23, 2015 at 9:48 AM, Ali Baharev <[hidden email]> wrote:
>>
>> Dear All,
>>
>> I used to work at the University. Whenever a student asked me a
>> question, I first focused on the question and tried to answer it.
>> Sometimes the question was tough, maybe because there wasn't any easy
>> solution to the problem. In those situations I used to say to my
>> students: “Problem well spotted, unfortunately I cannot give you an
>> answer / there is no easy solution to this problem.” However, I have
>> never started questioning the questions of my students, especially
>> when I could not give them an answer.
>>
>> According to the Wiki on [hidden email]: "Here, there is no
>> such thing as a 'stupid question.'" If you start questioning my
>> question, then I really do not know where to go...
>>
>> You might as well say: The whole question is pointless, just use
>> Data.Tree and be done with it!
>>
>> It is really not part of the original question, and I sooo not want to
>> get into a discussion over this: It is important to have language
>> support for helping humans to input data, without a full-blown parser.
>> Examples would be user-defined implicit type conversions and
>> user-defined literals in other statically typed languages.
>>
>> OK, let's get back to the original question.
>>
>> Apparently, there is no easy way to solve it with nested lists.
>> However, no one has touched the nested tuples so far. How can I write
>> a toString function that works similarly to mine but destructures
>> arbitrarily nested tuples?
>>
>> Thanks,
>>
>> Ali
>>
>> On Thu, Jul 23, 2015 at 9:41 AM, Imants Cekusins <[hidden email]> wrote:
>> > .. on the other hand, if facing this problem:
>> > - import large trees from concise human-readable representation as
>> > string
>> >
>> > , it is probably possible to write a parser which does just that.
>> >
>> > After all json parser works somehow ;)
>> >
>> > Just saying that you could do this in Haskell, given enough interest.
>> > _______________________________________________
>> > Beginners mailing list
>> > [hidden email]
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>> _______________________________________________
>> Beginners mailing list
>> [hidden email]
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
>
> _______________________________________________
> Beginners mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Traversing generic trees

Thomas Koster
In reply to this post by Ali Baharev
Ali,

On 23 July 2015 at 07:24, Ali Baharev <[hidden email]> wrote:
> I have started learning Haskell recently, and I try to reimplement
> interesting algorithms that are challenging to do in other languages.
..
> 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.

On Wed, Jul 22, 2015 at 11:51 PM, elliot <[hidden email]> wrote:
> In general you don't produce large trees (or any data structure) by hand.

On 23 July 2015 at 16:05, Thomas Koster <[hidden email]> wrote:

> I am a Haskell novice myself, so don't take my advice as expert
> opinion, but it sounds like you may have the wrong expectation about
> what Haskell offers regarding "shorter", "cleaner", "purer" code. I
> think Elliot was right to question your question.
>
> To get started, you should read this influential article by J. Hughes
> [1][2].
>
> [1] Hughes, J. "Why Functional Programming Matters", The Computer
> Journal 32 (2), pp. 98-107, 1989.
> [2] http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html

On 24 July 2015 at 02:48, Ali Baharev <[hidden email]> wrote:
> I used to work at the University.
...
> I have never started questioning the questions of my students,
> especially when I could not give them an answer.
...
> OK, let's get back to the original question.
>
> Apparently, there is no easy way to solve it with nested lists.
> However, no one has touched the nested tuples so far. How can I write
> a toString function that works similarly to mine but destructures
> arbitrarily nested tuples?

Sorry, my point was not to defend Elliot's useless response (he didn't
actually respond to the list anyway). I admit that "to question your
question" was a poor phraseology.

From your original email, your question regarding the efficacy of
nested lists or tuples for implementing a tree data structure seems to
have been motivated by a desire to reduce the amount of typing in a
tree constant.

The question itself has already been answered by others with "neither
of these are appropriate." But now what?

My point is that this exercise of saving some characters in the
definitions of constants by fiddling with the data structure will not
really lead to any useful intuitions about Haskell. Instead, Hug89
demonstrates two concepts (higher-order functions and laziness) that
really do show you what makes non-strict functional languages like
Haskell exceptional. Not only that, Hughes does this by talking you
through some functions for lists, trees and numerical algorithms,
which all sound very relevant to your learning project.

--
Thomas Koster
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners