F# Polynomial Derivator

Question

I'm writing a program that takes a polynomial and returns its derivative. The polynomial is passed as predefined type "poly", which is a list of tuples in which the first element is a float representing a coefficient, and the second is an integer representing the degree of that term. So a poly p = [(2.0, 3);(1.5,2);(3.2;1)] would represent 2x^3 + 1.5x^2 + 3.2x^1. My code is as follows:

let rec diff (p:poly):poly = 
  match p with
    | [] -> raise EmptyList
    | [a]-> (fst a * snd a, snd a - 1)
    | x::xs -> ((fst x * snd x), (snd x - 1)) :: diff xs

The error I'm getting tells me that the program expects the function to return a type poly, but here has the type 'a * 'b. I don't see why thats the case, when in my base case I return a tuple and in all other situations I'm appending onto an accumulating list. I've played around with the brackets, to no avail. Why is my code tossing this error?

All input is appreciated on the matter.

Answer 1

you said it yourself: in the base case you are returning a tuple not a list - so the inference thinks this is what you want

Just change it into:

let rec diff (p:poly):poly = 
  match p with
    | [] -> raise EmptyList
    | [a]-> [fst a * snd a, snd a - 1]
    | x::xs -> ((fst x * snd x), (snd x - 1)) :: diff xs

and it should be fine (just replace the (..) with [..] ;) )

remember: :: will cons a new head onto a list

---

there are a few issues with float vs. int there so I would suggest this (using recursion):

type Poly = (float*int) list

let test : Poly =  [(2.0, 3);(1.5,2);(3.2,1);(1.0,0)]

let rec diff (p:Poly):Poly = 
    match p with
    | [] -> []
    | x::xs -> (fst x * float (snd x), snd x - 1) :: diff xs

which is really just this:

let diff : Poly -> Poly = 
    List.map (fun x -> fst x * float (snd x), snd x - 1)

and can look a lot nicer without fst and snd:

let diff : Poly -> Poly = 
    List.map (fun (a,p) -> a * float p, p - 1)