I need help with Scheme

Question

taylola 0 Newbie Poster

17 Years Ago

Hi! I am new to Scheme and I need help with this problem.

Split and return a list of two lists at a given element; call it (split List Element). The given element should be the head of the second list.
(split ‘(2 3 4 6) 4) => ((2 3) (6)). If the element is not in the list, a list consisting of the list and the null list are returned.

This is what I have so far along with some other functions I had to do. Can someone please help me with this split function???

(define(split List Element)
;(c)splits and returns a list of two lists at a given element. The given element should be the head of the second list. If the element is not in the list, a list consisting of the list and the null list are returned.
(cond ((equal?(member Element List)#F)(cons List ()))
(else
(cond ((null? List) (cons List ()))
((equal? Element (car List)) (cons () List))
))))

(define(remove Item List)
;(a)remove an element from a list and return the list without the element
(cond ((null? List) List)
((equal? Item (car List)) (cdr List))
(else( cons (car List) (remove Item (cdr List))))))

(define(after Given List)
;(b)return the tail of a list after a given element (if element is not in list it returns the original list)
(cond ((equal?(member Given List)#F)List)
(else
(cond ((null? List) List)
((equal? Given (car List))(cdr List))
(else( after Given(cdr List)))))))

;(d)returns the last element of a list.
(define(last list)
(cond ((null? (cdr list)) (car list))
(else (last (cdr list)))))

;(e)counts the elements (length) of a list.
(define (count list)
(cond((null? list) 0)
(else (+ 1 (count (cdr list))))))

;(f)Merges two (ascending) ordered lists of integers into a single (ascending)ordered list.
(define (Merge a b)
(cond
((null? a) b)
((null? b) a)
((< (car a) (car b))
(cons (car a) (Merge (cdr a) b)))
((>= (car a) (car b))
(cons (car b) (Merge a (cdr b))))
))

;(g)Returns the shorter of two lists.
(define (shorter l1 l2)
(if (< (count l2) (count l1))
l2
l1))

lisp-scheme

3 Contributors
7 Replies
260 Views
2 Months Discussion Span
Latest Post 17 Years Ago Latest Post by Harleqin

Dani AI

Generated 9 Months Ago

Quick clarification first: the element you split on should be the head of the second sublist. So splitting at 4 in the list '(2 3 4 6) should produce '((2 3) (4 6)), not drop the pivot. already called out that expectation.

A clean, idiomatic approach is to walk the list once with a tail-recursive helper, accumulating items seen so far (in reverse). When you hit the pivot, return the reversed accumulator as the first list and the current remainder (starting with the pivot) as the second. If you reach the end without finding the pivot, return the original list and the empty list. This handles the pivot-at-head case, absent-element case, and splits at the first occurrence.

Example implementation (tail-recursive, O(n) time):

(define (split lst pivot)
  (let loop ((xs lst) (front '()))
    (cond ((null? xs) (list (reverse front) '()))
          ((equal? (car xs) pivot) (list (reverse front) xs))
          (else (loop (cdr xs) (cons (car xs) front))))))

Notes and quick tips:

Use equal? for general equality; if you know the list contains only numbers, = is appropriate (but errors on non-numbers).
This splits at the first match. If you need to split at the last occurrence, you must scan the whole list and remember the last match.
Scheme guarantees proper tail calls, so the helper is stack-safe. Complexity is linear and you allocate O(n) extra conses for the accumulator and reversed result.
As hinted, keep your code well indented and test small cases in the REPL (or use trace/display) to find logic errors quickly.

All 7 Replies

Rashakil Fol 978 Super Senior Demiposter

17 Years Ago

Use code tags please.

Rashakil Fol 978 Super Senior Demiposter

17 Years Ago

What the fuck. Do you realize how bad the indentation is?

Aghh.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

taylola 0 Newbie Poster · Answer 1 · 2009-03-08T04:59:57+00:00

Use code tags please.

Hi! I am new to Scheme and I need help with this problem.

Split and return a list of two lists at a given element; call it (split List Element). The given element should be the head of the second list.
(split ‘(2 3 4 6) 4) => ((2 3) (6)). If the element is not in the list, a list consisting of the list and the null list are returned.

This is what I have so far along with some other functions I had to do. Can someone please help me with this split function???

(define(split List Element)
;(c)splits and returns a list of two lists at a given element. The given element should be the head of the second list. If the element is not in the list, a list consisting of the list and the null list are returned.
(cond ((equal?(member Element List)#F)(cons List ()))
(else
(cond ((null? List) (cons List ()))
((equal? Element (car List)) (cons () List))
))))

(define(remove Item List)
;(a)remove an element from a list and return the list without the element
(cond ((null? List) List)
((equal? Item (car List)) (cdr List))
(else( cons (car List) (remove Item (cdr List))))))

(define(after Given List)
;(b)return the tail of a list after a given element (if element is not in list it returns the original list)
(cond ((equal?(member Given List)#F)List)
(else
(cond ((null? List) List)
((equal? Given (car List))(cdr List))
(else( after Given(cdr List)))))))

;(d)returns the last element of a list. 
(define(last list)
(cond ((null? (cdr list)) (car list))
(else (last (cdr list)))))

;(e)counts the elements (length) of a list.
(define (count list)
(cond((null? list) 0)
(else (+ 1 (count (cdr list))))))

;(f)Merges two (ascending) ordered lists of integers into a single (ascending)ordered list.
(define (Merge a b)
(cond
((null? a) b)
((null? b) a)
((< (car a) (car b))
(cons (car a) (Merge (cdr a) b)))
((>= (car a) (car b))
(cons (car b) (Merge a (cdr b))))
))

;(g)Returns the shorter of two lists. 
(define (shorter l1 l2) 
(if (< (count l2) (count l1)) 
l2 
l1))

Rashakil Fol 978 Super Senior Demiposter Team Colleague · Answer 2 · 2009-03-08T06:28:26+00:00

Well, if you want to implement a split function, the first step would be for your code to handle all the possible cases.

taylola 0 Newbie Poster · Answer 3 · 2009-03-08T08:14:54+00:00

Look that is just how it copied over from Dr. Scheme...sorry you don't have to help me out ok

Rashakil Fol 978 Super Senior Demiposter Team Colleague · Answer 4 · 2009-03-08T08:26:54+00:00

The ironic thing is that your first pasting _was_ indented, if you look at when you quote it.

And I do want to help, I just identified for you the main thing you need to do to implement split right now. What is stopping you from doing that?

Harleqin 0 Newbie Poster · Answer 5 · 2009-06-03T05:24:59+00:00

Split and return a list of two lists at a given element; call it (split List Element). The given element should be the head of the second list.
(split ‘(2 3 4 6) 4) => ((2 3) (6)). If the element is not in the list, a list consisting of the list and the null list are returned.

I believe that (split '(2 3 4 6) 4) should return ((2 3) (4 6)) , according to the specification.

(define (split List Element)
  ;(c)splits and returns a list of two lists at a given element. The
  ;given element should be the head of the second list. If the
  ;element is not in the list, a list consisting of the list and the null
  ;list are returned.
  (cond ((equal? (member Element List) #F) (cons List ()))
        (else
         (cond ((null? List) (cons List ()))
               ((equal? Element (car List)) (cons () List))))))

OK, first a little cleanup: having an (else (cond ;... clause in a cond form is not sensible; the following does exactly the same, but clearer:

(define (split List Element)
  (cond ((equal? (member Element List) #F) (cons List ()))
        ((null? List) (cons List ()))
        ((equal? Element (car List)) (cons () List))))))

Asking whether something is equal? to #f is better expressed as (false? something) :

(define (split List Element)
  (cond ((false? (member Element List)) (cons List ()))
        ((null? List) (cons List ()))
        ((equal? Element (car List)) (cons () List))))))

What does member do? It walks the list, and as soon as it finds the element it is looking for, it returns the tail of the list including the element. If the element is not in the list, #f is returned. Well, this is almost what you need for the second part of your result, but how do you get the first part then? When you construct the first part, you will get the second almost automatically, so you don't need member here.

You will need to walk the list somehow, most likely with a recursive helper function. Every element that is not the searched one gets pushed onto an intermediate list. As soon as you find the element, you reverse the intermediate list, and return it together with the tail of the original list.

Feel free to show how far you got.

I need help with Scheme

Dani AI

Recommended Answers Collapse Answers

All 7 Replies

Recommended Answers