[plt-scheme] Re: On continuations...

Matthias Felleisen writes: 

> P.S. If you come across a specification of the mathematical solution in 
> math, could you please share with us? Most mathematicians dont really use 
> higher-order functions much so there solution is typically much longer and 
> I'd love to see what they do instead.
 

Well, I present my solution, which seems slightly simpler than what
has been proposed by Jens Axel Søgaard. 

The mathematical idea is not so mathematical after all, rather structural.
Map is useful, and fold *may* be used, but the straight recursion is
simpler. No tables needed.
Take *one* concrete partition of 10, say the Ferrer diagram (or, as
physicists say, an (unfilled) Young diagram): (6,2,1,1) 

******
**
*
* 

It should be obvious that all partitions of N are: (N), and all partitions
(pkmax n (n-1)), where (pkmax n k) are all partitions restricted so that the
longest segment is equal or shorter than k. 

Now, pkmax can be decomposed into two contributions. First, with the longest
segment really equal to k, and
all lower restricted partitions, i.e., pkmax n (k-1). 

Here you are the program in Haskell 

part n | n>0 = [n] : pkmax n (n-1)
      | otherwise = []
pkmax n k | n>0 && k>0 = map (k:) (pkmax (n-k) k) ++ pkmax n (k-1)
         | n==0 = [[]]
         | otherwise = [] 

and its translation into Scheme: 

(define (part n)
 (if (> n 0) (cons (list n) (pkmax n (- n 1)))
     ()))
(define (pkmax n k)
 (cond ((and (> n 0) (> k 0))
        (append (map (lambda (x) (cons k x))
                     (pkmax (- n k) k))
                (pkmax n (- k 1))) )
       ((= n 0) (list ()))
       (else ()))) 

================================= 

Jerzy Karczmarczuk