[Haskell-cafe] tree insert and laziness

[Tikhon Jelvis]

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:Purely_functional_tree_after.svg


On Sun, Aug 17, 2014 at 3:09 AM, Semen Trygubenko / Семен Тригубенко <
semen at 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 / Семен
> Тригубенко <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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140818/6a844306/attachment.html>