# sicp-ex-2.18

jz

I couldn't figure out a way to do this problem without using an intermediary variable to store the reversed list as it is built. If there is such a way, post it.

```
;; ex 2.18, reverse.

;; Note: nil isn't defined in my environment, using footnote from page
;; 101.
(define nil '())

(define (reverse items)
(define (iter items result)
(if (null? items)
result
(iter (cdr items) (cons (car items) result))))

(iter items nil))

;; Usage
(reverse (list 1 2 3 4))

```

vlprans

This is a solution that doesn't use intermediary variable, former should be more efficient though.

```
(define nil '())

(define (reverse items)
(if (null? (cdr items))
items
(append (reverse (cdr items))
(cons (car items) nil))))

(reverse (list 1 2 3 4))

```

You can get rid of the nil definition by replacing cons with list:

``` guile>
(define (reverse items)
(if (null? (cdr items))
items
(append (reverse (cdr items))
(list (car items)))))
guile> (reverse (list 1 2 3 4))
(4 3 2 1)
guile>
```

You can also get rid of the boundary-condition failure by eliminating the first cdr:

``` guile> (reverse '())

Backtrace:
In standard input:
9: 0* [reverse {()}]
2: 1  (if (null? (cdr items)) items ...)
2: 2* [null? ...
2: 3*  [cdr {()}]]

standard input:2:14: In procedure cdr in expression (cdr items):
standard input:2:14: Wrong type (expecting pair): ()
ABORT: (wrong-type-arg)
guile>
(define (reverse items)
(if (null? items)
items
(append (reverse (cdr items))
(list (car items)))))
guile> (reverse '())
()
guile> (reverse (list 1 2 3 4))
(4 3 2 1)
guile>

```

bmm

``` ;; ex 2.18

;; nil
(define nil '())

;; returns length of list
(define length (lambda (list)
(if (null? list) 0
(+ 1 (length (cdr list))))))

;; returns the n-th element
(define list-ref (lambda (list n)
(if (= n 0) (car list)
(list-ref (cdr list) (- n 1)))))

;; reverse list procedure
(define (reverse list)
(define (do-reverse items size)
(if (< size 0) nil
(cons (list-ref items size) (do-reverse items (- size 1)))))
(let ((len (- (length list) 1)))
(do-reverse list len)))

;; Test

(reverse (list 1 2 3 4 5)) ;; '(5 4 3 2 1)
```

karthikk

Yes, the boundary condition (when the input parameter is the null list) should work. So here are two simple solutions: the first generates an iterative process and the second a recursive process (note since cons treats its first formal parameter as an atom, we have to use append in the recursive definition). The iterative solution is mostly the same as the fp's but the recursive definition eliminates testing the base step on the cdr of the list...

```
;iterative solution
(define (i-reverse l)
(define (it-rev lat ans)
(if (null? lat)
ans
(it-rev (cdr lat) (cons (car lat) ans))))
(it-rev l '()))

;recursive solution
(define (r-reverse lat)
(if (null? lat)
'()
(append (r-reverse (cdr lat)) (list (car lat)))))
```

This is the combination of jz's comment and the reply to vlprans's comment.

dgski

Solution using collector paradigm (form of iterative process).

```
(define (reverse l)
(define (helper l col)
(if (null? (cdr l))
(col (car l))
(helper (cdr l) (lambda (x)
(cons x (col (car l)))))))
(helper l (lambda (x) (cons x '()))))

```

This uses one col wrapper for jz's comment although it doesn't consider the case when l is nil.

gwj

a iterative solution of reverse,also fit when it is a empty list

```
(define (reverse items)
(define (iter list result)
(if (null? list)
result
(iter (cdr list) (cons (car list) result))))
(if (null? items)
(list )
(iter (cdr items) (cons (car items) nil))))

```

Similar to the former jz's but manipulates with nil out of (iter list result).

LisScheSic

This is also shown in course 6.001 Fall 2007 Recitation 7 solution https://people.csail.mit.edu/jastr/6001/fall07/r07sol.pdf 4-(h). fold-left https://www.r6rs.org/final/r6rs-lib.pdf is implemented in R6RS https://stackoverflow.com/a/32698820/21294350. MIT-Scheme as the course includes this implementation (its implementation is a bit too complex in source code https://github.com/jaseemabid/mit-scheme/blob/d30da6b2c103e34b6e0805bd5cbefeb9501382c1/src/runtime/list.scm#L793-L831).

So I tried to implement it by myself using the same interface as the lib (the idea is same as jz's comment):

``` (define x '(1 2 3 4 5 6 7))
(define nil '())
(define (fold-left op init lst)
(define (helper result rest_lst)
(if (null? rest_lst)
result
(helper (op result (car rest_lst)) (cdr rest_lst))))
(helper init lst))
(fold-left (lambda (a b) (cons b a)) nil x)
```

guile also implements it in https://github.com/cky/guile/blob/89ce9fb31b00f1f243fe6f2450db50372cc0b86d/module/rnrs/lists.scm#L40-L46 as https://lists.nongnu.org/archive/html/guile-devel/2010-06/msg00153.html says. This is almost same as the above mine.