CODEWITHSUNDEEP
schemelisp
Zafar
Zafar

Reputation: 1211

Reversing list with sublists and atoms in lisp

I am new to a functional programming and trying to reverse a list in lisp. List consists of sublists and atoms. The function (reverse-tree '((1 2) 5 6 (3))) should return ((3) 6 5 (2 1)). Here is my function:

(define (reverse-tree s)
    ;; giving problem with an atom 
  (if (not(list? s)) ( reverse-tree s) (reverse (map reverse s)))

  )

It works when I do (reverse-tree '((1 2) (3))) => ((3) (2 1)). But it crashes when I do (reverse-tree '((1 2) 5 6 (3))). The error I am getting is reverse: contract violation expected: list?

I am limited to use only: reverse, map, if, cond, list? null? functions.

EDIT, someone marked this question as duplicate, but there is a restriction in this problem, which is not similar to the other question. I cannot use cons, car, cdr, append. Any suggestions?

Upvotes: 1

Views: 1048

Answers (1)

jkiiski
jkiiski

Reputation: 8421

Think about the problem in pieces. First, if the function is given a list as an argument, you need to reverse that list. That's easy, something like:

(define (reverse-tree tree)
  (if (list? tree)
      (reverse tree)
      ...))

But you also need to reverse all sublists in it and all sublists in them and so on. Since that's exactly what our reverse-tree does, we should use map to apply it to all elements in the reversed list (it doesn't actually matter whether you use map before or after reversing the list):

(define (reverse-tree tree)
  (if (list? tree)
      (map reverse-tree (reverse tree))
      ...))

But if the input is ((1 2) 3 4 (5 6)), the map will call reverse-tree on the atoms 3 and 4 too. It wouldn't make any sense to reverse them, so we can just return them:

(define (reverse-tree tree)
  (if (list? tree) 
      (map reverse-tree (reverse tree))
      tree))

Now it should work:

(reverse-tree '((1 2) 3 4 (5 6)))
;=> ((6 5) 4 3 (2 1))
(reverse-tree '((1 2) 3 4 (5 6 (7 8))))
;=> (((8 7) 6 5) 4 3 (2 1))

Upvotes: 1

Related Questions