[Haskell-cafe] "Natural" polymorphism for n*(n+1)/2

[Tom Smeding]

That has n :: Integer, not n :: a, right?

@Douglas:

What about the ring of polynomials over the integers, i.e. Z[X]? We can certainly define a Num instance for that if we set 'signum _ = 1' and 'abs = id'. 'fromInteger' then injects constant polynomials.

However, if 'n' is X + 1, then n*(n+1) is X^2 + 3X + 2; what's that divided by 2? Not well-defined, since we were talking about polynomials over the integers.

If your function is to have type Num a => a -> a, it will need to handle this case, but I don't see a way in which it can.

- Tom

P.S. Unless, of course, you allow extra typeclasses; other posters have already suggested (inefficient) versions for Ord and Enum.

-------- Original Message --------

On 16 Dec 2020, 23:13, Jaro Reinders < jaro.reinders at gmail.com> wrote:

Num alone is enough: sum [1..n] = sum (map fromInteger [1..n])

On 12/16/20 11:07 PM, MigMit wrote:

> Num + Enum would be enough though, since n*(n+1)/2 = sum [1..n], n*(n+1)*(n+2)/6 = sum (map (\m -> sum [1..m]) [1..n]) etc. Not quite effective, of course.

>

>> On 16 Dec 2020, at 22:57, David Feuer <david.feuer at gmail.com> wrote:

>>

>> I very much doubt that Num a is sufficient. That's not even enough to check whether a number is even. You can certainly perform the calculation with `Integral a`, but you'll have to apply some external reasoning to see that the result is correct.

>>

>> On Wed, Dec 16, 2020, 4:45 PM M Douglas McIlroy <m.douglas.mcilroy at dartmouth.edu> wrote:

>> Some nominally rational functions, e.g n*(n+1)/2,

>> yield integer values for integer arguments. I seek

>> either a way to wrap such a function so it has type

>> Num a => a->a or a convincing argument that it can't

>> be done.

>>

>> Doug

>> _______________________________________________

>> Haskell-Cafe mailing list

>> To (un)subscribe, modify options or view archives go to:

>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

>> Only members subscribed via the mailman list are allowed to post.

>> _______________________________________________

>> Haskell-Cafe mailing list

>> To (un)subscribe, modify options or view archives go to:

>> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

>> Only members subscribed via the mailman list are allowed to post.

>

> _______________________________________________

> Haskell-Cafe mailing list

> To (un)subscribe, modify options or view archives go to:

> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

> Only members subscribed via the mailman list are allowed to post.

>

_______________________________________________

Haskell-Cafe mailing list

To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Only members subscribed via the mailman list are allowed to post.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20201216/c9dd28e6/attachment.html>