[kunqiana]

I tried to recode what you did in scheme for practice

    (define (pascal n)
      (if (= n 0) (list 1)
       (begin
       (let ((L (pascal (- n 1)))
           (ret (list 1))) 
       (do ((i 0 (+ i 1)))
           ((= i (- (length L) 1)))
           (begin (set! ret (append ret (list (+ (list-ref L    i) (list-ref L (+ i 1))))))))
       (append ret (list 1))
        ))))

[vtail]

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)))))

[kunqiana]

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]

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#... [1] http://www.bluishcoder.co.nz/jsscheme/ [2] http://en.wikipedia.org/wiki/Tail_call [3] http://en.wikipedia.org/wiki/Side_effect_(computer_science)

[kunqiana]

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]

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))))))))

[jemfinch]

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

[rayval]

Here's my version in C:

    int main(int argc, char ** argv) 
    { 
    	long *n1,*n2;
    	int row,i;

    	row=0; N1[0]=1L; print_row(row,N1);

    	while(row++ < MAX_ROWS)
    	{
    		for(i=0, n1 = N1, n2=N2; i<MAX_BUF && *n1; i++)
    		{
    			if (i==0 )        n2[i] = 0       + n1[i];
    			else if(n1[i]==0) n2[i] = n1[i-1] + 0;
    			else              n2[i] = n1[i-1] + n1[i];
    		}
    		print_row(row,N2);
    		for(n1=N1,n2=N2; *n2; ) *n1++ = *n2++;
    	}
    }

    void print_row(int row,long*n)
    {
        printf("row #%d",row);
        while(*n) { printf(" %ld ", *n++);}
        printf("\n");
    }

This works through the size of long int (at least 50 rows).

[haberman]

I think some of your code is missing (like where N1 and MAX_ROWS are defined).

Here's mine:

  #include <stdio.h>
  #include <stdlib.h>

  long *pascal(int row) {
    long *ret = (row == 1 ? NULL : pascal(row - 1));
    ret = realloc(ret, sizeof(long) * row);
    ret[row - 1] = 1;
    for (int i = row - 2; i > 0; i--)
      ret[i] += ret[i - 1];
    return ret;
  }

  int main(int argc, char *argv[]) {
    int row = atoi(argv[1]);
    long *data = pascal(row);
    for (int i = 0; i < row; i++)
      printf("%ld ", data[i]);
    printf("\n");
    free(data);
    return 0;
  }

[zyzzy]

Hi,

I ran your code and it does run well. However fails for large cases such as pascal(200000).

You mentioned you worked for Google and Amazon, how can you modify the code to get an answer for pascal(200000)

[haberman]

Yeah, for large cases the long will overflow (also it will do a lot of realloc()). Your two main options for this are:

  1. use double to get approximately-correct answers
  2. use an abitrary-precision library like GMP

[zyzzy]

What if I wanted an exact precision. Could I use a custom data type to get better precision? If I used a custom data type, how could I make the code work for a distributed system to get parallel behavior?

[jiggy2011]

upvoted for realloc trick

[haberman]

This inspired me to write one that is even shorter and doesn't heap-allocate any memory at all. What can I say, I'm a sucker for minimal C.

  #include <stdio.h>
  #include <stdlib.h>

  int main(int argc, char *argv[]) {
    int row = atoi(argv[1]);
    long data[row];
    for (int i = 0; i < row; i++) {
      data[i] = 1;
      for (int j = i - 1; j > 0; j--) data[j] += data[j - 1];
    }
    for (int i = 0; i < row; i++) printf("%ld ", data[i]);
    printf("\n");
    return 0;
  }

[demallien]

When did C start accepting non-constants for array size declarations?

[hn_reader]

I was wondering the same thing. But I can confirm it compiles and runs, though I had to supply a -std=c99 flag to gcc.

[haberman]

Variable-length arrays were added in C99.

[hn_reader]

Best solution I've seen here so far.

[shaggyfrog]

If row is too big you can bust your stack frame when you define your data array.

[hn_reader]

True, though in this example integer overflow would happen first.

[kunqiana]

I think your code is off by 1.