Re: [Haskell-cafe] tree insert and laziness

I think the most relevant part to efficiency is that trees are *persistent*, not necessarily laziness. After all, OCaml and Clojure, among others, manage immutable structures like this reasonably quickly themselves. Since the tree is immutable and made up of pointers internally, we can reuse every part that we don't modify. As a simpler example, consider a list: to "add" a new element, we don't copy the whole list; instead, we create a new node with a pointer to the old list. Since everything is immutable, this is completely safe. Trees are a bit more complicated, but the same idea remains: we only modify as little of the tree as we need, reusing everything else. Wikipedia has a great article[1] on persistence. I found the diagrams especially useful, like this illustration of what a modified persistent tree looks like[2]. [1]: http://en.wikipedia.org/wiki/Persistent_data_structure [2]: http://en.wikipedia.org/wiki/Persistent_data_structure#mediaviewer/File:Pure... On Sun, Aug 17, 2014 at 3:09 AM, Semen Trygubenko / Семен Тригубенко < semen@trygub.com> wrote:

Hi Nicola,

On Sun, Aug 17, 2014 at 09:52:27AM +0200, Nicola Gigante wrote:

...

Il giorno 16/ago/2014, alle ore 23:05, Semen Trygubenko / Семен

Тригубенко ha scritto:

...

...

Dear Haskell-Cafe,

I'm presently reviewing a translation of the following paragraph (taken from LUaH, chapter 8):

http://learnyouahaskell.com/making-our-own-types-and-typeclasses

"In languages like C, we'd do this by modifying the pointers and values inside the tree. In Haskell, we can't really modify our

...

...

so we have to make a new sub-tree each time we decide to go left or right and in the end the insertion function returns a completely new tree, because Haskell doesn't really have a concept of pointer, just values. Hence, the type for our insertion function is going to be something like a -> Tree a - > Tree a. It takes an element and a

tree, tree

...

...

and returns a new tree that has that element inside. This might seem like it's inefficient but laziness takes care of that problem."

I was wondering if it is really the laziness that makes this approach efficient? If it isn't, what did the author want to say in the last sentence?

I think he wants to say that, unlike what would happen in a strict language, the function is not going to really copy the entire tree only to insert a new value, because the evaluation of the function is lazy, thus it will evaluate only some nodes of the new trees, only when needed.

It is somewhat misleading, I agree, because actually we should also take into consideration the fact that unmodified nodes gets shared between the two trees so we're really copying only the nodes along the path from the root to the inserted node.

Given the context (the paragraph above, minus the final sentence) I suspect the author wants to say that the approach that involves creation of "a whole new tree" might seem inefficient (e.g., for someone coming from the imperative school), but in actuality it isn't, because of the way functional data structures are implemented — since they are immutable (and there is sharing going on under the hood) this operation is actually a cheap one. I just wanted to confirm this with Haskell-Cafe (the response of Daniel Trstenjak)…

Thanks for your help, S.

...

Aside, are you translating it in Russian? Is it as a job, or there's a community effort of translation of that book in other languages?

PS I am reviewing a Ukrainian translation, not as a job.

-- Семен Тригубенко http://trygub.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe