Next To Last Item In A List
July 28, 2015
We begin with the function that gets the next-to-last item in a list; we return #f if the list is too small, but depending on your application you may want to raise an error instead:
(define (next-to-last xs)
(cond ((or (null? xs) (null? (cdr xs))) #f)
((null? (cddr xs)) (car xs))
(else (next-to-last (cdr xs)))))
We have three test cases: list with no items, list with one item, and list with more items:
(define (test-next-to-last)
(assert (next-to-last '()) #f)
(assert (next-to-last '(1)) #f)
(assert (next-to-last '(1 2)) 1)
(assert (next-to-last '(1 2 3)) 2)
(assert (next-to-last '(1 2 3 4)) 3)
(assert (next-to-last '(1 2 3 4 5)) 4))
As always, no news is good news:
> (test-next-to-last)
The nth-to-last function is a little bit harder. First we run through n items, reporting an error if there aren’t enough. Then we keep two pointers n items apart, reporting the item at the trailing pointer when the leading pointer reaches the end of the list:
(define (nth-to-last n xs)
(if (not (positive? n)) #f
(let loop ((n n) (leading xs))
(if (null? leading) #f
(if (< 1 n) (loop (- n 1) (cdr leading))
(let loop ((trailing xs) (leading (cdr leading)))
(if (null? leading) (car trailing)
(loop (cdr trailing) (cdr leading)))))))))
Testing is a little bit harder; because we want to test lots of combinations of n and xs, we have to have a way to generate them with known results:
(define (test-nth-to-last)
(assert (nth-to-last 0 '()) #f)
(assert (nth-to-last 0 '(1)) #f)
(do ((n 1 (+ n 1))) ((= n 7))
(do ((x 1 (+ x 1))) ((= x 7))
(let ((r (if (< x n) #f (- x n -1))))
(assert (nth-to-last n (range 1 (+ x 1))) r)))))
Notice that we had to test the case n = 0 separately, because the calculation of r in (- x n -1) does the wrong thing. As before, no news is good news:
> (test-nth-to-last)
We used assert and range from the Standard Prelude. You can run the program at http://ideone.com/3HbSOt.
In Python. I assumed that n cannot exceed the length of the list. I did use a list for the linked list, but did not use len and slicing.
For testing I use the hopthesis library.
from hypothesis import given, Settings, Verbosity import hypothesis.strategies as st from itertools import tee, islice def slidingwindow(iterable, n=2): """example: [1,2,3,4,5],3) -> (1,2,3), (2,3,4), (3,4,5)""" its = tee(iter(iterable), n) for i, it in enumerate(its): next(islice(it, i, i), None) return zip(*its) def bf(seq, n): """for testing assumption is that n cannot exceed the length of the sequence """ if len(seq) < n: return None return seq[-n] # use list as linked list - you cannot use seq[-2] and len def next_to_last_n(seq, n): a = None # slidingwindow(s,2) returns (s1,s2), (s2,s3), ....., (s_n-1, s_n) for a, *b in slidingwindow(seq, n): pass return a def next_to_last(seq): return next_to_last_n(seq, 2) # generate random lists of integers with random lengths, and generate a random n @given(st.lists(st.integers(), average_size=20), st.integers(min_value=1, max_value=20), settings=Settings(verbosity=Verbosity.normal)) def test_next_to_last_n(seq, n): exp = bf(seq, n) act = next_to_last_n(seq, n) assert act == exp, "{} {} {}".format(act, exp, seq[-4:]) @given(st.lists(st.integers())) def test_next_to_last(seq): exp = bf(seq, 2) act = next_to_last(seq) assert act == exp, "{} {} {}".format(act, exp, seq[-4:]) if __name__ == "__main__": test_next_to_last() test_next_to_last_n() print("OK")In Python. A simpler version.
from collections import deque def next_to_last_n(seq, n): d = deque(seq, n) # d contains the last n values of seq return d[0] if len(d) == n else NoneWith Lisp-style lists in Python, and a verbose option in the test function for checking that no news is any news at all.
Backwards indexing has always been tricky for me, including this time. Oh, and I let Python raise an exception when the list is too short, and then I test for that.
from functools import reduce def nest(flat): return reduce((lambda rest, elt: (elt, rest)), reversed(flat), ()) def tail(nested, n = 1): '''Tail starting at index n.''' for k in range(n): _, nested = nested return nested def nthtolast(nested, n = 0): '''Head of the tail of length n + 2.''' slow, fast = nested, tail(nested, n + 2) while fast: _, slow = slow _, fast = fast elt, _ = slow return elt def test(n, verbose = False): for data in ('abcdef'[:e] for e in range(7)): if n + 1 < len(data): x = nthtolast(nest(data), n) assert x == data[-2-n] ( verbose and print('nthtolast(({}), n = {}) => {}' .format(' '.join(data), n, x)) ) else: try: nthtolast(nest(data), n) assert False except ValueError: ( verbose and print('nthtolast(({}), n = {}) => ValueError' .format(' '.join(data), n)) ) test(0) test(1) test(2)A solution in (Racket) Scheme.
nfl0 is the inefficient but clear functional specification, nfl is the implementation (using the double pointer approach). Both assume n is non-negative.
Test just compares the two functions over a suitable set of inputs.
nfl0 n s | n >= length s = Nothing | otherwise = Just (s !! (length s - n - 1)) f 0 s t = g s t f n s (_:t) = f (n-1) s t f _ _ _ = Nothing g (a:_) [] = Just a g (_:s) (_:t) = g s t nfl n s = f (n+1) s s test0 m n = nfl n [1..m] == nfl0 n [1..m] test1 m = all (test0 m) [0..m+1] test = all test1 [0..5] main = print testfun next_to_last_item [] = ~1 (* return -1 on error *) | next_to_last_item (x::y::nil) = x | next_to_last_item (x::xs) = next_to_last_item xs val test_valid_list = (next_to_last_item [1, 2, 3, 4, 5]) = 4 val test_empty_list = (next_to_last_item []) = ~1 val test_single_elem_list = (next_to_last_item [1]) = ~1 fun nth_from_last_item n [] = ~1 | nth_from_last_item n lst = let val len = List.length lst fun loop counter [] = ~1 (* counter goes past end of list *) | loop counter (x::xs) = if len - counter = n then x else loop (counter + 1) xs in loop 0 lst end val test_1st_from_last = (nth_from_last_item 1 [1, 2, 3, 4, 5]) = 5 val test_2nd_from_last = (nth_from_last_item 2 [1, 2, 3, 4, 5]) = 4 (* rewriting next_to_last_item using nth_from_last_item *) fun next_to_last_item2 xs = nth_from_last_item 2 xs; val test_valid_list2 = (next_to_last_item2 [1, 2, 3, 4, 5]) = 4 val test_empty_list2 = (next_to_last_item2 []) = ~1 val test_single_elem_list2 = (next_to_last_item2 [1]) = ~1 val all_test_pass = List.all (fn x => x) [test_valid_list, test_empty_list, test_single_elem_list, test_1st_from_last, test_2nd_from_last, test_valid_list2, test_empty_list2, test_single_elem_list2];