# [plt-scheme] On continuations...

 From: Alexander Schmolck (a.schmolck at gmx.net) Date: Sun Dec 19 21:23:05 EST 2004 Previous message: [plt-scheme] Re: On continuations... Next message: [plt-scheme] On continuations... Messages sorted by: [date] [thread] [subject] [author]

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

>   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
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
if not tail or tail[0] <= head))

def lazyPartitions(n):
if n == 0:
return []
else:
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

 Posted on the users mailing list. Previous message: [plt-scheme] Re: On continuations... Next message: [plt-scheme] On continuations... Messages sorted by: [date] [thread] [subject] [author]