Re: transitive closure

From: David Fetter <david_at_fetter.org>
Date: Fri, 10 Feb 2006 12:42:31 -0600
Message-ID: <rbqdnV41SpQKQ3HenZ2dnUVZ_vudnZ2d@speakeasy.net>

-CELKO- <jcelko212_at_earthlink.net> wrote:

>>> I yet to see a case that is handled by recursive "with" and not handled by "connect by". <<

>
> Want to try an Ackeramnn function?
>
> A(x,y) = if x = 0
> then (y+1)
> else if y = 0
> then A(x-1, 1)
> else A(x-1, A(x,y-1));

Here's a PostgreSQL version. It should be possible to memoize this using a table and one or two more SQL functions.

CREATE OR REPLACE FUNCTION ack(NUMERIC, NUMERIC) RETURNS NUMERIC
LANGUAGE SQL
AS '
SELECT
    CASE
    WHEN $1 = 0 THEN $2+1
    WHEN $2 = 0 THEN ack($1-1, 1)
    ELSE ack($1-1, ack($1, $2-1))
    END;
';

Cheers,
D

-- 
David Fetter david@fetter.org http://fetter.org/
phone: +1 510 893 6100    mobile: +1 415 235 3778

Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it.
                                       Kernighan

Received on Fri Feb 10 2006 - 12:42:31 CST