Scheme - processing a list of lists

Author

processing a list of lists

Chris

2005-02-10, 8:59 am

I'm fairly new to scheme, and was wondering if someone explain to me
how I can solve this problem I am working on. It asks you to go
through a list of lists and pull out all the elements, putting them
into a single list like such:
((a b c) (d e f) (g h i j)) -> (a b c d e f g h i j)

It asks that you use append with two arguments...
I wrote some code, but it doesn't work.

Do I need to pass in a variable in my recursive calls to hold the new
list?

Thanks!

Jussi Piitulainen

2005-02-10, 4:00 pm

Chris writes:

> I'm fairly new to scheme, and was wondering if someone explain to me
> how I can solve this problem I am working on. It asks you to go
> through a list of lists and pull out all the elements, putting them
> into a single list like such:
>
> ((a b c) (d e f) (g h i j)) -> (a b c d e f g h i j)
>
> It asks that you use append with two arguments...

So you can't just (apply append list-of-lists). Is this because your
list of lists might be very long? Or is it for no reason? How about

(if (null? list-of-lists)
(append '() '())
(if (null? (cdr list-of-lists))
(append (car list-of-lists) '())
(append (car list-of-lists)
(apply append (cdr list-of-lists)))))

where every branch does call append with two arguments?

> I wrote some code, but it doesn't work.

Try to see what your code does with some very simple input. Start with
(), then (()), then (() ()), then (() () ()). Always do this when in
doubt.

If you want help with your code, it helps to show your code.

> Do I need to pass in a variable in my recursive calls to hold the
> new list?

So you are using recursion. You don't pass variables to procedures.
You pass values. When you are being recursive, you pass a simpler
instance of the same problem. Consider passing a shorter list of
lists.

But this problem has a particular form: you fold the list of lists
from the right using append. Your Scheme implementation should have
some folding procedures in its library, or you can write one like so:

(define (fold-from-right f z xs)
(if (null? xs)
z
(f (car xs) (fold-from-right f z (cdr xs)))))

Then just (fold-from-right append '() lists-of-lists), and notice that
fold-from-right calls f only with two arguments, as required.

mhartl@post.harvard.edu

2005-02-10, 8:58 pm

I'm not sure what "It asks that you use append with two arguments..."
means. One way to write your function (which is a concatenation
operator) is to accumulate the result of appending each list to the
null list. Using dotted tail notation, we can define it as follows:

;(define (concatenate . lists)
; (accumulate append '() lists))

where accumulate is defined as (SICP 2.2.3)

;(define (accumulate op initial sequence)
; (if (null? sequence)
; initial
; (op (car sequence)
; (accumulate op initial (cdr sequence)))))

This might be too advanced for your purposes, but I think it's an
instructive solution to your problem.

Michael

David Van Horn

2005-02-11, 4:00 am

Chris wrote:
> I'm fairly new to scheme, and was wondering if someone explain to me
> how I can solve this problem I am working on. It asks you to go
> through a list of lists and pull out all the elements, putting them
> into a single list like such:
> ((a b c) (d e f) (g h i j)) -> (a b c d e f g h i j)

(define (apply-append ls-ls)
(letrec ((apply-append-s
(lambda (ls1 ls2)
(if (null? ls1)
(if (null? ls2) '() (apply-append-s (car ls2) (cdr ls2)))
(shift c
(cons (car ls1)
(c (reset (apply-append-s (cdr ls1) ls2)))))))))
(if (null? ls-ls) '()
(reset (apply-append-s (car ls-ls) (cdr ls-ls))))))

Sponsored Links