[Haskell-cafe] tree insert and laziness

[Semen Trygubenko / Семен Тригубенко]

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 / Семен Тригубенко <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."
> > 
> > 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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 196 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140817/925059f9/attachment.sig>