[plt-scheme] On continuations...

Matthias Felleisen <matthias at ccs.neu.edu> writes:

>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
> In that case, you should definitely consider the functional solution the best
> effort. It would be a literal translation of the mathematical "program" that
> specifies the solution and thus automatically comes with a correctness proof.
> The Python solution is an imperative kludge whose correctness not one Python
> programmer, including GvR, could argue. 

A) Well you can write it as functionally as you like in python, too:

    (lambda f: (lambda g:lambda n:f(g(g))(n))(lambda g:lambda n:(f(g(g))(n))))(
        lambda partitions: lambda n: (n == 0 and [[]] or
                            [[head] + tail for head in range(1, n+1)
                                           for tail in partitions(n-head) 
                                           if not tail or tail[0] <= head]))


B) Which trivially transformed into a (of course no longer functional)
   generator version:

    def lazyPartitions(n):
        return (n == 0 and iter([]) or
                ([head] + tail for head in range(1, n+1) 
                               for tail in partitions(n-head) 
                               if not tail or tail[0] <= head))

Or more readably:

    def lazyPartitions(n):
        if n == 0:
             return []
        else:
             return ([head] + tail for head in range(1, n+1) 
                                   for tail in partitions(n-head) 
                                   if not tail or tail[0] <= head)

This also translates pretty directly into (non-idiomatic) Haskell:

    partitions n = if n == 0 then 
                       [[]]
                   else 
                       [h:t | h <- [1..n], 
                              t <- partitions(n-h), 
                              t == [] || (head t) <= h]

And frankly though the generators might be evil/imperative etc. -- in practice
I'd be rather more quickly convinced of the correctness of the above python
and haskell versions than of that of the list-based scheme versions posted so
far (because I find it more readable). Plus, of course both the haskell and
the generator style python rendering have the not inconsiderable advantage
that you only need to "pay as you go" (and the above is trivially translated
into an efficient version).

'as