# "Natural" polymorphism for n*(n+1)/2 Classic List Threaded 16 messages Open this post in threaded view
|

## "Natural" polymorphism for n*(n+1)/2

 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-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 On Wed, 16 Dec 2020, M Douglas McIlroy 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. Num will be difficult, but with Integral class you could use 'div'. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 In reply to this post by M Douglas McIlroy 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 <[hidden email]> 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-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 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 <[hidden email]> 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 <[hidden email]> 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-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 On Wed, 16 Dec 2020, 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. You could also use Num + Ord and do:    sum \$ takeWhile (<=n) \$ iterate (1+) 1 _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 On Wed, 16 Dec 2020, Tom Smeding wrote: > @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. I also thought about polynomials, but Num is a Ring plus 'signum' and 'abs'. Are your definitions ob 'signum' and 'abs' sound? Are there other sound definitions that may allow the n*(n+1)/2 magic? _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 I'm not sure what "sound" means if the documentation for Num states that the only reasonable expectation is that of a ring.However, if we are to have laws for signum and abs, then I would expect that 'abs n = n * signum n'. My definitions satisfy that law.Furthermore for polynomials, I don't think there is a useful definition of 'abs' where 'abs n' has a higher degree than 'n' itself. Assuming that 'abs' does not increase the degree, I don't think there are any other _useful_ definitions of abs and signum than the ones I gave: multiplication in Z[X] will never decrease the degree, so the degree of 'n * signum n' is at least that of 'n', and therefore the degree of 'abs n' is the same as that of 'n'; therefore 'signum n' is a constant polynomial (without X'es). With that restriction the only reasonable choice I see is 'signum = const 1'.But even if you take 'abs' and 'signum' to be absolutely wild functions, to be able to write n*(n+1)/2 you need to define your division operator. There is certainly not one in base that will work for 'Int -> Int' as well as 'Float -> Float' as well as 'Poly Integer -> Poly Integer'. And in particular not abs nor signum. :)- Tom: https://hackage.haskell.org/package/base-4.14.1.0/docs/Prelude.html#t:Num-------- Original Message --------On 16 Dec 2020, 23:26, Henning Thielemann < [hidden email]> wrote:On Wed, 16 Dec 2020, Tom Smeding wrote:> @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.I also thought about polynomials, but Num is a Ring plus 'signum' and'abs'. Are your definitions ob 'signum' and 'abs' sound? Are there othersound definitions that may allow the n*(n+1)/2 magic?_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 On Wed, 16 Dec 2020, Tom Smeding wrote: > I'm not sure what "sound" means if the documentation for Num states that the only reasonable expectation is > that of a ring. > > However, if we are to have laws for signum and abs, then I would expect that 'abs n = n * signum n'. My > definitions satisfy that law. What about abs x = x/2 and signum _ = 2? Would satisfy your law and solve the problem of the original poster. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 In reply to this post by migmit-2 Ah, my mistake. n has to have the given type a and not Integer of course._______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 In reply to this post by Henning Thielemann You say 'abs x = x/2', but what's that (/)? For example, what is 'abs' supposed to give when called on (the representation of) the polynomial X^2 + 3X + 2?Interesting also to think about what the meaning of 'n*(n+1)/2' on polynomials should even be. What is the sum of the numbers (polynomials?) from 1 to X + 1?- Tom-------- Original Message --------On 16 Dec 2020, 23:48, Henning Thielemann < [hidden email]> wrote:On Wed, 16 Dec 2020, Tom Smeding wrote:> I'm not sure what "sound" means if the documentation for Num states that the only reasonable expectation is> that of a ring.>> However, if we are to have laws for signum and abs, then I would expect that 'abs n = n * signum n'. My> definitions satisfy that law.What about abs x = x/2 and signum _ = 2?Would satisfy your law and solve the problem of the original poster._______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.
Open this post in threaded view
|

## Re: "Natural" polymorphism for n*(n+1)/2

 On Wed, 16 Dec 2020, Tom Smeding wrote: > You say 'abs x = x/2', but what's that (/)? For example, what is 'abs' > supposed to give when called on (the representation of) the polynomial > X^2 + 3X + 2? I meant it this way: instance (Fractional a) => Num (Polynomial a) where     abs = fmap (/2) _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafeOnly members subscribed via the mailman list are allowed to post.