Re: [Haskell-cafe] adding the elements of two lists
On Sun, Mar 25, 2012 at 5:06 AM, Michael Snoyman mich...@snoyman.com wrote:
On Sun, Mar 25, 2012 at 2:01 PM, TP paratribulati...@free.fr wrote:
Hello,
My primary problem may be reduced to adding elements of two lists:
[1,2,3] + [4,5,6] = [5,7,9]
My first idea was to declare a list of Int as an instance of Num, and define
(+)
in the correct way.
However, it seems it is not possible to do that:
---
instance Num [Int] where
l1 + l2 =
---
Why?
It seems it is necessary to do:
--
newtype ListOfInt = ListOfInt { getList :: [Int] }
deriving (Show, Eq)
instance Num ListOfInt where
l1 + l2 = ...
---
Am I correct? Is it the best way to do that?
Now, what is the most usual way to implement l1+l2?
I have just read about applicative functors, with which I can do:
---
import Control.Applicative
let l1 = [1,2,3]
let l2 = [4,5,6]
print $ getZipList $ (+) $ ZipList l1 * ZipList l2
[5,7,9]
---
Is it the correct way to do that?
I have tried:
---
instance Num ListOfInt where
l1 + l2 = ListOfInt $ getZipList $ (+) $ ZipList (getList l1) *
ZipList (getList l2)
---
Isn't it too much complicated?
Thanks
TP
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
A simple solution is to use the zipWith[1] function:
zipWith (+) [1,2,3] [4,5,6] == [5,7,9]
It takes a bit of time to get acquainted with all of the incredibly
convenient functions in base, but once you know them, it can greatly
simplify your code.
Michael
Not knowing zipWith, I usually write
map (uncurry (+)) (zip [1,2,3] [4,5,6])
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Richard O'Keefe o...@cs.otago.ac.nz writes: newtype PS a = PS [a] deriving (Eq, Show) u f (PS x)= PS $ map f x b f (PS x) (PS y) = PS $ zipWith f x y to_ps x = PS (x : repeat 0) BTW, isn't this a good candidate for an Applicative instance (similar to ZipList)? u f p = f $ p -- or u = fmap b f p1 p2 = f $ p1 * p2 Not a big deal for the Num instance, perhaps, but more general than u and b, and it might make it easier to work with in other ways. -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
From: Richard O'Keefe o...@cs.otago.ac.nz Date: Thu, 29 Mar 2012 16:34:46 +1300 On 29/03/2012, at 3:08 PM, Doug McIlroy wrote: - without newtype toSeries f = f : repeat 0 -- coerce scalar to series instance Num a = Num [a] where (f:fs) + (g:gs) = f+g : fs+gs (f:fs') * gs@(g:gs') = f*g : fs'*gs + (toSeries f)*gs' - with newtype newtype Num a = PS a = PS [a] deriving (Show, Eq) fromPS (PS fs) = fs -- extract list toPS f = PS (f : repeat 0) -- coerce scalar to series instance Num a = Num (PS a) where (PS (f:fs)) + (PS (g:gs)) = PS (f+g : fs+gs) (PS (f:fs)) * gPS@(PS (g:gs)) = PS $ f*g : fromPS ((PS fs)*gPS + (toPS f)*(PS gs)) Try it again. newtype PS a = PS [a] deriving (Eq, Show) u f (PS x)= PS $ map f x b f (PS x) (PS y) = PS $ zipWith f x y to_ps x = PS (x : repeat 0) ps_product (f:fs) (g:gs) = whatever instance Num a = Num (PS a) where (+) = b (+) (-) = b (-) (*) = b ps_product negate = u negate abs = u abs signum = u signum fromInteger = to_ps . fromInteger I've avoided defining ps_product because I'm not sure what it is supposed to do: the definition doesn't look commutative. You have given the Hadamard product--a construction with somewhat esoteric properties. The product I have in mind is the ordinary mathematical product that one meets in freshman calculus. The distributive law yields this symmetric formulation (f:fs) * (g:gs) = f*g : (toSeries f)*gs + fs*(toSeries g) + (0 : fs*gs) The version I gave is an optimization (which I learned from Jerzy). For more explanation see www.cs.dartmouth.edu/~doug/powser.html. I like the lifting functions b and u, but they don't get one very far. The product is where the PS pox begins to bite badly. I would welcome a perspicuous formulation of that using newtype. Incidentally, a more efficient way to write the symmetric product is (f:fs) * (g:gs) = f*g : zipWith (f*) gs + zipWith fs (*g) + (0 : fs*gs) toSeries and zipWith appear in the formulas because Haskell overloading won't let one use the multiplication symbol for both series*series and scalar*series. One might also invent a distinct operator for the purpose. Coercion with toSeries strikes me as the least jarring of these approaches. zipWith suffers from mixing levels of abstraction--it signifies not the idea of multiplication, but the algorithm. A new operator would suffer both from unfamiliarity and lack of commutativity. The code suffers a pox of PS. But it doesn't *need* to. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On 29 March 2012 04:34, Richard O'Keefe o...@cs.otago.ac.nz wrote: u f (PS x)= PS $ map f x b f (PS x) (PS y) = PS $ zipWith f x y to_ps x = PS (x : repeat 0) Also see: http://hackage.haskell.org/package/newtype -- Ozgur Akgun ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Date: Tue, 27 Mar 2012 11:03:54 +1300 From: Richard O'Keefe o...@cs.otago.ac.nz Subject: Re: [Haskell-cafe] adding the elements of two lists To: jerzy.karczmarc...@unicaen.fr Cc: haskell-cafe@haskell.org And *that* is why I stopped trying to define instance Num t = Num [t]. If I KNEW that the length of the lists is ... fixed ... then the type wasn't *really* [t], but some abstract type that happened to be implemented as [t], and that abstract type deserved a newtype name of its own. Naming the type - makes the author's intent clearer to readers - lets the compiler check it's used consistently - lets you have instances that don't match instances for other abstract types that happen to have the same implementation - provides a natural place to document the purpose of the type - gives you a way to enforce the intended restrictions all for zero run-time overhead. Quite taken by this manifesto for high style and morality, I resolved to do right by some old code, of which I had been quite proud: www.cs.dartmouth.edu/~doug/powser.html. Sadly, the exercise took some bloom off the rose. What the code gained in honesty and safety, it lost in beauty and readability. Here's the contrast, seen in overloading arithmetic to handle addition and multiplication of power series. - without newtype toSeries f = f : repeat 0 -- coerce scalar to series instance Num a = Num [a] where (f:fs) + (g:gs) = f+g : fs+gs (f:fs') * gs@(g:gs') = f*g : fs'*gs + (toSeries f)*gs' - with newtype newtype Num a = PS a = PS [a] deriving (Show, Eq) fromPS (PS fs) = fs -- extract list toPS f = PS (f : repeat 0) -- coerce scalar to series instance Num a = Num (PS a) where (PS (f:fs)) + (PS (g:gs)) = PS (f+g : fs+gs) (PS (f:fs)) * gPS@(PS (g:gs)) = PS $ f*g : fromPS ((PS fs)*gPS + (toPS f)*(PS gs)) The code suffers a pox of PS. When one goes on to introduce efficiencies and generalize to handle finite series (polynomials), it only gets worse. One unpleasant technical problem: the deriving clause is almost useless--one can't print or detect equality of infinite objects. For output one must apply something like (take 10 . fromPS). Yet this modest package would likely pose problems if it were combined with others in a grander suite for automated mathematics. What to do? I think I might write the package without newtype, and then wrap it in PS for export in hopes of exploiting the advantages of both styles. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On 29/03/2012, at 3:08 PM, Doug McIlroy wrote: - without newtype toSeries f = f : repeat 0 -- coerce scalar to series instance Num a = Num [a] where (f:fs) + (g:gs) = f+g : fs+gs (f:fs') * gs@(g:gs') = f*g : fs'*gs + (toSeries f)*gs' - with newtype newtype Num a = PS a = PS [a] deriving (Show, Eq) fromPS (PS fs) = fs -- extract list toPS f = PS (f : repeat 0) -- coerce scalar to series instance Num a = Num (PS a) where (PS (f:fs)) + (PS (g:gs)) = PS (f+g : fs+gs) (PS (f:fs)) * gPS@(PS (g:gs)) = PS $ f*g : fromPS ((PS fs)*gPS + (toPS f)*(PS gs)) Try it again. newtype PS a = PS [a] deriving (Eq, Show) u f (PS x)= PS $ map f x b f (PS x) (PS y) = PS $ zipWith f x y to_ps x = PS (x : repeat 0) ps_product (f:fs) (g:gs) = whatever instance Num a = Num (PS a) where (+) = b (+) (-) = b (-) (*) = b ps_product negate = u negate abs = u abs signum = u signum fromInteger = to_ps . fromInteger I've avoided defining ps_product because I'm not sure what it is supposed to do: the definition doesn't look commutative. The code suffers a pox of PS. But it doesn't *need* to. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Le 26/03/2012 02:41, Chris Smith a écrit : Of course there are rings for which it's possible to represent the elements as lists. Nevertheless, there is definitely not one that defines (+) = zipWith (+), as did the one I was responding to. What? The additive structure does not define a ring. The multiplication can be a Legion, all different. Over. Jerzy K ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
This is interesting because it seems to be a counterexample to the claim that you can lift any Num through an Applicative (ZipList, in this case). It seems like maybe that only works in general for monoids instead of rings? On Mar 25, 2012 8:43 PM, Chris Smith cdsm...@gmail.com wrote: Jerzy Karczmarczuk jerzy.karczmarc...@unicaen.fr wrote: Le 26/03/2012 01:51, Chris Smith a écrit : instance (Num a) = Num [a] where xs + ys = zipWith (+) xs ys You can do this in the sense that it's legal Haskell... but it is a bad idea [...] It MIGHT be a ring or not. The real problem is that one should not confuse structural and algebraic (in the classical sense) properties of your objects. Of course there are rings for which it's possible to represent the elements as lists. Nevertheless, there is definitely not one that defines (+) = zipWith (+), as did the one I was responding to. By the time you get a ring structure back by some *other* set of rules, particularly for multiplication, the result will so clearly not be anything like a general Num instance for lists that it's silly to even be having this discussion. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Jerzy Karczmarczuk jerzy.karczmarc...@unicaen.fr wrote: Le 26/03/2012 02:41, Chris Smith a écrit : Of course there are rings for which it's possible to represent the elements as lists. Nevertheless, there is definitely not one that defines (+) = zipWith (+), as did the one I was responding to. What? The additive structure does not define a ring. The multiplication can be a Legion, all different. I'm not sure I understand what you're saying there. If you were asking about why there is no ring on [a] that defines (+) = zipWith (+), then here's why. By that definition, you have [1,2,3] + [4,5] = [5,7]. But also [1,2,42] + [4,5] = [5,7]. Addition by [4,5] is not one-to-one, so [4,5] cannot be invertible. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Le 26/03/2012 16:31, Chris Smith a écrit : If you were asking about why there is no ring on [a] that defines (+) = zipWith (+), then here's why. By that definition, you have [1,2,3] + [4,5] = [5,7]. But also [1,2,42] + [4,5] = [5,7]. Addition by [4,5] is not one-to-one, so [4,5] cannot be invertible. So, * the addition* is not invertible, why did you introduce rings to this discussion, if the additive group within is already lousy?... OK I see now. You are only interested in the explicitly ambiguous usage of the element-wise addition which terminates at the shortest term... But I don't care about using (+) = zipWith (+) anywhere, outside of a programming model / framework, where you keep the sanity of your data. In my programs I KNEW that the length of the list is either fixed, or of some minimal size (or infinite). Your [4,5] simply does not belong to MY rings, if I decided to keep the other one. Jerzy K. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On Mon, Mar 26, 2012 at 10:18 AM, Jerzy Karczmarczuk jerzy.karczmarc...@unicaen.fr wrote: So, * the addition* is not invertible, why did you introduce rings ... My intent was to point out that the Num instance that someone suggested for Num a = Num [a] was a bad idea. I talked about rings because they are the uncontroversial part of the laws associated with Num: I think everyone would agree that the minimum you should expect of an instance of Num is that its elements form a ring. In any case, the original question has been thoroughly answered... the right answer is that zipWith is far simpler than the code in the question, and that defining a Num instance is possible, but a bad idea because there's not a canonical way to define a ring on lists. The rest of this seems to have devolved into quite a lot of bickering and one-ups-manship, so I'll back out now. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On 3/26/12 8:16 AM, Jake McArthur wrote: This is interesting because it seems to be a counterexample to the claim that you can lift any Num through an Applicative (ZipList, in this case). It seems like maybe that only works in general for monoids instead of rings? I'm not so sure about that. The Applicative structure of ZipLists is specifically defined for infinite lists (cf., pure = repeat). And in the case of infinite lists the (+) = zipWith(+) definition works just fine, since we don't have to worry about truncation. I wasn't aware that Num was supposed to be liftable over any Applicative, but this doesn't seem like a counterexample... -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On 27/03/2012, at 5:18 AM, Jerzy Karczmarczuk wrote: But I don't care about using (+) = zipWith (+) anywhere, outside of a programming model / framework, where you keep the sanity of your data. In my programs I KNEW that the length of the list is either fixed, or of some minimal size (or infinite). Your [4,5] simply does not belong to MY rings, if I decided to keep the other one. And *that* is why I stopped trying to define instance Num t = Num [t]. If I KNEW that the length of the lists is ... fixed ... then the type wasn't *really* [t], but some abstract type that happened to be implemented as [t], and that abstract type deserved a newtype name of its own. Naming the type - makes the author's intent clearer to readers - lets the compiler check it's used consistently - lets you have instances that don't match instances for other abstract types that happen to have the same implementation - provides a natural place to document the purpose of the type - gives you a way to enforce the intended restrictions all for zero run-time overhead. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Well, ZipList's pure is indeed repeat, but there is nothing about ZipList restricting it to infinite lists. As long as pure is repeat, I'm pretty sure any other value can still be finite without violating Applicative's laws. On Mar 26, 2012 1:02 PM, wren ng thornton w...@freegeek.org wrote: On 3/26/12 8:16 AM, Jake McArthur wrote: This is interesting because it seems to be a counterexample to the claim that you can lift any Num through an Applicative (ZipList, in this case). It seems like maybe that only works in general for monoids instead of rings? I'm not so sure about that. The Applicative structure of ZipLists is specifically defined for infinite lists (cf., pure = repeat). And in the case of infinite lists the (+) = zipWith(+) definition works just fine, since we don't have to worry about truncation. I wasn't aware that Num was supposed to be liftable over any Applicative, but this doesn't seem like a counterexample... -- Live well, ~wren __**_ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/**mailman/listinfo/haskell-cafehttp://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On Sun, Mar 25, 2012 at 2:01 PM, TP paratribulati...@free.fr wrote:
Hello,
My primary problem may be reduced to adding elements of two lists:
[1,2,3] + [4,5,6] = [5,7,9]
My first idea was to declare a list of Int as an instance of Num, and define
(+)
in the correct way.
However, it seems it is not possible to do that:
---
instance Num [Int] where
l1 + l2 =
---
Why?
It seems it is necessary to do:
--
newtype ListOfInt = ListOfInt { getList :: [Int] }
deriving (Show, Eq)
instance Num ListOfInt where
l1 + l2 = ...
---
Am I correct? Is it the best way to do that?
Now, what is the most usual way to implement l1+l2?
I have just read about applicative functors, with which I can do:
---
import Control.Applicative
let l1 = [1,2,3]
let l2 = [4,5,6]
print $ getZipList $ (+) $ ZipList l1 * ZipList l2
[5,7,9]
---
Is it the correct way to do that?
I have tried:
---
instance Num ListOfInt where
l1 + l2 = ListOfInt $ getZipList $ (+) $ ZipList (getList l1) *
ZipList (getList l2)
---
Isn't it too much complicated?
Thanks
TP
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
A simple solution is to use the zipWith[1] function:
zipWith (+) [1,2,3] [4,5,6] == [5,7,9]
It takes a bit of time to get acquainted with all of the incredibly
convenient functions in base, but once you know them, it can greatly
simplify your code.
Michael
[1]
http://hackage.haskell.org/packages/archive/base/4.5.0.0/doc/html/Prelude.html#v:zipWith
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On Sun, Mar 25, 2012 at 5:01 AM, TP paratribulati...@free.fr wrote:
Hello,
My primary problem may be reduced to adding elements of two lists:
[1,2,3] + [4,5,6] = [5,7,9]
My first idea was to declare a list of Int as an instance of Num, and
define (+)
in the correct way.
However, it seems it is not possible to do that:
---
instance Num [Int] where
l1 + l2 =
---
Why?
It seems it is necessary to do:
--
newtype ListOfInt = ListOfInt { getList :: [Int] }
deriving (Show, Eq)
instance Num ListOfInt where
l1 + l2 = ...
---
Am I correct? Is it the best way to do that?
Now, what is the most usual way to implement l1+l2?
I have just read about applicative functors, with which I can do:
---
import Control.Applicative
let l1 = [1,2,3]
let l2 = [4,5,6]
print $ getZipList $ (+) $ ZipList l1 * ZipList l2
[5,7,9]
---
Is it the correct way to do that?
I have tried:
---
instance Num ListOfInt where
l1 + l2 = ListOfInt $ getZipList $ (+) $ ZipList (getList l1) *
ZipList (getList l2)
---
Isn't it too much complicated?
Thanks
TP
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
As Michael suggests using zipWith (+) is the simplest solution.
If you really want to be able to write [1,2,3] + [4,5,6], you can define
the instnace as
instance (Num a) = Num [a] where
xs + ys = zipWith (+) xs ys
You'll also likely want to give definitions for the other functions ((*),
abs, signum, etc.) as well.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
TP : However, it seems it is not possible to do that: --- instance Num [Int] where l1 + l2 = --- Why? Why not?? It is possible. All what has been said by other people is right. But you can do it your way as well, GHC won't protest if you :set -XFlexibleInstances . (Then you might have some other small problems, but nobody is perfect). Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On 26/03/2012, at 1:01 AM, TP wrote:
Hello,
My primary problem may be reduced to adding elements of two lists:
[1,2,3] + [4,5,6] = [5,7,9]
zipWith (+) [1,2,3] [4,5,6]
gets the job done.
However, it seems it is not possible to do that:
---
instance Num [Int] where
l1 + l2 =
---
Why?
Because the 'instance' machinery is keyed off the *outermost* type
constructor (here []) not the *whole* type (here [Int]) and the
reason for that is polymorphism; we want to be able to work with
[t] where t is not specially constrained.
You *can* do
instance (Num t) = Num [t] where ...
It seems it is necessary to do:
--
newtype ListOfInt = ListOfInt { getList :: [Int] }
That's *still* a good idea because there are lots of different
things that arithmetic on lists might mean. For example,
is [1,2] + [3,4,5] an error or not? If it is not an error,
what actually happens?
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Jonathan Grochowski jongrocho...@gmail.com wrote: As Michael suggests using zipWith (+) is the simplest solution. If you really want to be able to write [1,2,3] + [4,5,6], you can define the instnace as instance (Num a) = Num [a] where xs + ys = zipWith (+) xs ys You can do this in the sense that it's legal Haskell... but it is a bad idea to make lists an instance of Num, because there are situations where the result doesn't act as you would like (if you've had abstract algebra, the problem is that it isn't a ring). More concretely, it's not hard to see that the additive identity is [0,0,0...], the infinite list of zeros. But if you have a finite list x, then x - x is NOT equal to that additive identity! Instead, you'd only get a finite list of zeros, and if you try to do math with that later, you're going to accidentally truncate some answers now and then and wonder what went wrong. In general, most type classes in Haskell are like this... the compiler only cares that you provide operations with certain types, but the type class also carries around additional laws that you should obey when writing instances. Here there's no good way to write an instance that obeys the laws, so it's better to write no instance at all. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Le 26/03/2012 01:51, Chris Smith a écrit : instance (Num a) = Num [a] where xs + ys = zipWith (+) xs ys You can do this in the sense that it's legal Haskell... but it is a bad idea to make lists an instance of Num, because there are situations where the result doesn't act as you would like (if you've had abstract algebra, the problem is that it isn't a ring). More concretely, it's not hard to see that the additive identity is [0,0,0...], the infinite list of zeros. But if you have a finite list x, then x - x is NOT equal to that additive identity! Instead, you'd only get a finite list of zeros, and if you try to do math with that later, you're going to accidentally truncate some answers now and then and wonder what went wrong. In general, most type classes in Haskell are like this... the compiler only cares that you provide operations with certain types, but the type class also carries around additional laws that you should obey when writing instances. Here there's no good way to write an instance that obeys the laws, so it's better to write no instance at all. Sorry, Chris, I disagree quite strongly. You begin badly: the problem is that it isn't a ring. Who told you so? It MIGHT be a ring or not. The real problem is that one should not confuse structural and algebraic (in the classical sense) properties of your objects. 1. You may consider your lists as representants of polonomials. A very decent ring. 2. I used hundred times lists as representants of power series. Infinite, potentially, but often having just finite number of non-zero coefficients, and if those could be divided, the list was not only a ring, but a field. (Doug McIlroy did that as well, and his papers on power series are much better known than mine...) And NO, no truncation problems, if you know how to program correctly. The laziness helps. 3. A very similar stuff to series or polynomials is the usage of lists as differential algebras (uni-variate). I needed not only the numerical instances, but a derivation operator. A ring, a field, *different* from the previous ones. 4. I wanted to have the trajectories - the numerical sequences which were solutions of differential equations, to behave as mathematical objects that could be added, scaled, etc. A vector space, and much more. 5. I used lists as signals which could be added (sound composition), multiplied (modulation), etc. Good rings. Totally different from the previous ones. Whether it would be better to use some specific ADT rather than lists, is a question of style. The fact that - as you say - there's no good way to write an instance that obeys the laws won't disturb my sleep. You know, there is no good way to organise a society where everybody obeys the Law. This is no argument against the organisation of a Society... Thank you. Jerzy Karczmarczuk ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
Jerzy Karczmarczuk jerzy.karczmarc...@unicaen.fr wrote: Le 26/03/2012 01:51, Chris Smith a écrit : instance (Num a) = Num [a] where xs + ys = zipWith (+) xs ys You can do this in the sense that it's legal Haskell... but it is a bad idea [...] It MIGHT be a ring or not. The real problem is that one should not confuse structural and algebraic (in the classical sense) properties of your objects. Of course there are rings for which it's possible to represent the elements as lists. Nevertheless, there is definitely not one that defines (+) = zipWith (+), as did the one I was responding to. By the time you get a ring structure back by some *other* set of rules, particularly for multiplication, the result will so clearly not be anything like a general Num instance for lists that it's silly to even be having this discussion. -- Chris Smith ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On 3/25/12 8:06 AM, Michael Snoyman wrote: A simple solution is to use the zipWith[1] function: zipWith (+) [1,2,3] [4,5,6] == [5,7,9] It takes a bit of time to get acquainted with all of the incredibly convenient functions in base, but once you know them, it can greatly simplify your code. [1] http://hackage.haskell.org/packages/archive/base/4.5.0.0/doc/html/Prelude.html#v:zipWith And if you want different behavior with regards to lists of differing length, you may also be interested in pairWith[2] or zipOrWith[3] -- Silently truncate uneven lists. zipWith (+) [1,2,3] [4,5,6] == [5,7,9] zipWith (+) [1,2,3] [4,5] == [5,7] -- Give errors for uneven lists. pairWith (+) [1,2,3] [4,5,6] == Just [5,7,9] pairWith (+) [1,2,3] [4,5] == Nothing -- Assume infinitely many trailing zeros. zipOrWith plus [1,2,3] [4,5,6] == [5,7,9] zipOrWith plus [1,2,3] [4,5] == [5,7,3] where plus (Fst x ) = x plus (Sndy) = y plus (Both x y) = x+y [2] http://hackage.haskell.org/packages/archive/list-extras/0.4.0.1/doc/html/Data-List-Extras-Pair.html#v:pairWith [3] http://hackage.haskell.org/packages/archive/data-or/1.0.0/doc/html/Data-Or.html#v:zipOrWith -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] adding the elements of two lists
On 26/03/2012, at 12:51 PM, Chris Smith wrote: More concretely, it's not hard to see that the additive identity is [0,0,0...], the infinite list of zeros. But if you have a finite list x, then x - x is NOT equal to that additive identity! Said another way: if you do want [num] to support + and -, then you DON'T want the definitions of + and - to be unthinking applications of zipWith. The approach I took the time I did this (before I learned better) was this: smart_cons :: Num t = t - [t] - [t] smart_cons 0 [] = [] smart_cons x xs = x : xs instance Num t = Num [t] where (x:xs) + (y:ys) = smart_cons (x+y) (xs + ys) xs + [] = xs [] + ys = ys ... fromInteger 0 = [] fromInteger n = [n] ... so that a finite list acted _as if_ it was followed by infinitely many zeros. Of course this wasn't right either: if the inputs don't have trailing zeroes, neither do the outputs, but if they _do_ have trailing zeros, [0]+[] = [0] when it should = []. That was about the time I realised this was a bad idea. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
