[Haskell-cafe] tree insert and laziness

[Nicola Gigante]

Il giorno 16/ago/2014, alle ore 23:05, Semen Trygubenko / Семен Тригубенко <semen at trygub.com> 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 tree,
> 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
> and returns a new tree that has that element inside.
> This might seem like it's inefficient but laziness takes care of that
> problem."
> 
> 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.

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?

> Thank you,
> Semen

Bye,
Nicola