combinatorial problem

combinatorial problem

Post by Pietr » Fri, 30 Jun 2006 15:14:22

Hi all,
I've this small mall toy problem.

type patt = A | B | C | X
type elemt = A of int | B of int | C of int

and a set of elements of type elemt, for example

S = { A(1), A(2), B(2), C(4) }

I want to write a function that enumerates all possible way of
pattern matching elements of the set S with a list of pattern of
type patt. So

f S [A ; B ; X]

shall return

[[A(1)];[B(2)],[A(2), C(4)]] ;
[[A(2)];[B(2)],[A(1), C(4)]]

that is, for each pattern A,B,C I'll match only one element from S,
while the pattern X is a catch-all pattern that will collect everything
that has not been matched.

I'm very much of an ocaml programmer and I already have an ocaml
solution (based on fold, map, flatten) and I'm kinda happy with it.

I'll be curious to see an haskell solution based on list comprehension.

I've just started to get my head around that syntax and I'm still not
sure how to write a compact and elegant solution for the problem above.

thanks :)

++ "All great truths begin as blasphemies." -George Bernard Shaw
++ Please avoid sending me Word or PowerPoint attachments.

combinatorial problem

Post by Dirk Thier » Tue, 04 Jul 2006 15:47:53

ietro < XXXX@XXXXX.COM > wrote:

As nobody else seems to want to reply: I don't think that list
comprehension is going to help a lot with this problem. But if
you just want to play around and get a feeling for the syntax,
the following is one way to do it:

Essentially, you need to find sublists of S (I assume you really mean
a list here, not a set. If you indeed want a set, I don't see much
point to "pattern matching", because then you can just split the set S
into all the letters, count all the letters in the "pattern", and
combine them completely independently -- no real "pattern" left,
especially it doesn't make sense to ask for any order inside the
pattern. Unless you just want to use the pattern as a "scheme" to
generate output). So here's a function that constructs all sublists
together with the "complement":


*Main> subl [1..2]

The reasoning is that each element of the list must be either in
the sublist (hence preppend it to all sublists of the recursive results),
or in the complement (hence preppend it to all complements). Note that
this function isn't very space efficient (it leaves lots of partially
evaluated thunks on the stack during lazy evaluation).

Now, let's declare a somewhat generalized data structure, and a
straightforward function to match a pattern with a sublist:

Then you can already find all matching sublists and their complements
with a list comprehension like [(s,r) | (s,r) <- subl ss, match pattern s].

Finally, you only have to substitute the results into the pattern. You
haven't defined what should happen if there's no X, or more than one
X, so I'll just substitute all X's with the complement:

Then you can write f as list comprehension

Note that the substitution is somewhat awkward, and repeats work already
done, and you could just work on directly with the results as in the
simpler comprehension above. This suggests that the "pattern language"
is probably not the right way to do it if you actually want to
go on working with the results.

- Dirk