|| CSE 341 Spring 2002
|| Assignment 2
|| TA Sample Solution
|| Ken Yasuhara <yasuhara@cs>


||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| perfect numbers

|| returns (theoretically) infinite list of perfect numbers
|| A perfect number is the sum of its factors (excluding itself).
|| Helper factor_set takes a number and returns a list of its factors
|| (itself excluded).
perfect_nos 
  = [ p | p <- [6..]; p = sum (factor_set p) ]
    where
    factor_set k = 
      [ factor | factor <- [1..(n/2)]; k mod factor = 0 ]


||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| provided code for polynomial multiplication

|| code only modified with addition of this case for function parse
||   parse (N 0 : rest) = parse rest 

|| This includes all the type definitions you'll need, plus the 
|| input function string2poly that takes string and turns it into 
|| the internal representation 'poly' for polynomials.


|| For convenience, define the type alias 'string'
string == [char]

|| Data types for scanner
token ::= N num | X | Hat | Times | Plus | Minus

|| data types for polynomials
|| a polynomial is represented as a list of (coefficient, exponent) terms
|| a pterm is a term in a polynomial, consisting of a coefficient and 
|| an exponent 
pterm ::= Term num num   

|| poly is a type synomym for a list of pterms 
poly == [pterm]


|| Here is the top-level function 'multiply', which multiplies two polynomials 
|| (represented as strings)
multiply :: string->string->string
multiply p q = poly2string (polymult (string2poly p) (string2poly q))

|| This function converts a properly-formed input string into a polynomial.
|| You shouldn't need to modify the definition of this function.
string2poly :: string->poly
string2poly p = parse (polyscan p)

|| polyscan is a helper function for string2poly that takes a string 
|| and turns it into a list of tokens.
polyscan :: string->[token]
polyscan [] = []
polyscan (c:cs) = polyscan cs, if c=' '
                = X : polyscan cs, if c='x'
                = Times : polyscan cs, if c='*'
                = Plus : polyscan cs, if c='+'
                = Minus : polyscan cs, if c='-'
                = Hat : polyscan cs, if c='^'
                = scannum (c:cs), if digit c
                = error "bad input to polyscan", otherwise

|| another helper function, that scans numbers from an input string
scannum :: string->[token]
scannum s = N (numval digits) : polyscan rest
            where
            (digits,rest) = getdigits s

getdigits "" = ("","")
getdigits (c:cs) = (c:moredigits,rest), if digit c
                 = ("",(c:cs)), otherwise
                   where
                   (moredigits,rest) = getdigits cs


|| the parse function takes a list of tokens and parses it into a polynomial
parse :: [token]->poly

parse [] = []

parse (Plus : N c : Times : X : rest) = Term c exp : parse tokens
                                        where
                                        (exp,tokens) = get_exp rest

parse (Minus : N c : Times: X : rest) = Term (-c) exp : parse tokens
                                        where
                                        (exp,tokens) = get_exp rest


parse (N c : Times: X : rest) = Term c exp : parse tokens
                                where
                                (exp,tokens) = get_exp rest

parse (Plus : X : rest) = Term 1 exp : parse tokens
                          where
                          (exp,tokens) = get_exp rest

parse (Minus : X : rest) = Term (-1) exp : parse tokens
                           where
                           (exp,tokens) = get_exp rest

parse (X : rest) = Term 1 exp : parse tokens
                   where
                   (exp,tokens) = get_exp rest

parse (Plus : N c : rest) = Term c 0 : parse rest
parse (Minus : N c : rest) = Term (-c) 0 : parse rest
parse (N 0 : rest) = parse rest  || added case to handle "0" polynomial
parse (N c : rest) = Term c 0 : parse rest


get_exp (Hat : N exp : rest) = (exp,rest)
get_exp rest = (1,rest)


||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| added code for polynomial-to-string conversion

|| converts poly (list of pterms) into string representation
poly2string :: poly->string
poly2string [] = "0"
poly2string (first:rest)
  = (leadingpterm2string first) ++ (concat (map nonleadingpterm2string rest))

|| converts a single term into string representation, treating it as a
|| leading term, e.g.,
||   leadingpterm2string (Term (-2) 4) => "-2*x^4"
||   leadingpterm2string (Term 2 4) => "2*x^4"
leadingpterm2string :: pterm->string
leadingpterm2string (Term coeff exp)
  = optionalminus ++ pterm2stringunsigned (Term coeff exp)
    where
    optionalminus
      = "-", if coeff < 0
      = "", if coeff > 0
      = error "zero coeff in leadingpterm2string", otherwise
      
|| converts a single term into string representation, treating it as a
|| nonleading term, e.g.,
||   leadingpterm2string (Term (-2) 4) => " - 2*x^4"
||   leadingpterm2string (Term 2 4) => " + 2*x^4"
nonleadingpterm2string :: pterm->string
nonleadingpterm2string (Term coeff exp)
  = paddedsign ++ pterm2stringunsigned (Term coeff exp)
    where 
    paddedsign 
      = " + ", if coeff > 0
      = " - ", if coeff < 0
      = error "zero coeff in nonleadingpterm2string", otherwise

