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.

About these ads

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. [...]

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

    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. javabloggi said

    My java solution here.

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

  6. 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
    
  7. 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]))

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: