## Three List Exercises

### May 7, 2013

The first exercise removes every *n*th 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*(*n*^{2}) 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

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

My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/07/programming-praxis-three-list-exercises/ for a version with comments):

[…] Question is from here. […]

My java solution here.

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[0].push(i) : both_lists[1].push(i) }

both_lists

end

#!/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]))