|| takes a pterm and returns string representation w/ sign of
|| coeff. dropped, e.g., 
||   pterm2stringunsigned (Term (-2) 4) => "2*x^4"
|| for coeff. of 1 or -1, '1' not included unless term degree is 0
|| x included only for terms of degree higher than 0
|| ^ and exponent included only for terms of degree higher than 1
pterm2stringunsigned :: pterm->string
pterm2stringunsigned (Term coeff exp)  
  = coeffpart ++ xpart
    where 
    coeffpart
      = shownum (abs coeff), if (abs coeff) ~= 1 \/ exp = 0
      = "", otherwise
    xpart 
      = optionalstar ++ "x^" ++ shownum exp, if exp > 1
      = optionalstar ++ "x", if exp = 1
      = "", if exp = 0
      = error "negative exponent in pterm2string", if exp < 0
        where 
        optionalstar = "*", if (abs coeff) ~= 1
                     = "", otherwise


||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| added code for polynomial multiplication

|| takes two polys and returns product as poly
|| simply wraps call to sortedpolymult, which assumes sorted arguments
polymult :: poly->poly->poly
polymult p1 p2 = sortedpolymult (polysort p1) (polysort p2)

|| same as polymult but assumes input polynomials are sorted in
|| decreasing degree order (see polysort)
|| recursion based on algebraic transformation as in this example:
||   (term1 + term2 + term3)(term4 + term5) 
||   term1(term4 + term5) + (term2 + term3)(term4 + term5)
||   term1(term4 + term5) + term2(term4 + term5) + term3(term4 + term5)
sortedpolymult :: poly->poly->poly
sortedpolymult p1 [] = []  || (this case not strictly necessary)
sortedpolymult [] p2 = []
sortedpolymult (firstterm:rest) p2 
  = polyadd (map (termmult firstterm) p2) (sortedpolymult rest p2)

|| adds two polynomials together; linear time merge
|| assumes sorted order (see polysort)
|| assumes, in each polynomial, no more than one term per degree, 
||   i.e., assumes polynomial is already simplified
polyadd :: poly->poly->poly
polyadd p1 [] = p1
polyadd [] p2 = p2
polyadd ((Term coeff1 sameexp):rest1) ((Term coeff2 sameexp):rest2) 
    || case where highest degree terms have same degree
  = (Term (coeff1 + coeff2) sameexp) : (polyadd rest1 rest2), 
    if (coeff1 + coeff2) ~= 0
  = polyadd rest1 rest2, otherwise  || omit result if zero
polyadd ((Term coeff1 exp1):rest1) ((Term coeff2 exp2):rest2)   
    || case where highest degree terms have different degree 
  = (Term coeff1 exp1) : (polyadd rest1 ((Term coeff2 exp2):rest2)),
    if exp1 > exp2
  = (Term coeff2 exp2) : (polyadd ((Term coeff1 exp1):rest1) rest2),
    otherwise

|| takes two terms and returns product
|| assumes both exponents are nonnegative
termmult :: pterm->pterm->pterm
termmult (Term coeff1 exp1) (Term coeff2 exp2)
  = Term (coeff1 * coeff2) (exp1 + exp2)

|| takes two pterms and returns true iff first term is lower order
|| than second term
ptermlt :: pterm->pterm->bool
ptermlt (Term coeff1 exp1) (Term coeff2 exp2)
  = exp1 < exp2

|| sorts polynomial in descending term order; uses quicksort w/ first
|| term chosen as pivot
polysort :: poly->poly
polysort [] = []
polysort (pivot:rest) 
  = higherorder ++ [pivot] ++ lowerorder
    where                                                               
    higherorder = polysort [ term | term <- rest; ~(ptermlt term pivot) ]
    lowerorder = polysort [ term | term <- rest; ptermlt term pivot ]


||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| testing constants

p1 = string2poly "-2*x^3 - x^4"
p2 = string2poly "x + 3"
p3 = string2poly "5*x^7 + 3*x^2 - x"
p4 = string2poly "-4*x^7 + 2*x^3 - 3*x^2 - x - 1"

unsortedp1 = string2poly "5*x^1 + 3*x^2 - x^7 - 2"


||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|| testing

|| very basic testing of poly2string
test1 
  = "passed:  string2poly (poly2string unsortedp1) = unsortedp1", 
    if string2poly (poly2string unsortedp1) = unsortedp1
  = "failed", otherwise

||
|| series of multiply tests based on examples given in problem 
||

|| "x^4 - 1"
extest1  
  = multiply "x^3 + x^2 + x + 1" 
             "x - 1"

|| "0"
extest2  
  = multiply "-3*x^3 + x + 5" 
             "0"

|| "-5*x^3 - 5*x + 5"
extest3  
  = multiply "x - 1 + x^3" 
             "-5"

|| "-10*x^10001 + 100*x^10000 + 5*x^9999 + 10*x^9 - 100*x^8 + ...
|| ... 5*x^7 - 100*x^6 - 5*x^5 - 10*x^3 + 70*x^2 + 305*x + 15"
extest4
  = multiply "-10*x^2 + 100*x + 5" 
             "x^9999 - x^7 - x^5 + x + 3"
