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
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?
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 <imantc@gmail.com> 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
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 <ali.baharev@gmail.com> 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 <imantc@gmail.com> 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Hi Ali, On 23 July 2015 at 07:24, Ali Baharev <ali.baharev@gmail.com> 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 <elliot@citrusbytes.net> 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
.. 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.
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 beginners@haskell.org: "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 <imantc@gmail.com> 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
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 <ali.baharev@gmail.com> 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 beginners@haskell.org: "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 <imantc@gmail.com> 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
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 <bob@redivi.com> 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 <ali.baharev@gmail.com> 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 beginners@haskell.org: "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 <imantc@gmail.com> 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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
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 <ali.baharev@gmail.com> 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 <bob@redivi.com> 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 <ali.baharev@gmail.com> 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 beginners@haskell.org: "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 <imantc@gmail.com>
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 Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Ali, On 23 July 2015 at 07:24, Ali Baharev <ali.baharev@gmail.com> 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 <elliot@citrusbytes.net> wrote:
In general you don't produce large trees (or any data structure) by hand.
On 23 July 2015 at 16:05, Thomas Koster <tkoster@gmail.com> 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 <ali.baharev@gmail.com> 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
participants (5)
-
Ali Baharev -
Bob Ippolito -
Imants Cekusins -
Joel Williamson -
Thomas Koster