Pattern Matching - Polynomial?

Questions
1

Hi all,

I’d like to try and use pattern matching to check - and ideally parse - a student’s answer that should be a polynomial of the form ax^3+bx^2+cx+d. However, I’m drawing a blank if I want to allow for some of the terms to be negative without a forced + - situation - for example, I would like 3x^3-2x^2+5x-3 to be ‘matched’ just the same as if b and d were positive, but pattern matching does not recognise this as a “sum”.

So far I’ve tried, where … is a pattern to match a polynomial term:

  • p.anyOf(p.sum(...), p.difference(...)) - works for matching (to a degree) but not parsing as you don’t seem to be able to parse an ‘anyOf’. Also I think I would need to exhaust every combination of addition and subtraction to account for all cases.
  • p.sum(p.repeat(p.anyOf(...,p.negative(...)))) - doesn’t recognise a negative coefficient as part of the “sum”. Also couldn’t parse because of ‘anyOf’.
  • p.contains(p.repeat(...)) - simply doesn’t match anything.

and a couple of other options that just failed with an error.

I can check the function evaluates to the correct answer, and with countNumberUsage I could probably enforce the simplified form by brute force - but it kind of seems like this is exactly what pattern matching is good for. I just can’t figure out, if it’s even possible, what the correct match would be.

Grateful for any thoughts. Thanks!

2

It’s not very efficient but (unless I’m unaware of something) you need to make multiple combinations using difference instead of sum.

I think much easier would be to just use function evaluation, and maybe eliminate a product pattern (if you’re looking to exclude an unexpanded form). There may also be a way to parse the number of terms.

p=patterns
expanded= not(p.product(p.expression, p.expression)

I think something like this, 2x(3x+4), may cause issues.

3

Thanks Daniel for your response. It’s reassuring to know I’m not missing something obvious (or we both are!).

Yes, useful to consider just ruling out the unexpanded version. My main thing I was trying to eliminate was repeated like terms - students entering 5x^3+…+3x^3+… rather than the simplified form.

I made some progress by just looking for p.contains and matching terms that way. Will need to add some optionality into the mix but essentially

p3=p.product(p.integer,p.exponent(p.literal(`x`),p.integer.satisfies(`x=3`)))
p2=p.product(p.integer,p.exponent(p.literal(`x`),p.integer.satisfies(`x=2`)))
p1=p.product(p.integer,p.literal(`x`))
p0=p.integer

then

tru=p.contains(p3).matches(this.latex) and p.contains(p2).matches(this.latex) and ...

which works fine. I can also parse out the (absolute) coefficients using the not-exactly-intuitive

val2=p2.parse(p.contains(p2).parse(this.latex).term1.latex).term1.numericValue

Maybe there’s a way of tidying that up that I’m not spotting!

I looked at an example @JayChow provided for p.repeat and thought that maybe I could be clever and use something like

nump2=p.contains(p.repeat(p2)).parse(this.latex).term1.n

to identify how many occurences there are of p2 (bx^2) and reject if it’s >1. However, including this seems to break the pattern matching for some reason - an expression that marks as true when I don’t have that parsing in place, marks as false when I do. I don’t know if this is a bug or intended or I’ve misunderstood that particular pattern.

For now, though, I think we have a semi-solution.

4

Yes, I’m reviving this topic to see if there’s a way to check if the entered input is a polynomial in a standard form (Here it is assumed that a polynomial is considered in standard form when it is arranged with descending order of the degree of each term). I tried all the different kinds of pattern match that I knew but how to check for the correct order? Thanks

6

Here’s how I’d go about it after a few more years experience (link). The obvious shortcoming is having to define up to the number of expected terms.

Notable pattern matching usages:

  • p.optional() allows parts to be omitted. Here, for the coefficient of terms, and the term itself.
  • .satisfies() basically allows a restriction (as you would in the graph), but only works for p.integer and p.number. You can get pretty dynamic and creative with it (e.g. accepting any of a list of numbers, or numbers divisible by a number).
  • .allowNegativeTerms: As it sounds. p.sum and p.product default to positive terms only.
  • .strictOrder: Default for patterns is any order. This forces the order of the pattern.
1 Like
7

Ah! The many things patterns can do! Thanks a lot for the explanation and the link with a working example! The only catch is that the linear term forces you to enter x^1 but that can easily be fixed by anyOf or Optional pattern types. I wish we had a more robust documentation for the many wonders pattern matching can do! Many thanks for taking some time out to look into this!

8

Good catch! I updated it to use formatLatex() instead which will strip out unnecessary coefficients or exponents of 1 and addends of 0, making the need for .anyOf() or .optional() unneeded for that term!

I didn’t edit, but also thinking you may want to add .strictOrder to each term as well to ensure coefficients are written first. Patterns can be a rabbit hole sometimes, but very powerful!

1 Like
9

Oh Yes! I use formatLatex at many places but it didn’t occur to me to bring it here! Thanks again for its use case here as well as the .strictOrder for coefficients! I am sharing one example for you to look at my CL codes and fix few broken pieces of it here and there and eventually improve it to achieve efficiency (if and when you get a chance!) in writing minimum lines of codes. Somewhat similar to when we had #MatchMyCL back in the days, can we start something like #ImproveMyCL? Thanks for all you do to support this!

1 Like
10

Honestly I enjoyed this and it helps highlight some interesting features of patterns. This is a nice challenge to improve, and recommend others check it out first before looking at my own solution here.

I commented out your original after my updates so it’s easier to compare, and left some notes. One notable misconception I had regards p.product, which is that “product” indicates multiplication of two or more factors, but in CL a product can be a single factor! That was the first notable efficient fix to clean out all the .anyOf()'s. Enjoy! And thanks for sharing!

11

An afterthought to clarify. Whenever using .term1 (or any up to term10), that refers to the term number in the defined pattern, and not the order of the input.

1 Like