CODEWITHSUNDEEP
haskell
Bob
Bob

Reputation: 49

derivation function in haskell

I want actually undestand what is happening in this code. Can someone tell me what it's the main idea. I get that is derivation of a polynom. But I don't know what derN xs 1 , derN xs (n+1) and derN xs 0 actually do

derN :: P -> Int -> P
derN [] n = []


derPolinom :: P -> P
derPolinom xs = derN xs 0

Upvotes: 1

Views: 709

Answers (2)

Jon Purdy
Jon Purdy

Reputation: 55019

Maybe it would help to work through an example. It looks like you have a definition like type P = [Int], so I’ll assume that. Let’s take the polynomial 3x2 + 5x + 7, which would be represented in this scheme as [7, 5, 3].

To compute the derivative of this polynomial, we start with derPolynom:

derPolinom [7, 5, 3]
=
derN [7, 5, 3] 0

So we just call derN. We find the first case that matches:

derN (x:xs) 0 = derN xs 1

Then x is 7 and xs is [5, 3], so we substitute those values into the body:

derN [5, 3] 1

We’ve arrived at another call, so we find the case that matches:

derN (x:xs) n = [n * x] ++ derN xs (n+1)

This time, x is 5, xs is [3], and n is 1. Again substitute:

[1 * 5] ++ derN [3] (1 + 1)
=
[5] ++ derN [3] 2

Now we have another recursive call, which matches the same pattern, binding x = 3, xs = [], and n = 2:

[5] ++ ([2 * 3] ++ derN [] (2 + 1))
[5] ++ ([6] ++ derN [] 3)

Finally we’ve reached the base case of the recursion:

derN [] n = []

So we perform our last substitution:

[5] ++ ([6] ++ [])

Then reduce to get an answer of [5, 6], which represents the polynomial 6x + 5, which is indeed the derivative of 3x2 + 5x + 7.

You’ll notice that we’re only ever prepending single-element lists, so this line:

derN (x:xs) n = [n * x] ++ derN xs (n+1)

Could be simplified into this:

derN (x:xs) n = n * x : derN xs (n+1)

This whole function could also be written more simply using a higher-order function to avoid having to write out the recursion explicitly. We can use drop to remove the last coefficient and zipWith (*) [1..] to multiply each remaining number in the list by its 1-based index (which indicates the exponent).

derPolinom xs = zipWith (*) [1..] (drop 1 xs)

Upvotes: 1

bipll
bipll

Reputation: 11940

Those are recursive calls. For instance, derN (x:xs) 0 = derN xs 1 should be read as "The derivative of a polynom, with x as a free member and xs as other coefficients, is the same as derivative of a polynom with coefficients xs, starting with power 1".

This procedure takes the list of coefficients of a polynom and builds the list of coefficients of its derivative, recursively traversing from the lowest power to the highest.

Upvotes: 0

Related Questions