Ropes - Haskell-Cafe - Haskell.org

newer
RE: readFile and closing a file

Ropes

older
Munging wiki articles with tagsoup

Rafael Gustavo da Cunha Pereira Pinto

19 Sep 2008 19 Sep '08

8:50 p.m.

Hi all, Is there any implementation of the rope data structure in Haskell? I couldn't find any on Hackage, and I am intending to implement it. Regards, Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

Attachments:

attachment.html (text/html — 343 bytes)

Reply

Sign in to reply online Use email software

Show replies by date

Ryan Ingram

19 Sep 19 Sep

10:15 p.m.

I think Data.Sequence uses fingertrees which are pretty fast. I used a handgrown rope-like structure for ICFPC07 but I wish I had known about Sequence; it would have likely just been better. -- ryan 2008/9/19 Rafael Gustavo da Cunha Pereira Pinto :

Hi all,

Is there any implementation of the rope data structure in Haskell?

I couldn't find any on Hackage, and I am intending to implement it.

Regards,

Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

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

Reply

Sign in to reply online Use email software

Rafael Gustavo da Cunha Pereira Pinto

20 Sep 20 Sep

6:54 a.m.

I am doing the ICFPC07 task right now, to learn Haskell and tried to use the Sequence, but the final code is too damn slow (a few iterations per minute!). The DNA needs only 2 operations: head (or take) and concat. I am thinking in using ropes for the DNA and sequences for all the rest (patterns, templates and RNA). On Fri, Sep 19, 2008 at 23:15, Ryan Ingram wrote:

I think Data.Sequence uses fingertrees which are pretty fast.

I used a handgrown rope-like structure for ICFPC07 but I wish I had known about Sequence; it would have likely just been better.

-- ryan

2008/9/19 Rafael Gustavo da Cunha Pereira Pinto < RafaelGCPP.Linux@gmail.com>:

...
Hi all,

Is there any implementation of the rope data structure in Haskell?

I couldn't find any on Hackage, and I am intending to implement it.

Regards,

Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

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

-- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

Reply

Sign in to reply online Use email software

apfelmus

7:38 a.m.

Rafael Gustavo da Cunha Pereira Pinto wrote:

I am doing the ICFPC07 task right now, to learn Haskell and tried to use the Sequence, but the final code is too damn slow (a few iterations per minute!).

The DNA needs only 2 operations: head (or take) and concat.

I am thinking in using ropes for the DNA and sequences for all the rest (patterns, templates and RNA).

I have been told that you could pretty much literally implement the algorithms from the problem specification with Seq from Data.Sequence and achieve acceptable speed (IIRC ~ one minute for generating a whole picture). Are you sure that there is no unintentional bug in your implementation that slows things down? Regards, apfelmus

Reply

Sign in to reply online Use email software

Nicolas Pouillard

21 Sep 21 Sep

10:10 a.m.

Excerpts from Rafael Gustavo da Cunha Pereira Pinto's message of Sat Sep 20 12:54:26 +0200 2008:

I am doing the ICFPC07 task right now, to learn Haskell and tried to use the Sequence, but the final code is too damn slow (a few iterations per minute!).

Is your structure a sequence of *Char*s, if so you should consider to use a sequence of strict bytestrings of a given size (chunks).

The DNA needs only 2 operations: head (or take) and concat.

I am thinking in using ropes for the DNA and sequences for all the rest (patterns, templates and RNA).

On Fri, Sep 19, 2008 at 23:15, Ryan Ingram wrote:

...
I think Data.Sequence uses fingertrees which are pretty fast.

I used a handgrown rope-like structure for ICFPC07 but I wish I had known about Sequence; it would have likely just been better.

-- ryan

2008/9/19 Rafael Gustavo da Cunha Pereira Pinto < RafaelGCPP.Linux@gmail.com>:

...
Hi all,

Is there any implementation of the rope data structure in Haskell?

I couldn't find any on Hackage, and I am intending to implement it.

Regards,

Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

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

-- Nicolas Pouillard aka Ertai

Reply

Sign in to reply online Use email software

Rafael Gustavo da Cunha Pereira Pinto

22 Sep 22 Sep

11:54 a.m.

That is a good idea! If I implement head, tail, take drop operations, I can use my KMP implementation out of the box... On Sun, Sep 21, 2008 at 11:10, Nicolas Pouillard < nicolas.pouillard@gmail.com> wrote:

...
I am doing the ICFPC07 task right now, to learn Haskell and tried to use

Excerpts from Rafael Gustavo da Cunha Pereira Pinto's message of Sat Sep 20 12:54:26 +0200 2008: the

...
Sequence, but the final code is too damn slow (a few iterations per minute!).

Is your structure a sequence of *Char*s, if so you should consider to use a sequence of strict bytestrings of a given size (chunks).

...
The DNA needs only 2 operations: head (or take) and concat.

I am thinking in using ropes for the DNA and sequences for all the rest (patterns, templates and RNA).

On Fri, Sep 19, 2008 at 23:15, Ryan Ingram wrote:

...
I think Data.Sequence uses fingertrees which are pretty fast.

I used a handgrown rope-like structure for ICFPC07 but I wish I had known about Sequence; it would have likely just been better.

-- ryan

2008/9/19 Rafael Gustavo da Cunha Pereira Pinto < RafaelGCPP.Linux@gmail.com>:

...
Hi all,

Is there any implementation of the rope data structure in Haskell?

I couldn't find any on Hackage, and I am intending to implement it.

Regards,

Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

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

-- Nicolas Pouillard aka Ertai

-- Rafael Gustavo da Cunha Pereira Pinto Electronic Engineer, MSc.

Reply

Sign in to reply online Use email software

Don Stewart

19 Sep 19 Sep

10:18 p.m.

RafaelGCPP.Linux:

Hi all,

Is there any implementation of the rope data structure in Haskell?

I couldn't find any on Hackage, and I am intending to implement it.

There's no mature rope implementation. Can you write a bytestring-rope that outperforms lazy bytestrings please :)

Reply

Sign in to reply online Use email software

6102

Age (days ago)

6104

Last active (days ago)

Download

6 comments

5 participants

tags

participants (5)

apfelmus
Don Stewart
Nicolas Pouillard
Rafael Gustavo da Cunha Pereira Pinto
Ryan Ingram