[Haskell-cafe] Ultra-newbie Question

[Daniel Fischer]

On Saturday 18 September 2010 19:44:38, Jake McArthur wrote:
> On 09/18/2010 02:51 AM, Christopher Tauss wrote:
> > I am trying to write a function that takes a list and returns the last
> > n elements.
>
> This may just be for the sake of learning, in which case this is fine,
> but usually, needing to do this would be a sign that you are using lists
> improperly (since this is a O(n) time operation).
>

By which he meant O(length list), not the number of elements you're asking 
for.

> > Let's call the function n_lastn and, given a list  [1,2,3,4,5], I
> > would like
> > n_lastn 3 = [3,4,5]
>
>      n_lastn n = reverse . take n . reverse

Which is the most elegant definition, but it's an O(length list) space 
operation (as are all others proposed so far). That will be a problem for 
long lists (consider n_lastn 10 [1 .. 10^8]). You can implement it as an 
O(n) [the number of elements you want] *space* operation, provided that the 
list is generated lazily and not referred to by anything else, but the code 
is decidedly less nice:

The first idea would be to keep a window of n elements and move it to the 
end of the list:

n_lastn n xs =
    case splitAt n xs of
      (ys,[]) -> ys   -- the list contains at most n elements, yay
      (ys,zs) -> loop ys zs
    where
      loop window [] = window
      loop window (v:vs) = loop (tail window ++ [v]) vs

The space behaviour is now fine (if compiled with optimisations), but 
unfortunately, the time complexity has become O(n*length list) because the 
(++)-calls are left-nested:

Suppose n = 4,

loop (1:2:3:4:[]) [5 .. end]
~> loop ((2:3:4:[]) ++ [5]) [6 .. end]
~> loop (2:((3:4:[]) ++ [5])) [6 .. end]
~> loop (((3:4:[]) ++ [5]) ++ [6]) [7 .. end]

The strictness analyser has been smart enough to transform the call to tail 
into a strict pattern match on window, as if we'd written
   loop (_:twindow) (v:vs) = loop (twindow ++ [v]) vs
so the first few tails go fast, but later, we have to go through more 
layers to get at the head of the window to discard it

~> loop ((3:((4:[]) ++ [5])) ++ [6]) [7 .. end]
~> loop (3:(((4:[]) ++ [5]) ++ [6])) [7 .. end]
-- finally!
~> loop ((((4:[]) ++ [5]) ++ [6]) ++ [7]) [8 .. end]
-- bubble the 4 through four layers of parentheses:
~> loop(((4:([] ++ [5])) ++ [6]) ++ [7]) [8 .. end]
~> loop ((4:(([] ++ [5]) ++ [6])) ++ [7]) [8 .. end]
~> loop (4:((([] ++ [5]) ++ [6]) ++ [7])) [8 .. end]
~> loop (((([] ++ [5]) ++ [6]) ++ [7]) ++ [8]) [9 .. end]
-- phew
-- form now on, it's uniform, on each step we have to match an expression

(((([] ++ [a]) ++ [b]) ++ [c]) ++ [d])

against (_:rest)
1. check whether ((([] ++ [a]) ++ [b]) ++ [c]) is empty, for that,
2. check whether (([] ++ [a]) ++ [b]) is empty, for that,
3. check whether ([] ++ [a]) is empty, for that,
4. check whether [] is empty, it is, hence [] ++ [a] = [a],
5. check whether [a] is empty, it's not, it's (a:[]), hence
6. (...) ++ [b] = a:([] ++ [b]), so 2's not empty, and
7. (...) ++ [c] = a:(([] ++ [b]) ++ [c]), so 1's not empty and
8. (...) ++ [d] = a:((([] ++ [b]) ++ [c]) ++ [d])
9. at last, a can be dropped and we get to 
   loop (((([] ++ [b]) ++ [c]) ++ [d]) ++ [e]) remainingList

Blech!

Appending to the end of a list is bad if it leads to left-nested 
parentheses (it's okay if the parentheses are right-nested).
So we might be tempted to keep the window reversed and cons each element to 
the front, dropping the last. No good, removing an element from the end is 
O(length window) too.

One possibility to fix it is to use a 'list-like' type with O(1) appending 
at the end and dropping from the front.
Data.Sequence is such a type,

import qualified Data.Sequence as Seq
import Data.Foldable (toList)
import Data.Sequence (ViewL(..), (|>))

n_lastn' :: Int -> [a] -> [a]
n_lastn' k _
    | k <= 0    = []
n_lastn' k xs =
    case splitAt k xs of
      (ys,[]) -> ys
      (ys,zs) -> go (Seq.fromList ys) zs
    where
      go acc [] = toList acc
      go acc (v:vs) = case Seq.viewl acc of
                        _ :< keep -> go (keep |> v) vs
                        _ -> error "teh impossible jus hapnd"

fixes space and time behaviour. But the constant factors for Sequence are 
larger than those for lists, so we can beat it with lists:


n_lastn :: Int -> [a] -> [a]
n_lastn k _
    | k <= 0  = []
n_lastn k xs =
    case splitAt k xs of
      (ys,[]) -> ys
      (ys,zs) -> go k (reverse ys) zs
    where
      m = k-1
      go _ acc [] = reverse $ take k acc
      go 0 acc (v:vs) = case splitAt m acc of
                          (keep,release) -> release `seq` go k (v:keep) vs
      go h acc (v:vs) = go (h-1) (v:acc) vs


Every k steps, we perform the O(k) operation of removing the last (k+1) 
elements from a (2k)-element list, making the removal from the end an 
amortized O(1) operation.
You can trade some space for speed and clip the window in larger intervals, 
say every (3*k) or every (10*k) steps.