Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Traversing generic trees (Ali Baharev)
2. Re: Traversing generic trees (Ali Baharev)
3. Re: Traversing generic trees (Imants Cekusins)
4. Re: Traversing generic trees (Ali Baharev)
5. Re: Traversing generic trees (Joel Williamson)
6. Re: Traversing generic trees (Thomas Koster)
7. Re: Traversing generic trees (Imants Cekusins)
----------------------------------------------------------------------
Message: 1
Date: Wed, 22 Jul 2015 23:24:07 +0200
From: Ali Baharev <[email protected]>
To: [email protected]
Subject: [Haskell-beginners] Traversing generic trees
Message-ID:
<cap9qzdzw4ox2wvehuqazjgsaechxa1f1_at+cbg37tfhfgj...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
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
------------------------------
Message: 2
Date: Thu, 23 Jul 2015 00:14:50 +0200
From: Ali Baharev <[email protected]>
To: elliot <[email protected]>
Cc: [email protected]
Subject: Re: [Haskell-beginners] Traversing generic trees
Message-ID:
<CAP9qzdaZ8-AgFWniHOxoD_0ZdaY0OvcHqk=e_ulfs_rhodf...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
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 <[email protected]> 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: [email protected]
> p: +44 751 070 5158
> ---- Original Message ----
> From: "Ali Baharev"
> To: [email protected]
> 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
> [email protected] (mailto:[email protected])
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> (http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners)
------------------------------
Message: 3
Date: Thu, 23 Jul 2015 01:10:12 +0200
From: Imants Cekusins <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Traversing generic trees
Message-ID:
<CAP1qinYxcJDa8oF15EjbiCQ6SBerV6-1Jf=vdp1gqy8-ngb...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
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?
------------------------------
Message: 4
Date: Thu, 23 Jul 2015 01:26:41 +0200
From: Ali Baharev <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Traversing generic trees
Message-ID:
<cap9qzdyegamqjuy7gct1o7ccsmz_ya+mb903rnsyg3j2z8b...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
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 <[email protected]> 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
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
Message: 5
Date: Wed, 22 Jul 2015 22:52:50 -0400
From: Joel Williamson <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Traversing generic trees
Message-ID:
<CAJGxSepFoUQVP=mnyy-oiycrba1z1+nnujxn2ttczvg-id0...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <[email protected]> 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 <[email protected]> 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
> > [email protected]
> > http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
> _______________________________________________
> Beginners mailing list
> [email protected]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20150722/d4db69c9/attachment-0001.html>
------------------------------
Message: 6
Date: Thu, 23 Jul 2015 16:05:12 +1000
From: Thomas Koster <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Traversing generic trees
Message-ID:
<cag1wh7abp8xhnrshdpxmre1jjsqb4dgej4e_ck2k8zk+qf6...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
Hi Ali,
On 23 July 2015 at 07:24, Ali Baharev <[email protected]> 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 <[email protected]> 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
------------------------------
Message: 7
Date: Thu, 23 Jul 2015 09:41:33 +0200
From: Imants Cekusins <[email protected]>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <[email protected]>
Subject: Re: [Haskell-beginners] Traversing generic trees
Message-ID:
<cap1qinaogtlum8e8hfz1fm_t6xieymdw9zc3iswzpxugoaj...@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8
.. 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.
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 85, Issue 14
*****************************************
