scheme expand function

I've been trying to solve this problem for hours. function expand that takes a list of elements and frequencies and expands them into a simple list. For example, the result of (expand '(a (3 b) (3 a) b (2 c) (3 a)) should be (a b b b a a a b c c a a a)

Here is my solution:

helper function:

(define (expandHelper n value)
  (if (= 0 n) 
      '()
      (cons (append (cons value '()))(expandHelper (- n 1) value)))) 

the expand fun开发者_运维问答ction

(define (expand lst) 
  (cond ((null? lst) '())
    (else (expandHelper (car lst) (cadr lst)))))

But, it doesn't do what I expected it to do. It looks for an integer when the list only has one element which is the value. For example, (expand '(a (2 b)). Since there is only one copy of a, it doesn't have (1 a) in the expression. I am new to Scheme. I would really appreciate it if you could help me.

Thanks

Here is an updated version: But's it's still not right. I would really appreciate it if someone would help me modify my code to get the right results.

;; helper function
(define (expandHelper value)
  (if (= 0 value) 
      '()
      (cons (append (cons (car sublist) '()))(expandHelper (- (car sublist) 1) (car sublist)))))  

;; the expand function
(define (expand lst) 
  (cond ((null? lst) '())
        (else (list? (car lst)) (expandHelper (car lst)) (expand (cadr lst)))))

This would be my solution, without any helper function, and recursing on sublist (i.e. (3 a) becomes (cons a (expand '(2 a))):

#lang racket

(define (expand lst)
  (cond
    ((null? lst) '())
    ((list? (car lst))
     (let ((cnt (caar lst)) (chr (cadar lst)))
       (if (= cnt 0)
           (expand (cdr lst))
           (cons chr (expand (cons (list (- cnt 1) chr) (cdr lst)))))))
    (else (cons (car lst) (expand (cdr lst))))))

You can express it as a right-fold, and avoid developing a custom recursive function. If the next element is a list like (3 a), expand and prepend it. If a symbol, just cons it.

(define (expand xs)
  (fold-right
   (lambda (x result)
     (if (list? x)
     (append (apply make-list x) result)
         (cons x result)))
   '()
   xs))

(define (term-expander n val partial)
  (if (zero? n)
    partial
    (term-expander (- n 1) val (cons val partial))))

(define (append-expand a b)
  (if (pair? b)
    (append a (term-expander (car b) (cadr b) '()))
    (append a (list b))))

(define (expand l) (foldl append-expand l '() ))

> (expand '(a (3 b) (3 a) b (2 c) (3 a)))
(a b b b a a a b c c a a a)

So... term-expander takes (5 a) -> '(a a a a a)'. append-expand will append the newest term (expanded iff it is a pair) to our answer in progress. just need to fold this over the list.

I'd hope you have a foldl already, but heres mine just in case.

(define (foldl op seq init)
  (define (iter acc rest)
    (if (null? rest)
      acc
      (iter (op acc (car rest)) (cdr rest))))
  (iter init seq))

EDIT

Realized afterwards this is can be done a LITTLE bit more naturally with foldr rather than foldl (will need append-expand written differently). Why don't you see if you can find it? Same idea mostly, but it will operate on the list from back to front and lends itself more naturally to cons structures

Here's me doing it without fold, but it works the same way and i dont really care for it

(define (term-expander p partial)
  (if (zero? (car p))
    partial
    (term-expander (cons (- (car p) 1) (cdr p)) (cons (cadr p) partial))))

(define (expand l)
  (define (expand-rec l partial)
    (if (null? l)
      partial
      (let ((t 
        (if (pair? (car l))
             (term-expander (car l) '())
             (list (car l)))))
      (expand-rec (cdr l) (append partial t)))))
  (expand-rec l '()))

> (expand '(a (3 b) (3 a) b (2 c) (3 a)))
(a b bb a a a b c c a a a)

If you would prefer, the (if (pair?... section could go in to term-expander instead, and then you'd just call it across the board. I slightly prefer this way but its all the same

There are two things you should think about here. The first is the one you mentioned-- that you could have either a or (1 a), both meaning the same thing. You probably want to move that into expandHelper, so it looks more like (expandHelper value), and then you should switch on whether it's a list or a symbol.

The second is in how you're calling expandHelper. If you feed in a list like '(a (3 b) (3 a) b (2 c) (3 a)) to expand, it'll currently call (expandHelper a (3 b)), which is probably not what you had in mind. Instead, you want to make sure you call expandHelper on every element of the list, and cons together the results. You can do that by calling expandHelper on the first element of the list, and then recursively calling expand on the remainder of the list.

I haven't checked to see that this compiles, it's just the general idea:

(define (expandHelper value)
    (if (list? value) ;; means value is something like (2 a)

        (if (= 0 (car value)) ;; then (car value) is 2
            '() ;; if it's zero, we complete the list and return!
            (cons (cadr value) ;;otherwise, we append (cadr value) = a to...
                  (expandHelper (cons (- (car value) 1) (cadr value))))))
                  ;; the result of expand helper on (- (car value) 1) = 1 
                  ;; and (cadr value) = a

         (cons value '()))) ;; if it's not a list, we should just return the value.

 (define (expand l)
   (cond ((null? l) '())
         ((not (pair? (car l))) (cons (car a) (expand (cdr l)))
         ((< (caar l) 1) (expand (cdr l)))
         (else (cons (cadar l)) (expand (cons (cons (- (caar l) 1) (cdar l))
                                                (cdr l))))))