17

So I have to remove the last element of a list in scheme.

For example, let's say I have a list (1 2 3 4). I need to return:

(1 2 3)

My idea:

reverse(list)
car(list)
reverse(list)

Is there a reverse function in scheme(racket)?

Verbeia
  • 4,400
  • 2
  • 23
  • 44
  • Indeed, one of the best things about StackOverflow is that once a question is posted, it can be referenced and built upon in other posts. SO is one of the top hits on Google when you search for things, so if someone comes across this in the future, they can learn from what is here. :) – corsiKa Feb 16 '11 at 00:07
  • To find out whether Racket has a reverse function, use docs.racket-lang.org to look it up. – soegaard Feb 16 '11 at 13:33
  • (reverse (cdr (reverse '(1 2 3)))) works fine in chez and racket. In any case if you open the interpreter (like in Terminal) an type a letter followed by TAB you should access the auto-complete suggestion which is a great way to answer this question by yourself. – majik Jul 06 '18 at 02:36

7 Answers7

24

You wrote: "reverse, car, reverse". I believe you meant to write "reverse, cdr, reverse". There's nothing wrong with this solution; it's linear in the size of the list, just like any solution to this that uses the standard lists.

As code:

;; all-but-last: return the list, not including the last element
;; list? -> list?
(define (all-but-last l) (reverse (cdr (reverse l))))

If the multiple traversal of the list or the needless construction of another list copy bothers you, you can certainly avoid it, by writing the thing directly.

Given your almost-solution, I'm going to assume that this isn't homework.

Here's what it would look like, in racket:

#lang racket

(require rackunit)

;; all-but-last : return the list, except for the last element
;; non-empty-list? -> list?
(define (all-but-last l)
  (cond [(empty? l) (error 'all-but-last "empty list")]
        [(empty? (rest l)) empty]
        [else (cons (first l) (all-but-last (rest l)))]))

(check-equal? (all-but-last '(3 4 5))
              '(3 4))
John Clements
  • 16,895
  • 3
  • 37
  • 52
  • 1
    p.s.: this solution uses several racket-isms: first & rest, error, check-equal?, etc. I'm assuming that this is okay, because your question is tagged "racket". – John Clements Feb 15 '11 at 17:27
11

There is a reverse, but using it would not be very efficient. I suggest the following recursive function.

(define (remove-last lst)
    (if (null? (cdr lst))
        '()
        (cons (car lst) (remove-last (cdr lst)))))

(remove-last '(1 2 3 4)) ; returns '(1 2 3)

The if checks whether it is at the last element of the list.

Tim
  • 13,904
  • 10
  • 69
  • 101
  • 2
    Actually, `reverse` is O(n), just like your function is. Both approaches are okay. – C. K. Young Feb 15 '11 at 17:35
  • 2
    @Chris: They are indeed of the same complexity class, but this algorithm should still be twice as fast because it only traverses the list once. – Tim Feb 15 '11 at 17:37
  • 4
    Only if you use a very narrow definition of "traverse". Since your function isn't tail-recursive, consing up from your call stack could be seen as the second traversal. – C. K. Young Feb 15 '11 at 17:38
  • @ChrisJester-Young, I don't know if Racket implements tail recursion modulo cons, but that would do the trick here. – dfeuer Feb 01 '15 at 19:18
10

SRFI 1 (activate in Racket using (require srfi/1)) has a drop-right function:

 (drop-right '(1 2 3 4) 1)   ; => (1 2 3)
C. K. Young
  • 219,335
  • 46
  • 382
  • 435
2

I've done something simpler than: reverse(list), car(list), reverse(list) to get the last element, check out:

(define (last-one liste)
  (if(null? (cdr liste))
     null
     (cons (car liste) (last-one (cdr liste)))
  )
)
Piroh
  • 31
  • 2
  • (define (last-one liste) (if(null? (cdr liste)) () (cons (car liste) (last-one (cdr listed))) ) ) I think returning an empty list instead of a null is better. Because I got ;Unbound variable: null error in my Scheme version 9. – rebahozkoc May 31 '23 at 09:29
2

I would do a recursive function that goes down the list and attaches the element (using cons) if the element after it is not the last, and appends nothing if it isn't.

I haven't done scheme for years though so that's as far as I can go.

Someone can run with how to implement it (unless it's homework then they probably shouldn't!)

corsiKa
  • 81,495
  • 25
  • 153
  • 204
  • 1
    -1 Appending a list is an O(n) operation each time, which makes your whole function O(n²). That's what you get when you're working with linked lists. – C. K. Young Feb 15 '11 at 17:33
  • Appending to a list in is not O(n). Appending to an array backed list is O(n). Appending to a linked list (like it is in scheme) is O(1). – corsiKa Feb 15 '11 at 17:55
  • 4
    @glowcoder: Not true. _Prepending_ to a linked list is O(1). _Appending_ to a linked list is O(n) on the list being appended. (Remember, Scheme lists are singly-linked lists, not doubly-linked.) – C. K. Young Feb 15 '11 at 18:19
  • @Chris No, it is not. While you iterate through the list, you have the reference to the last element in it already (the beauty of tail recursion) so you it isn't O(n), it's O(1). – corsiKa Feb 15 '11 at 18:24
  • (Even if you're using a destructive `append!`, you still have to find the end node to `set-cdr!` with, which is O(n). A non-destructive `append` would require every cons cell of the list to be copied.) – C. K. Young Feb 15 '11 at 18:24
  • You might want to write some code to explain your approach, then, as what I'm reading is that you're calling `append` on each iteration. (You can `cons` on each iteration---that's O(1)---but that's not called appending.) – C. K. Young Feb 15 '11 at 18:26
  • In fact, @John implemented exactly what I recommended, and it's still O(n) time. – corsiKa Feb 15 '11 at 18:27
  • (Look, if you change append to cons in your post, I'll undo my downvote. :-)) – C. K. Young Feb 15 '11 at 18:27
  • 2
    Oh I see what you're saying. You were interpeting my use of the word append to mean the actual append function as opposed to the plain-text notion of append. In that case, I concede the point that the append function will cause the order of the function to inflate. :) – corsiKa Feb 15 '11 at 20:03
1

Those who are looking for another way can check this out:

(define (removing-last xx)
(remove (list-ref xx (- (length xx) 1)) xx))
ryanwebjackson
  • 1,017
  • 6
  • 22
  • 36
Parmida Pourmatin
  • 21
  • 2
  • 1
    Did you test with `(removing-last '(1 2 3 4 2))` ? – mnemenaut Apr 12 '22 at 06:19
  • Yes I think it works and the output will be `'(1 2 3 4)` – Parmida Pourmatin Apr 19 '22 at 05:36
  • `remove` in [Scheme](https://scheme.com/tspl4/objects.html#./objects:s53) and [Racket](https://docs.racket-lang.org/reference/pairs.html#%28def._%28%28lib._racket%2Fprivate%2Flist..rkt%29._remove%29%29) (Always a good idea to actually _run_ code :) – mnemenaut Apr 19 '22 at 07:25
  • (For learning Scheme/Racket, this free [course](https://learning.edx.org/course/course-v1:UBCx+HtC1x+2T2017/home) is strongly recommended) – mnemenaut Apr 19 '22 at 07:36
0

I would write a simple recursion, altering the typical "empty? mylist" base case to "empty? (rest mylist)," so that I can return empty when the input list is only 1 element.

(define (removelast mylist)
  (cond
    [(empty? (rest mylist)) empty]
    [(cons? mylist) (cons (first mylist) (removelast (rest mylist)))]))

(removelast (list 1 2 3 4 5))

By the way, this code is in Racket/PLT Scheme, a subset of Scheme.

Adrienne
  • 2,540
  • 1
  • 29
  • 39