solving catalan type problems using Haskell

[kashyap]

Hi All,
I am a Haskell beginner. I was attempting to translate a catalan
problem of figuring out the possible combinations of a given number of
parenthesis. I'd appreciate it very much if you could help me with
this.

Here's the perl program -

#!/usr/bin/perl -w

use strict;

my $N = shift;

sub recurse
{
my ($string, $num_opened, $num_closed) = (@_);
if (($num_opened == $N) && ($num_closed == $N))
{
print "$string\n";
}
if ($num_opened < $N)
{
recurse("$string(", $num_opened+1, $num_closed);
}
if ($num_opened > $num_closed)
{
recurse("$string)", $num_opened, $num_closed+1);
}
}

recurse("", 0, 0);



And here's my attempt in haskell -


:: Int -> String
p n = _p "" n 0 0

_p :: String -> Int -> Int -> Int -> String
_p s n o c
| c==n && o==n = s
| o < n = _p (s++"(") n (o+1) c
| o > c = _p (s++")") n o (c+1)

This gives out only one solution -

Regards,
Kashyap

[Marius Scurtescu]

Hi Kashyap,

I am assuming that you refer to this problem:
http://mathworld.wolfram.com/CatalansProblem.html

I am also learning Haskell, so take my reply for what is worth.

The sample Perl code is using the side effect of print to show all the
results, it is not collecting them in a data structure for example. In
Haskell you don't have side effects like this (well, you do, but
that's more complicated) so you cannot transcode 1-to-1 the Perl
implementation.

In Haskell the recursion will terminate when you first hit "| c==n &&
o==n = s" and only that result will be returned, this is why you get
only one.

What you need is to also pass an accumulator with a partial list of
results, and when you find more just keep appending. At the end this
accumulator will contain all of them.

Here is an implementation that will work:

catalan :: Int -> String
catalan n = cata "" [] n 0 0

cata :: String -> [String] -> Int -> Int -> Int -> [String]
cata s ss n o c
| c==n && o==n = s:ss
| otherwise = let
ss1 = if o < n then cata (s ++ "(") ss n
(o + 1) c else []
ss2 = if o > c then cata (s ++ ")") ss n o
(c + 1) else []
in
ss1 ++ ss2 ++ ss

The second argument to cata is the accumulator with the solutions
found so far. The return type of cata is a list of Strings, the
solutions found so far (the second argument, plus what was found in
this iteration). Also, please note that in the Perl code the second
and third if statements do not exclude each other, they can both be
executed. This is why I called both, if the conditions are met, and
collected all results with "ss1 ++ ss2 ++ ss".

I am sure that there are more elegant solutions, and I would be
curious to see them. Let us know if you find any.

Marius

--
http://marius.scurtescu.com

[Marius Scurtescu]

Just realized that there is a problem with the type signature of
catalan, it should be:
catalan :: Int -> [String]

Marius

On Wed, Mar 25, 2009 at 12:17 AM, Marius Scurtescu
<marius.s...@gmail.com> wrote:
> Here is an implementation that will work:
>
> catalan :: Int -> String
> catalan n = cata "" [] n 0 0

--
http://marius.scurtescu.com

[Marius Scurtescu]

After all that theory about accumulators I figured that in this case
they are not really needed. The previous version just happened to
work.

Here is a simplified version:
http://codepad.org/xN63Nmnn

Marius

On Wed, Mar 25, 2009 at 12:21 AM, Marius Scurtescu

<marius.s...@gmail.com> wrote:
> Just realized that there is a problem with the type signature of
> catalan, it should be:
> catalan :: Int -> [String]
>
> Marius
>
>
> On Wed, Mar 25, 2009 at 12:17 AM, Marius Scurtescu
> <marius.s...@gmail.com> wrote:
>> Here is an implementation that will work:
>>
>> catalan :: Int -> String
>> catalan n = cata "" [] n 0 0
>
> --
> http://marius.scurtescu.com
>

--
http://marius.scurtescu.com