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 :)

p

--

++

++ "All great truths begin as blasphemies." -George Bernard Shaw

++ Please avoid sending me Word or PowerPoint attachments.

See http://www.yqcomputer.com/

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":

Example:

*Main> subl [1..2]

[([],[1,2]),([2],[1]),([1],[2]),([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

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":

Example:

*Main> subl [1..2]

[([],[1,2]),([2],[1]),([1],[2]),([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

1. question on constrained combinatorial problem with matlab

2. An interesting combinatorial problem

3. Determining the best model could be a "combinatorial problem" (Solvers come to mind)

5. Solving Large Combinatorial Problems

8. JMLR: Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems

9. Determining the best model could be a "combinatorial problem" (Solvers come to mind)

11. CFP-International Journal of Combinatorial Optimization Problems and Informatics

12. CALL FOR EDITORS-International Journal of Combinatorial Optimization Problems and Informatics

13. How to solve this Combinatorial Optimization problem?

14. CFP: CALL FOR EDITORS-International Journal of Combinatorial Optimization Problems and Informatics

2 post • Page:**1** of **1**