CODEWITHSUNDEEP
listhaskell
TomTom
TomTom

Reputation: 2940

Reverse first k elements of a list

I'd like to reverse the first k elements of a list efficiently.

This is what I came up with:

reverseFirst :: Int -> [a] -> [a] -> [a]
reverseFirst 0 xs rev     = rev ++ xs
reverseFirst k (x:xs) rev = reverseFirst (k-1) xs (x:rev)

reversed = reverseFirst 3 [1..5] mempty -- Result: [3,2,1,4,5]

It is fairly nice, but the (++) bothers me. Or should I maybe consider using another data structure? I want to do this many million times with short lists.

Upvotes: 2

Views: 176

Answers (2)

dfeuer
dfeuer

Reputation: 48631

Let's think about the usual structure of reverse:

reverse = rev [] where
  rev acc [] = acc
  rev acc (x : xs) = rev (x : acc) xs

It starts with the empty list and tacks on elements from the front of the argument list till it's done. We want to do something similar, except we want to tack the elements onto the front of the portion of the list that we don't reverse. How can we do that when we don't have that un-reversed portion yet?

The simplest way I can think of to avoid traversing the front of the list twice is to use laziness:

reverseFirst :: Int -> [a] -> [a]
reverseFirst k xs = dis where
  (dis, dat) = rf dat k xs

  rf acc 0 ys = (acc, ys)
  rf acc n [] = (acc, [])
  rf acc n (y : ys) = rf (y : acc) (n - 1) ys

dat represents the portion of the list that is left alone. We calculate it in the same helper function rf that does the reversing, but we also pass it to rf in the initial call. It's never actually examined in rf, so everything just works. Looking at the generated core (using ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures) suggests that the pairs are compiled away into unlifted pairs and the Ints are unboxed, so everything should probably be quite efficient.

Profiling suggests that this implementation is about 1.3 times as fast as the difference list one, and allocates about 65% as much memory.

Upvotes: 5

leftaroundabout
leftaroundabout

Reputation: 120751

Well, usually I'd just write splitAt 3 >>> first reverse >>> uncurry(++) to achieve the goal.

If you're anxious about performance, you can consider a difference list:

reverseFirstN :: Int -> [a] -> [a]
reverseFirstN = go id
 where go rev 0 xs = rev xs
       go rev k (x:xs) = go ((x:).rev) (k-1) xs

but frankly I wouldn't expect this to be a lot faster: you need to traverse the first n elements either way. Actual performance will depend a lot on what the compiler is able to fuse away.

Upvotes: 2

Related Questions