Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Type classes and synonyms (Philip Scott)
2. Re: Type classes and synonyms (Stephen Tetley)
3. Re: Type classes and synonyms (Felipe Lessa)
4. Re: Re: Is Haskell for me? (Jon Harrop)
5. Re: Type classes and synonyms (Philip Scott)
6. Re: Type classes and synonyms (Philip Scott)
7. Re: Type classes and synonyms (Stephen Tetley)
8. Re: Type classes and synonyms (Felipe Lessa)
----------------------------------------------------------------------
Message: 1
Date: Sat, 21 Nov 2009 15:20:30 +0000
From: Philip Scott <[email protected]>
Subject: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="us-ascii"
Hello all,
Quick one for you. I have a list of (<timestamp>,<value>) pairs, and I have
defined lots of nice functions for doing various tricks with them. I'd like to
define a custom data type which is an instance of 'Num' so I can conveniently
do arithmetic on them. (I have written some tools for merging two time series
etc...)
e.g.
t (x,y) = x
v (x,y) = y
mergeSkip _ [] = []
mergeSkip [] _ = []
mergeSkip (x:xs) (y:ys)
| t x == t y = ( t x, (v x, v y) ) : (mergeSkip xs ys)
| t x > t y = mergeSkip xs (y:ys)
| t x < t y = mergeSkip (x:xs) ys
binaryValueFunc f [] = []
binaryValueFunc f ((t,(a,b)):xs) = (t, f a b):binaryValueFunc f xs
add xs = binaryValueFunc (+) xs
addSkip xs ys = add $ mergeSkip xs ys
So addSkip will nicely take two of my time series, merge them by throwing out
any pairs which don't have a time stamp that exists in both and then add the
values to return a new series. All is well. But how do I make it so that I can
use the + operator to add two of them?
Well of course, I tried making a custom data type:
data Ts a b = Ts [(a,b)]
intance Ts Num where
<blaa blaa blaa>
But then I have to rewrite all of my functions to pattern match on Ts instead
of just the list. Worse, when I am writing recursive functions I have to
construct a Ts again for the recursive call. I guess I could make my own
'list-like' datastructure
data Ts a b = Empty
| Cons ((a,b), Ts)
But that seems rather clumsy.
So I tried to make 'Ts' a type synonym for [(a,b)] which worked, but then
I couldn't declare it an instance of 'Num'.
So I guess the question is, is there any way of making a type synonym for a
type which I can define as an instance of another class? So I can use my
values of the type synonym for functions which expect the 'vanilla' type, but
define 'extra' stuff my type synonym can do?
Any help or advice greatly appreciated.
- Philip
------------------------------
Message: 2
Date: Sat, 21 Nov 2009 16:34:33 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: Philip Scott <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hello Philip
If you are wanting element-wise addition with two lists, you can do
> instance Num a => Num [a] where
> (+) = zipWith (+)
> (-) = zipWith (-)
> (*) = zipWith (*)
> fromInteger = repeat . fromInteger
> abs = map abs
> signum = map signum
Plus as you are representing timestamped values as pairs you would
need a Num instance for pairs...
> instance (Num a,Num b) => Num (a,b) where
> (+) (a,b) (x,y) = (a+x,b+y)
> (-) (a,b) (x,y) = (a-x,b-y)
> (*) (a,b) (x,y) = (a*x,b*y)
> fromInteger a = (fromInteger a, fromInteger a)
> abs (a,b) = (abs a, abs b)
> signum (a,b) = (signum a, signum b)
But... these instances are somewhat arbitrary, and other people
would no doubt disagree with their details:
For Num on lists there is the problem of uneven length lists.
Also fromInteger has a valid definintion as
fromInteger a = a : repeat 0
Hence, there aren't instances in the Hierarchical Libraries.
Uneven lists can be solved with Streams - see Ralf Hinze's
Streams, but then you move to infinite lists... Oh well.
http://hackage.haskell.org/packages/archive/hinze-streams/1.0/doc/html/Data-Stream-Hinze-Stream.html
As for your question, you can't use a type synonym to define
different class instances, you have to use a newtype. Perhaps the
best illustration is in Data.Monoid - Numbers have several useful
monoids, two of them are:
addition (0,+)
multiplication (1,*)
Data.Monoid uses the Sum newtype wrapper to define the addition
monoid and the Product newtype wrapper to define the
multiplication monoid.
Best wishes
Stephen
------------------------------
Message: 3
Date: Sat, 21 Nov 2009 14:07:14 -0200
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
Well, let's begin by making some suggestions to your current
code. Below I tell my answer to your question as well. :)
On Sat, Nov 21, 2009 at 03:20:30PM +0000, Philip Scott wrote:
] t (x,y) = x
] v (x,y) = y
> t = fst
> v = snd
] mergeSkip _ [] = []
] mergeSkip [] _ = []
] mergeSkip (x:xs) (y:ys)
] | t x == t y = ( t x, (v x, v y) ) : (mergeSkip xs ys)
] | t x > t y = mergeSkip xs (y:ys)
] | t x < t y = mergeSkip (x:xs) ys
Using 't' and 'v' isn't very readable, so probably it would be
better to just type two more characters and use 'fst' and 'snd':
> mergeSkip (x:xs) (y:ys)
> | fst x == fst y = (fst x, (snd x, snd y)) : mergeSkip xs ys
> | fst x > fst y = mergeSkip xs (y:ys)
> | fst x < fst y = mergeSkip (x:xs) ys
Or, even better yet,
> mergeSkip xss@((xa,xb):xs) yss@((ya,yb):ys)
> | xa == ya = (xa, (xb, yb)) : mergeSkip xs ys
> | xa > ya = mergeSkip xs yss
> | xa < ya = mergeSkip xss ys
] binaryValueFunc f [] = []
] binaryValueFunc f ((t,(a,b)):xs) = (t, f a b):binaryValueFunc f xs
> import Control.Arrow (second)
> binaryValueFunc f = map (second $ uncurry f)
Now, to your question!
] So addSkip will nicely take two of my time series, merge them by throwing out
] any pairs which don't have a time stamp that exists in both and then add the
] values to return a new series. All is well. But how do I make it so that I can
] use the + operator to add two of them?
]
] Well of course, I tried making a custom data type:
]
] data Ts a b = Ts [(a,b)]
] intance Ts Num where
] <blaa blaa blaa>
]
] But then I have to rewrite all of my functions to pattern match on Ts instead
] of just the list. Worse, when I am writing recursive functions I have to
] construct a Ts again for the recursive call. I guess I could make my own
] 'list-like' datastructure
The common idiom is to write
> newtype Ts a b = Ts {unTs :: [(a,b)]} deriving (Eq, Show)
We use a newtype just to guarantee that there will be no overhead
in using this data type instead of just using a plain list
(i.e. at runtime Ts and unTs will be striped out). We name the
field as unTs to use it when composing functions (see below). So
your definitions above will become:
> mergeSkip' (T xs) (T ys) = T (mergeSkip xs ys)
if you want to keep the old definition, or
> mergeSkip'' (T []) _ = T []
> mergeSkip'' _ (T []) = T []
> mergeSkip'' xss@(T ((xa,xb):xs)) yss@(T ((ya,yb):ys))
> | xa == ya = T $ (xa, (xb, yb)) : mergeSkip'' xs ys
> | xa > ya = mergeSkip'' (T xs) yss
> | xa < ya = mergeSkip'' xss (T ys)
Not that bad, I think. Continuing, let's use unTs:
> binaryValueFunc f = Ts . map (second $ uncurry f) . unTs
Not bad at all :). However we can just define:
> instance Functor (Ts a) where
> fmap f = Ts . fmap (second f) . unTs
Using the Functor we can rewrite binaryValueFunc to just
> binaryValueFunc' :: Functor f => (a -> b -> c) -> f (a,b) -> f c
> binaryValueFunc' f = fmap (uncurry f)
I've written the type explicitly to show how general we just got.
However, I guess the following function is more useful for the
Num instance:
> liftBin f xs ys = fmap (uncurry f) $ mergeSkip xs ys
Now our Num instance is just
> instance (Ord a, Num b) => Num (Ts a b) where
> (+) = liftBin (+)
> (-) = liftBin (-)
> (*) = liftBin (*)
> abs = fmap abs
> negate = fmap negate
> signum = fmap signum
> fromInteger = error "I don't know how you would define this :)"
I hope that helps!
(Note that if you can implement the Applicative type class for
your Ts data type and then get liftBin = liftA2 for free.)
--
Felipe.
------------------------------
Message: 4
Date: Sat, 21 Nov 2009 18:02:33 +0000
From: Jon Harrop <[email protected]>
Subject: Re: [Haskell-beginners] Re: Is Haskell for me?
To: Ben Lippmeier <[email protected]>
Cc: beginners <[email protected]>
Message-ID: <[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
On Saturday 21 November 2009 11:56:09 Ben Lippmeier wrote:
> Hmm. I'd be careful about conflating algorithmic complexity with memory
> management issues.
No need. Just look at how badly the performance scales for Haskell vs other
languages. For example, inserting 1-16 million floating point key/values into
a hash table:
Haskell OCaml F#
1M: 3.198s 1.0x 1.129s 1.0x 0.080s 1.0x
2M: 8.498s 2.7x 2.313s 2.0x 0.138s 1.7x
4M: 25.697s 8.0x 4.567s 4.0x 0.281s 3.5x
8M: 97.994s 30.6x 10.450s 9.3x 0.637s 8.0x
16M: 388.080s 121.4x 23.261s 20.6x 1.338s 16.7x
Note that Haskell is 290x slower than F# on that last test.
In practice, you would turn to a purely functional dictionary in Haskell based
upon balanced binary trees in order to work around this long-standing bug in
the GC but those trees incur O(log n) indirections and typically run orders
of magnitude slower than a decent hash table.
Suffice to say, Haskell is nowhere near being in the ballpark of C++'s
performance for basic functionality like dictionaries and sorting.
> By the above reasoning, if I were to run any program
> using arrays on a system with a two space garbage collector (which copies
> all live objects during each GC) I could say the worst case algorithmic
> complexity was O(n). That doesn't sound right.
Can you write a program that demonstrates this effect as I did?
> I could take this further and say that in a virtual memory system, there is
> a chance that the whole heap gets copied to the disk and back between each
> array update.
Can you write a program that demonstrates this effect as I did?
--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e
------------------------------
Message: 5
Date: Sat, 21 Nov 2009 17:39:20 +0000
From: Philip Scott <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
Hi Stephan,
> > instance Num a => Num [a] where
> > (+) = zipWith (+)
> > (-) = zipWith (-)
> > (*) = zipWith (*)
> > fromInteger = repeat . fromInteger
> > abs = map abs
> > signum = map signum
Oooh I had no idea you could do that with 'instance'
I merge my lists into a list of pairs before I do anything with them so
unevenness isn't a problem; I was just trying t convince haskell that I could
use nice operators like '+' on my derived type.
Thank you very much for your reply; between that and Felipe's I have enough to
keep me busy all evening digesting the new toys you have demonstrated :)
- Philip
------------------------------
Message: 6
Date: Sat, 21 Nov 2009 17:57:45 +0000
From: Philip Scott <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: Text/Plain; charset="iso-8859-1"
> Well, let's begin by making some suggestions to your current
> code. Below I tell my answer to your question as well. :)
What a fantastic and comprehensive answer, thank you!
I now need to sit down and digest it. There are so many little clever tricks
you can do with Haskell, is there a collection of them somewhere?
If you want to collect your obligatory cookie and are ever in and around
Cambridge UK let me know :)
- Philip
------------------------------
Message: 7
Date: Sat, 21 Nov 2009 18:13:02 +0000
From: Stephen Tetley <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: Philip Scott <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset=ISO-8859-1
Hi Philip
Aesthetics, taste, sanity, whatever... strongly suggest not doing it of course.
But there is (probably) little harm in trying it.
Best wishes
Stephen
2009/11/21 Philip Scott <[email protected]>:
>
> Oooh I had no idea you could do that with 'instance'
>
> > instance Num a => Num [a] where
> > (+) = zipWith (+)
> > (-) = zipWith (-)
> > (*) = zipWith (*)
> > fromInteger = repeat . fromInteger
> > abs = map abs
> > signum = map signum
------------------------------
Message: 8
Date: Sat, 21 Nov 2009 16:19:34 -0200
From: Felipe Lessa <[email protected]>
Subject: Re: [Haskell-beginners] Type classes and synonyms
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=us-ascii
On Sat, Nov 21, 2009 at 05:57:45PM +0000, Philip Scott wrote:
> What a fantastic and comprehensive answer, thank you!
No problem. :)
> I now need to sit down and digest it. There are so many little clever tricks
> you can do with Haskell, is there a collection of them somewhere?
Lately people have been suggesting the Typeclassopedia[1] as a
good place for begginners. It's a good reading and I recommend
it, I just don't know if you'll find everything needed for my
answer there.
In general, however, you just need practice. Go code! =)
[1] http://haskell.org/sitewiki/images/8/85/TMR-Issue13.pdf
> If you want to collect your obligatory cookie and are ever in and around
> Cambridge UK let me know :)
Too bad I'm 8837 km away from Cambridge according to Alpha =(...
Cheers,
--
Felipe.
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 17, Issue 20
*****************************************
