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. |
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-cafe Only members subscribed via the mailman list are allowed to post. |
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, _______________________________________________ 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. |
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-cafe Only members subscribed via the mailman list are allowed to post. |
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-cafe Only members subscribed via the mailman list are allowed to post. |
In reply to this post by migmit-2
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 <[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-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. |
A small optimization, maybe: fromInteger ((n * (n+1)) `div` 2)?
> On 16 Dec 2020, at 23:13, Jaro Reinders <[hidden email]> 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 <[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-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. |
In reply to this post by Jaro Reinders
That has n :: Integer, not n :: a, right?
_______________________________________________ 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. |
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-cafe Only members subscribed via the mailman list are allowed to post. |
I'm not sure what "sound" means if the documentation[1] for Num states that the only reasonable expectation is that of a ring.
_______________________________________________ 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. |
On Wed, 16 Dec 2020, Tom Smeding wrote: > I'm not sure what "sound" means if the documentation[1] 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-cafe Only members subscribed via the mailman list are allowed to post. |
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-cafe Only members subscribed via the mailman list are allowed to post. |
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?
_______________________________________________ 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. |
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-cafe Only members subscribed via the mailman list are allowed to post. |
Good point, that would allow the original, desired function to be written 'f :: Num a => a -> a; f n = abs (n * (n + 1))'. However, that doesn't do the right thing when 'a' is Int or Float.
_______________________________________________ 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. |
In reply to this post by Henning Thielemann
here's why it cannot be done: data TwoByTwoMatrix = TTM Integer Integer Integer Integer instance Num TwoByTwoMatrix where fromInteger i = TTM i 0 0 i (TTM a b c d) + (TTM e f g h) = TTM (a+e) (b+f) (c+g) (d+h) negate m = (fromInteger (-1)) * m (TTM a b c d) * (TTM e f g h) = TTM (b*g+a*e) (a*f+b*h) (d*g+c*e) (c*f+d*h) It should follow that the above is a (non-abelian) ring, as required (all definitions follow the standard matrix addition/multiplication/addition convensions). n = (TTM 0 1 0 0) then: n * (n + 1) = n. Since n has odd entries, it cannot be divided by 2 (more precisely: we cannot find an m s.t. n * 2 = m). Best, Sebastiaan On Wed, Dec 16, 2020 at 6:14 PM Henning Thielemann <[hidden email]> wrote:
_______________________________________________ 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. |
Free forum by Nabble | Edit this page |