[Haskell-beginners] Traversing generic trees

[Thomas Koster]

Hi Ali,

On 23 July 2015 at 07:24, Ali Baharev <ali.baharev at 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 at 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