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.ht...

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 (Snd y) = y plus (Both x y) = x+y [2] http://hackage.haskell.org/packages/archive/list-extras/0.4.0.1/doc/html/Dat... [3] http://hackage.haskell.org/packages/archive/data-or/1.0.0/doc/html/Data-Or.h... -- Live well, ~wren

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

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

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

Le 26/03/2012 16:31, Chris Smith a écrit : 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.

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.

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

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.