4 ms·

This is very, very, very bad scheme. set! and list-ref are no-no. This is better scheme: (define (pascal n) (if (= n 0) (list 1) (let ((L (pascal (- n 1))

by vtail 15y ago

This is very, very, very bad scheme. set! and list-ref are no-no. This is better scheme: (define (pascal n) (if (= n 0) (list 1) (let ((L (pascal (- n 1)))) (append (list 1) (map + (cdr L) L) (list 1)))))

jemfinch 15y ago
Ah, (map + (cdr L) L). That's excellent!
kunqiana 15y ago
Thanks for the tip, but when I tried to run it under mzscheme I got the error: map: all lists must have same size; arguments were: #<procedure:+> () (1). Also could you explain why set! and list-ref are bad?
- vtail 15y ago
  You are doing yourself a great service by learning Scheme - that can fundamentally change how you think about programming. Reading the first chapter of SICP[0] will change you forever. Yet right now you're using Scheme as a Python/C/Ruby with a strange syntax, while it's a totally different language with its own idioms. You should learn them to master Scheme. As for your particular questions: 1. map yields an error under mzscheme I'm at work, and didn't have access to a proper scheme, so I used an online REPL[1], which apparently is more forgiving. Regardless, you can write your own map (a good exercise!) that stops as soon as one of the arguments is exhausted. Make it tail-recursive[2] as well! 2. list-ref is bad Lists are beautiful data structures designed for recursive algorithms. If you are using lists and not using recursion (or a hidden recursion in the form of map), you're doing something wrong. list-ref uses list as a vector, which has a performance implications - your algorithm is O(n^3) while mine is O(n^2). 3. set! is bad Margins are too small for a proper explanation :), but basically set! has side-effects[3], and functional programming should avoid having them. Have fun learning Scheme! [0] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-9.html#%_chap_1 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-9.html#... [1] http://www.bluishcoder.co.nz/jsscheme/ http://www.bluishcoder.co.nz/jsscheme/ [2] http://en.wikipedia.org/wiki/Tail_call http://en.wikipedia.org/wiki/Tail_call [3] http://en.wikipedia.org/wiki/Side_effect_(computer_science) http://en.wikipedia.org/wiki/Side_effect_(computer_science)
  - kunqiana 15y ago
    Just out of curiosity did you learn scheme primarily through books? Do you actually use the language on a daily basis? Maybe you are a lisp hacker?
mangodrunk 15y ago
Using (map + (cdr L) L) doesn't work since they're different sizes (with DrRacket that I used, I see that it worked for you in your other comment, it is a very nice solution!). I'm not sure of an easy constant time way to append a zero to the end of (cdr L). The way I did it is similar to how you did it without map: (define next (lambda (l) (if (null? (cdr l)) '(1) (cons (+ (car l) (cadr l)) (next (cdr l)))))) (define pascal (lambda (n) (cond ((< n 1) '()) ((= n 1) '(1)) (else (cons 1 (next (pascal (- n 1))))))))

by vtail 15y ago

jemfinch 15y ago

Ah, (map + (cdr L) L). That's excellent!

kunqiana 15y ago

Thanks for the tip, but when I tried to run it under mzscheme I got the error: map: all lists must have same size; arguments were: #<procedure:+> () (1). Also could you explain why set! and list-ref are bad?

vtail 15y ago
You are doing yourself a great service by learning Scheme - that can fundamentally change how you think about programming. Reading the first chapter of SICP[0] will change you forever. Yet right now you're using Scheme as a Python/C/Ruby with a strange syntax, while it's a totally different language with its own idioms. You should learn them to master Scheme. As for your particular questions: 1. map yields an error under mzscheme I'm at work, and didn't have access to a proper scheme, so I used an online REPL[1], which apparently is more forgiving. Regardless, you can write your own map (a good exercise!) that stops as soon as one of the arguments is exhausted. Make it tail-recursive[2] as well! 2. list-ref is bad Lists are beautiful data structures designed for recursive algorithms. If you are using lists and not using recursion (or a hidden recursion in the form of map), you're doing something wrong. list-ref uses list as a vector, which has a performance implications - your algorithm is O(n^3) while mine is O(n^2). 3. set! is bad Margins are too small for a proper explanation :), but basically set! has side-effects[3], and functional programming should avoid having them. Have fun learning Scheme! [0] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-9.html#%_chap_1 http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-9.html#... [1] http://www.bluishcoder.co.nz/jsscheme/ http://www.bluishcoder.co.nz/jsscheme/ [2] http://en.wikipedia.org/wiki/Tail_call http://en.wikipedia.org/wiki/Tail_call [3] http://en.wikipedia.org/wiki/Side_effect_(computer_science) http://en.wikipedia.org/wiki/Side_effect_(computer_science)
- kunqiana 15y ago
  Just out of curiosity did you learn scheme primarily through books? Do you actually use the language on a daily basis? Maybe you are a lisp hacker?

mangodrunk 15y ago

Using (map + (cdr L) L) doesn't work since they're different sizes (with DrRacket that I used, I see that it worked for you in your other comment, it is a very nice solution!). I'm not sure of an easy constant time way to append a zero to the end of (cdr L). The way I did it is similar to how you did it without map: (define next (lambda (l) (if (null? (cdr l)) '(1) (cons (+ (car l) (cadr l)) (next (cdr l)))))) (define pascal (lambda (n) (cond ((< n 1) '()) ((= n 1) '(1)) (else (cons 1 (next (pascal (- n 1))))))))