## Three List Exercises

### May 7, 2013

The first exercise removes every nth item from a list. We count using variable i and accumulate the result in variable zs in reverse order. A three-legged `cond` returns when the input is empty, loops without copying at each n item, or loops with copying otherwise:

```(define (remove-nth n xs)   (let loop ((i 1) (xs xs) (zs (list)))     (cond ((null? xs) (reverse zs))           ((= i n) (loop 1 (cdr xs) zs))           (else (loop (+ i 1) (cdr xs) (cons (car xs) zs))))))```

Here’s an example:

```> (remove-nth 4 '(1 2 3 4 5 6 7 8 9 10) (1 2 3 5 6 7 9 10)```

This function has time complexity linear in the length of the list.

The second exercise removes duplicate items from a list; it has the same three-legged `cond` as the first exercise, but the predicate in the second leg checks if the current list element is already in the output, in which case it is ignored.

```(define (remove-dups xs)   (let loop ((xs xs) (zs (list)))     (cond ((null? xs) (reverse zs))           ((member (car xs) zs) (loop (cdr xs) zs))           (else (loop (cdr xs) (cons (car xs) zs))))))```

Here are some examples:

```> (remove-dups '(1 2 3 4 5)) (1 2 3 4 5) > (remove-dups '(1 1 2 3 4 5)) (1 2 3 4 5) > (remove-dups '(1 2 3 4 5 5)) (1 2 3 4 5) > (remove-dups '(1 2 1 3 1 4 1 5 1)) (1 2 3 4 5) > (remove-dups '(1 2 2 3 3 3 4 4 4 4 5 5 5 5 5)) (1 2 3 4 5)```

We stored the already-seen items in the output list, giving the `remove-dups` function an O(n2) time complexity; that could be reduced to O(n log n) by using some kind of balanced tree to store the set of already-seen items, or even to O(n) by using a hash table (assuming a good hash function), but that’s more work than we want to do here.

The third function splits a list into two halves using the tortoise-and-hare algorithm from computing folklore; the hare pointer races through the list twice as fast as the tortoise pointer, reaching the end of the list when the tortoise reaches the middle.

```(define (split xs)   (let loop ((tortoise xs) (hare xs) (head (list)))     (if (or (null? hare) (null? (cdr hare)))         (values (reverse head) tortoise)         (loop (cdr tortoise) (cddr hare) (cons (car tortoise) head))))) ```
Here are some examples:

```> (split '(1 2 3 4 5 6)) (1 2 3) (4 5 6) > (split '(1 2 3 4 5 6 7)) (1 2 3) (4 5 6 7)```

This function runs in linear time.

Our bonus exercise is to write a function that returns a range of integers: `(range n)` returns a list of integers from 0 to n, excluding n, `(range first past)` returns a list of integers from first to past, excluding past, and `(range first past step)` returns a list of integers from first to past in steps of size step, excluding past. The range is written in ascending order unless past is less than first, in which case the range is written in descending order.

The tricky part of this exercise is making sure to handle all of the arguments properly; that’s easy if your Scheme provides `case-lambda`, and ugly if it doesn’t:

```(define range   (case-lambda     ((past) (range 0 past (if (positive? past) 1 -1)))     ((first past) (range first past (if (< first past) 1 -1)))     ((first past step)       (let ((le? (if (positive? step) =)))         (let loop ((x first) (xs (list)))           (if (le? past x)             (reverse xs)             (loop (+ x step) (cons x xs))))))     (else (error 'range "invalid arguments"))))```

The first two cases simply call `range` recursively with three arguments. The work in done in the third case, which defines a stopping condition `le?` less-than-or-equal based on the sign of the step argument. Here are some examples:

```> (range 7) (0 1 2 3 4 5 6) > (range -3) (0 -1 -2) > (range 7 0) (7 6 5 4 3 2 1) > (range 11 0 -2) (11 9 7 5 3 1)```

The run-time complexity is linear in the size of the output list.

You can run the program at http://programmingpraxis.codepad.org/TiCFpjxN, where you can see a version of `range` that doesn’t rely on `case-lambda`. There are many other examples of list utilities in the Standard Prelude.

Pages: 1 2

### 8 Responses to “Three List Exercises”

1. […] today’s Programming Praxis exercise, we need to implement three functions that work on linked lists. […]

```deleteNth :: Int -> [a] -> [a]
deleteNth _ [] = []
deleteNth n xs = take (n - 1) xs ++ deleteNth n (drop n xs)

nub :: Eq a => [a] -> [a]
nub = foldl (\a x -> if elem x a then a else a ++ [x]) []

half :: [a] -> ([a], [a])
half xs = splitAt (div (length xs) 2) xs
```
3. […] Question is from here. […]

4. javabloggi said

My java solution here.

5. eupraxia said
```skip_every_nth = lambda lst, n: [x for i, x in enumerate(lst, 1) if i%n!=0]
#
ordered_set = lambda lst: [lst[lst.index(x)] for x in set(lst)]
#
halfish_split = lambda lst: [(lst[:n], lst[n:]) for n in [int(len(lst)/2)]]
```
6. Dan said

def remove_nth_from_list(input, nth)
new_list = []
input.each { |i| new_list.push(i) unless i % nth == 0 }
new_list
end

def deduplicate(input)
new_list = input.uniq
end

def split_list(input)
both_lists = [[],[]]
half_point = input.size/2
input.each_with_index { |i, index| index < half_point ? both_lists.push(i) : both_lists.push(i) }
both_lists
end

7. ```def delete_nth(list, n)
list.each_index.select{|i| (i+1) % n != 0}.map{|i| list[i]}
end

def drop_dups(list)
list.each_index.select{|i| i == list.index(list[i])}.map{|i| list[i]}
end

def halve(list)
Array[list[0...(list.count / 2)], list[(list.count / 2)..-1]]
end
```
8. brice said

``` #!/usr/bin/env python```

``` def remove_ns(ls, n): return (v for i, v in enumerate(ls, 1) if i % n != 0) print("".join(remove_ns("abdefgh", 2))) def remove_dups(ls): seen = set() for i in ls: if not i in seen: seen.add(i) yield i print("".join(remove_dups("abbdssfgsha"))) def split(ls): return ls[:int(len(ls)/2)], ls[int(len(ls)/2):] print(split([1,2,3,4,5])) ```