Reversing Parts Of A List
December 3, 2013
For the first exercise, we take the car and cadr of a list, as long as they are not null, write them in reverse order to a result list, and stop at the end, when we reverse the entire list:
(define (rev-2 xs)
(let loop ((xs xs) (zs (list)))
(cond ((null? xs) (reverse zs))
((null? (cdr xs)) (reverse (cons (car xs) zs)))
(else (loop (cddr xs) (cons (car xs) (cons (cadr xs) zs)))))))
> (rev-2 '(1 2 3 4 5 6))
(2 1 4 3 6 5)
> (rev-2 '(1 2 3 4 5))
(2 1 4 3 5)
For the second exercise, we make use of the auxiliary functions take and drop from the Standard Prelude to repeatedly collect k elements from the list, append them to a result list, and finally reverse the result; this works properly at the tail end of the list because both take and drop return less than k elements at the end of the list:
(define (rev-k k xs)
(let loop ((xs xs) (zs (list)))
(if (null? xs) (reverse zs)
(loop (drop k xs) (append (take k xs) zs)))))
> (rev-k 3 '(1 2 3 4 5 6))
(3 2 1 6 5 4)
> (rev-k 4 '(1 2 3 4 5 6))
(4 3 2 1 6 5)
The third exercise uses Raymond Floyd’s tortoise-and-hare algorithm to race two pointers through the list, one twice as fast as the other; when the hare gets to the end of the list, the tortoise points to the middle of the list. The elements of the first half of the list are collected as the tortoise walks the list; the result is assembled when the hare reaches the end:
(define (rev-half xs)
(let loop ((t xs) (h xs) (zs (list)))
(cond ((null? h) (append zs (reverse t)))
((null? (cdr h)) (append zs (reverse t)))
(else (loop (cdr t) (cddr h) (cons (car t) zs))))))
> (rev-half '(1 2 3 4 5 6))
(3 2 1 6 5 4)
> (rev-half '(1 2 3 4 5))
(2 1 5 4 3)
You can run the program at http://programmingpraxis.codepad.org/WGr77ExY.
Programming Praxis 
Haskell solutions. They’re written in rather different style.
In Python.
from itertools import izip_longest # FILL for izip_longest - make sure that None can be used in the array FILL = object() def inv_k(arr, k): """invert k items""" it = iter(arr) res = [] for p in izip_longest(*([it]*k), fillvalue=FILL): while p[-1] == FILL: p = p[:-1] res += reversed(p) return res def inv_pairs(arr): return inv_k(arr, 2) def inv_half(arr): return inv_k(arr, (len(arr) + 1) // 2)In guile scheme: http://community.schemewiki.org/?chunky%20list%20reversals
Pairwise reversal:
Would love to hear input on my method. Thanks.
package praxis; import java.util.LinkedList; public class Praxis { public static void main(String[] args) { LinkedList<Integer> seq = new LinkedList<Integer>(); seq.add(1); seq.add(2); seq.add(3); seq.add(4); seq.add(5); seq.add(6); seq.add(7); seq.add(8); seq.add(9); seq.add(10); seq.add(11); int k = 3; System.out.println(reversal(seq,2)); System.out.println(reversal(seq,k)); System.out.println(reversal(seq,seq.size()/2)); } public static LinkedList<Integer> reversal(LinkedList<Integer> a,int k) { LinkedList<Integer> rev = new LinkedList<Integer>(); for(int i=0;i<a.size();i=i+k){ int idx_sec = (i+k-1); for(int j=0;j<k;j++){ if(idx_sec < a.size()) { rev.add(i+j,a.get(idx_sec-j)); } else{ if(rev.size() != a.size()){ rev.add(i+j,a.get(a.size()-j-1)); } } } } return rev; } }