List operation question

Eric Olander

4 Feb 2007 4 Feb '07

1:44 p.m.

Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially shiftl:

...

...
moves the first element to the end of the list shiftr :: [a] -> [a] shiftr [] = [] shiftr (x:y) = y ++ [x]

...

...
moves the last element to the head of the list shiftl :: [a] -> [a] shiftl [] = [] shiftl x = [last x] ++ init x

-Eric

Attachments:

attachment.html (text/html — 595 bytes)

Show replies by date

Not much better. You could define shiftl such that is does a single traversal and returns both the last element and all but the last. That will save you one traversal. On Feb 4, 2007, at 18:44 , Eric Olander wrote:

...

Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially shiftl:

...
...
moves the first element to the end of the list shiftr :: [a] -> [a] shiftr [] = [] shiftr (x:y) = y ++ [x]

...
...
moves the last element to the head of the list shiftl :: [a] -> [a] shiftl [] = [] shiftl x = [last x] ++ init x

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

Nicolas Frisby

2:24 p.m.

I've always thought that when certain operations are of particular interest, it's time to use more appropriate data structures, right? Lists are great and simple and intuitive, but if you need such operations as shifts, something like a deque is the way to go. I'm not a data structure pro, but I'm sure someone on this list could post a neat example. Or you could look for work by Osaki - he seems to be the reference for functional data structures. "Finger trees" and "tries" also get a lot of attention around here. Enjoy. On 2/4/07, Lennart Augustsson wrote:

...

Not much better. You could define shiftl such that is does a single traversal and returns both the last element and all but the last. That will save you one traversal.

On Feb 4, 2007, at 18:44 , Eric Olander wrote:

...
Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially shiftl:

...
...
moves the first element to the end of the list shiftr :: [a] -> [a] shiftr [] = [] shiftr (x:y) = y ++ [x]

...
...
moves the last element to the head of the list shiftl :: [a] -> [a] shiftl [] = [] shiftl x = [last x] ++ init x

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

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

Yitzchak Gale

2:27 p.m.

Nicolas Frisby wrote:

...

I've always thought that when certain operations are of particular interest, it's time to use more appropriate data structures, right? Lists are great and simple and intuitive, but if you need such operations as shifts, something like a deque is the way to go.

This sounds like a job for Data.Sequence. -Yitz

Lennart Augustsson

2:39 p.m.

I agree. If performance is important enough to worry about is shiftl traverses the list once or twice then it's time to switch to a better data type. On Feb 4, 2007, at 19:27 , Yitzchak Gale wrote:

...

Nicolas Frisby wrote:

...
I've always thought that when certain operations are of particular interest, it's time to use more appropriate data structures, right? Lists are great and simple and intuitive, but if you need such operations as shifts, something like a deque is the way to go.

This sounds like a job for Data.Sequence.

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

Robert Dockins

5 Feb 5 Feb

3:08 p.m.

On Sunday 04 February 2007 14:24, Nicolas Frisby wrote:

...

I've always thought that when certain operations are of particular interest, it's time to use more appropriate data structures, right? Lists are great and simple and intuitive, but if you need such operations as shifts, something like a deque is the way to go.

I'm not a data structure pro, but I'm sure someone on this list could post a neat example. Or you could look for work by Osaki - he seems to be the reference for functional data structures. "Finger trees" and "tries" also get a lot of attention around here.

Also, take a look at Edison. It has a variety of sequence implementations with different properties. Several of them have efficient access to both ends of the sequence. http://www.eecs.tufts.edu/~rdocki01/edison.html

...

Enjoy.

On 2/4/07, Lennart Augustsson wrote:

...
Not much better. You could define shiftl such that is does a single traversal and returns both the last element and all but the last. That will save you one traversal.

On Feb 4, 2007, at 18:44 , Eric Olander wrote:

...
Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially

shiftl:

...
...
moves the first element to the end of the list

shiftr :: [a] -> [a] shiftr [] = [] shiftr (x:y) = y ++ [x]

...
...
moves the last element to the head of the list

shiftl :: [a] -> [a] shiftl [] = [] shiftl x = [last x] ++ init x

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

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

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

Bryan Donlan

4 Feb 4 Feb

2:51 p.m.

Eric Olander wrote:

...

Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially shiftl:

...
...
moves the first element to the end of the list shiftr :: [a] -> [a] shiftr [] = [] shiftr (x:y) = y ++ [x]

...
...
moves the last element to the head of the list shiftl :: [a] -> [a] shiftl [] = [] shiftl x = [last x] ++ init x

If you use Data.Sequence (new in 6.6, I think), these can be O(1): import qualified Data.Sequence as Seq import Data.Sequence ( (<|), (|>), (:<), (:>) ) shiftr seq = go (Seq.viewl seq) where go (EmptyL) = Seq.empty go (e :< remain) = remain |> e shiftl seq = go (Seq.viewr seq) where go (EmptyR) = Seq.empty go (remain :> e) = e <| remain Decomposing by elements like this is a bit unwieldy, but using the functions in Data.Traversable and Data.Foldable it shouldn't be too bad, depending on what you're doing.

ihope

5 Feb 5 Feb

5:21 p.m.

On 2/4/07, Eric Olander wrote:

...

Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially shiftl:

...
...
moves the last element to the head of the list shiftl :: [a] -> [a] shiftl [] = [] shiftl x = [last x] ++ init x

Well, you could try this, though I'm actually sure it's any faster:

...

shiftl (x1:x2:xs) = last:x1:init where last:init = shiftl (x2:xs) shiftl [x] = [x] shiftl [] = error "shiftl: empty list"

Or, if you don't want to give an error on [], omit the last line and replace both of the [x] with xs.

Eric Olander

6 Feb 6 Feb

12:40 a.m.

That's a clever routine. It should be faster than mine since it only makes a single pass though the list. Thanks for all the suggestions from everyone that responded. Here is a link to some more info on the project I'm working on if anyone is interested: http://ehaskell.blogspot.com/ -Eric On 2/5/07, ihope wrote:

...

On 2/4/07, Eric Olander wrote:

...
Hi, I'm still somewhat new to Haskell, so I'm wondering if there are better ways I could implement the following functions, especially shiftl:

...
...
moves the last element to the head of the list shiftl :: [a] -> [a] shiftl [] = [] shiftl x = [last x] ++ init x

Well, you could try this, though I'm actually sure it's any faster:

...
shiftl (x1:x2:xs) = last:x1:init where last:init = shiftl (x2:xs) shiftl [x] = [x] shiftl [] = error "shiftl: empty list"

Or, if you don't want to give an error on [], omit the last line and replace both of the [x] with xs. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

6679

Age (days ago)

6681

Last active (days ago)

List overview

Download

8 comments

7 participants

participants (7)

Bryan Donlan
Eric Olander
ihope
Lennart Augustsson
Nicolas Frisby
Robert Dockins
Yitzchak Gale