Re: [Haskell-cafe] nubBy seems broken in recent GHCs
On Sat, 2009-06-06 at 18:39 +0200, Bertram Felgenhauer wrote: Interesting. This was changed in response to http://hackage.haskell.org/trac/ghc/ticket/2528 | Tue Sep 2 11:29:50 CEST 2008 Simon Marlow marlo...@gmail.com | * #2528: reverse the order of args to (==) in nubBy to match nub | This only makes a difference when the (==) definition is not | reflexive, but strictly speaking it does violate the report definition | of nubBy, so we should fix it. It turns out that 'elem' differs from the report version and should have its comparison reversed. Of course that would only ever matter for broken Eq instances. However, the report also states that the nubBy function may assume that the given predicate defines an equivalence relation. http://haskell.org/onlinereport/list.html#sect17.6 So I'm not sure there's anything to be fixed here - although backing out the above patch probably won't hurt anybody. Seems to me the obvious solution is to revert the nubBy change and then fix nub so that so that we still get nub = nubBy (==) (which is what ticket #2528 was complaining about in the first place). We need more SmallCheck properties for the List module! When Don and I were testing our stream versions of the List module we uncovered several of these little weirdnesses which were underspecified in the report, or different between the report and common implementations. For example I seem to recall that genericTake and take do not coincide when their types coincide. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] Convert IO Int to Int
On Tue, 9 Jun 2009, Bulat Ziganshin wrote: Hello jerzy, Tuesday, June 9, 2009, 8:23:04 PM, you wrote: Please, tell him first about random streams, which he can handle without IO. Or, about ergodic functions (hashing contraptions which transform ANY parameter into something unrecognizable). When he says : I know all that, THEN hurt him badly with monads. i think that for someone coming from imperative programming teeling about IO monad is the easiest way. and then he will learn how to do it FP way I came from imperative programming and never wanted to use randomIO, because it forces you to IO and randomsIO is not lazy. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How To Make It Faster?
Hi, I come up with the following solution for this spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] nubBy seems broken in recent GHCs
On Tue, 9 Jun 2009, Cale Gibbard wrote: Similarly, groupBy f xs is (and should be) the unique list of contiguous sublists of xs such that: 1) concat (groupBy f xs) = xs 2) If x is the head of any of the sublists and y is any other element of that sublist, then f x y 3) The sequence of lengths of the sublists is lexicographically maximum for all lists satisfying the first two properties (That is, it always prefers adding elements to an earlier group to starting a new group.) groupBy defined this way was found to be inappropriate for many cases, like grouping a list into increasing sequences using groupBy (=). Other cases can be found in Haskell-Cafe or librar...@haskell.org. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] How To Make It Faster?
Hi, I come up with the following solution for this easy spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, -- ~dsouza yahoo!im: paravinicius gpg key fingerprint: 71B8 CE21 3A6E F894 5B1B 9ECE F88E 067F E891 651E ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] How To Make It Faster?
Diego Souza dso...@bitforest.org writes: I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. The usual approach is to compile with profiling (ghc -prof -auto-all, don't forget to optimize!), and run with time profiling enabled (./my-program -my-options +RTS -p). You can then examine the resulting profiling output (my-program.prof) to identify hotspots, and try to improve them. -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] How To Make It Faster?
On Wed, Jun 10, 2009 at 10:11 AM, paravinic...@yahoo.com.br wrote: Hi, I come up with the following solution for this spoj problem (warning!): problem: https://www.spoj.pl/problems/ARITH2/ solution: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5720#a5720 I'd like to make it run faster, if possible. What should I do to identify the bottlenecks and once I find them, a few guidelines to actually fix them. Thanks in advance, My profiling-fu is rather weak, but I think about 40% of the time is spent on reading from stdin, about 17% on splitting that into lines and then words. Only about 10% is spent in arith_expression and 8% in the lambda you pass into forM. I don't have any suggestions for actually speeding it up, but profiling helps in concentrating your efforts. :-) /M -- Magnus Therning(OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus identi.ca|twitter: magthe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
Hi, I have tried on the console to write x - randomRIO(1,10) :t x Everythings fine and the type of x is x :: Integer Now I have tried to write a Method which gives me a Number of random numbers the same way but it doesn't work. randomList :: Int - [Integer] randomList 0 = [] randomList n = do r - randomRIO (1, 10) r:randomList(n-1) It says Couldn't match expected type `IO t' against inferred type `[t]' r - randomRIO (1,10) causes an error. But why does it work on the console? Is there a way to solve it another way? -- View this message in context: http://www.nabble.com/Convert-IO-Int-to-Int-tp23940249p23960652.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
r - randomRIO (1,10) is NOT the source of error. Why do you think it is? ptrash wrote on 10.06.2009 15:55: Hi, I have tried on the console to write x - randomRIO(1,10) :t x Everythings fine and the type of x is x :: Integer Now I have tried to write a Method which gives me a Number of random numbers the same way but it doesn't work. randomList :: Int - [Integer] randomList 0 = [] randomList n = do r - randomRIO (1, 10) r:randomList(n-1) It says Couldn't match expected type `IO t' against inferred type `[t]' r - randomRIO (1,10) causes an error. But why does it work on the console? Is there a way to solve it another way? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
Hmm...I use the Eclipse Plugin. And this row is marked as error. Then where is the error? -- View this message in context: http://www.nabble.com/Convert-IO-Int-to-Int-tp23940249p23960827.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
On 10 Jun 2009, at 12:55 pm, ptrash wrote: Now I have tried to write a Method which gives me a Number of random numbers the same way but it doesn't work. randomList :: Int - [Integer] randomList 0 = [] randomList n = do r - randomRIO (1, 10) r:randomList(n-1) It says Couldn't match expected type `IO t' against inferred type `[t]' r - randomRIO (1,10) causes an error. But why does it work on the console? Is there a way to solve it another way? I had the same problem a while back, the thread is here http://www.mail-archive.com/haskell-cafe@haskell.org/msg46194.html the console uses IO already, so it's not a problem there. I ended up learning about the = operator, and that helped a lot. Anyway, lots of helpful links in that mail thread. Iain ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
On Wed, Jun 10, 2009 at 12:55 PM, ptrash ptr...@web.de wrote: Hi, I have tried on the console to write x - randomRIO(1,10) :t x Everythings fine and the type of x is x :: Integer The type of x *in the context of an IO computation* is Integer. GHCi is basically an IO computation. Another example: foo :: Integer - Integer foo x = x+1 main :: IO () main = do x - randomRIO (1,10) print (foo x) This is fine. In the context of the IO computation main, x is bound to the result of randomRIO (1,10), and you can pass it to functions expecting Integer values (not IO Integer!). So in this way, and this way only, you can access the Integer returned by an IO action. You can *not* access the Integer returned by an IO action from within a normal function, *only* by by binding it to a variable (with -) inside *another IO action*. I'm not sure what text you're using to learn Haskell, but a very basic and fundamental property of Haskell (and indeed 99% of why it's cool, IMO) is that code which does side effects (like reading from a global random number seed), and code which does not do side effects (i.e. functions which always return the same result given the same input) are kept extremely separate. This appears to be the source of your confusion. It's simply not possible to do side effect inside a normal function, just like it's not possible to cast an arbitrary integer to a pointer in Java - the language is designed to not require it, and the benefits of being able to trust that your program obeys certain properties are worth it. randomList :: Int - [Integer] randomList 0 = [] randomList n = do r - randomRIO (1, 10) r:randomList(n-1) In this code you're trying to do side effects from within a pure function. This is *not* allowed. You must either make randomList an IO action (i.e returning IO [Integer]), or remove any impurities from its implementation. For example you can make randomList take a randon number generator and use the random number generator to produce random values: randomList :: (RandomGen g) - Int - g - [Integer] randomList 0 _ = [] randomList n generator = r : randomList (n-1) newGenerator where (r, newGenerator) = randomR (1,10) generator This is totally pure, since if you pass in the same random number generator multiple times, you'll get the exact same result. Note that randomR returns a random values and a new random number generator (you wouldn't want to pass along the same one in the recursive call to randomList as that would give you an identical random number each time you use it!). So where do you get the random number generator from? Well one way is to make your own using mkStdGen, which produces one from a seed (it will give you an identical one given an identical seed). Another way is to use newStdGen to generate one from within an IO action: main :: IO () main = do generator - newStdGen print ( randomList 10 generator ) The point, though, is that things having side effects (such as newStdGen) can only be used in the context of something else having side effects. So the IO type is contagious, as soon as you use it in a function, then that function must also return IO, and so on for anything using *that* function and son. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
On Wed, Jun 10, 2009 at 2:08 PM, Sebastian Sylvan sebastian.syl...@gmail.com wrote: randomList :: (RandomGen g) - Int - g - [Integer] Just spotted this typo, it should be: randomList :: (RandomGen g) = Int - g - [Integer] There may be other minor typos as I don't have a compiler handy. -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
On Wed, Jun 10, 2009 at 2:10 PM, Sebastian Sylvan sebastian.syl...@gmail.com wrote: On Wed, Jun 10, 2009 at 2:08 PM, Sebastian Sylvan sebastian.syl...@gmail.com wrote: randomList :: (RandomGen g) - Int - g - [Integer] Just spotted this typo, it should be: randomList :: (RandomGen g) = Int - g - [Integer] There may be other minor typos as I don't have a compiler handy. Oh come on! randomList :: (RandomGen g) = Int - g - [Integer] -- Sebastian Sylvan +44(0)7857-300802 UIN: 44640862 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Convert IO Int to Int
This stuff is tricky for most newcomers I suspect (it was for me) x - randomRIO(1,10) is temporarilly pulling the Integer you've named x out of the IO Integer it came from. You can think of the console as being an input/output stream inside the IO monad, which is why it is allowed there. The fact is these are equivalent do x - randomRIO(1,10) x : expression and randomRIO(1,10) = (\x - x:expression) They are the same meaning, and both are illegal for the same reason. (=) is the bind operator for Monads and it allows you to do things like sequence an IO operation or action, then examine the contents returned by that IO action, possibly performing some transformation on it with another function. x:expression is the function that takes a value x and applies the cons function (:) to build a list with expression. The problem is that the type system of Haskell will not allow this because the bind function (which is used by the do syntax behind the scenes) is of type: (=) :: (Monad m) = m a - (a - m b) - m b Which states that the first argument to (=) is a Monad a, or in your case randomRIO(1,10) which is of type IO Integer IO being the m part of m a and Integer being the a part of m a. What comes next is your consing function of (x : expression). This is of type [Integer]. So you failed to give it a function of type (a - m b). (a - m b) says that the input type to that function must be the same as the contained value of the first argument to (=) (because they're both of type 'a'). The m b part says that you must use the *same Monad* you used in the first parameter to (=) which is IO, not []. However the 'b' part says you can convert things of one type 'a' to things of another type 'b'. This is legal: randomRIO(1,10) = return (x : expression) However what you've got now is not a List of Integers ([Integer]) but an IO [Integer]. Because of the type of (=), you are not going to ever permanently escape that IO wrapper around your values you're interested in. The return is a function of the class Monad, that takes a value, and wraps it up in a monad. Based on the (=) function's type, the system can infer that you meant the IO monad here. You can even test this at the console: Prelude System.Random randomRIO(1,10) = (\x - return (x:[99])) [7,99] Prelude System.Random randomRIO(1,10) = (\x - return (x:[99])) [6,99] Prelude System.Random randomRIO(1,10) = (\x - return (x:[99])) [2,99] Prelude System.Random :t randomRIO(1,10) = (\x - return (x:[99])) randomRIO(1,10) = (\x - return (x:[99])) :: (Num t, Random t) = IO [t] vs randomRIO(1,10) = (\x - x:[99]) Which doesn't pass the type checking of the system because [] is not the same monad as IO. Perhaps you'd do well for yourself by reading Learn You A Haskell? I've found it to be pretty darned good at explaining lots of haskell to newcomers. Dave On Wed, Jun 10, 2009 at 4:55 AM, ptrash ptr...@web.de wrote: Hi, I have tried on the console to write x - randomRIO(1,10) :t x Everythings fine and the type of x is x :: Integer Now I have tried to write a Method which gives me a Number of random numbers the same way but it doesn't work. randomList :: Int - [Integer] randomList 0 = [] randomList n = do r - randomRIO (1, 10) r:randomList(n-1) It says Couldn't match expected type `IO t' against inferred type `[t]' r - randomRIO (1,10) causes an error. But why does it work on the console? Is there a way to solve it another way? -- View this message in context: http://www.nabble.com/Convert-IO-Int-to-Int-tp23940249p23960652.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ 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] Convert IO Int to Int
Thanks a lot. I have put now everything into the main method and it works. -- View this message in context: http://www.nabble.com/Convert-IO-Int-to-Int-tp23940249p23964365.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] who's up for a hackathon? (ICFP, late Aug, early Sept)
Dear Haskellers, ICFP 2009 takes place from Monday 31 August to Wednesday 2 September, with the Haskell Symposium following it on 3 September. Would anybody be interested having a Haskell Hackathon during this? My thinking is that to catch people who are only going to the Haskell Symposium, the best time is the following weekend (4-6 September). Otherwise, the weekend before (29-30 August) is also an option and has the benefit of catching people before they get tired :-) Rah, rah, hackathon! 1. If possible, I'd like get a idea if there is any interest in attending such a Hackathon if it were to take place. 2. For rah-rah Hackathon to work, we need people! Could I get one kind (and local) soul to act as an organiser for this? Thanks! -- Eric Kow http://www.nltg.brighton.ac.uk/home/Eric.Kow PGP Key ID: 08AC04F9 signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Weird and entirely random problem...
The code that causes it is here:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5731#a5731
This is the strangest thing. Occasionally, using nothing but gets and
puts and frees on a non-full Cache will result in this:
Cache {
store = fromList
[((\icons/addBookmark.png\,False),TextureObject {textureID = 4})
,((\icons/addCircle.png\,False),TextureObject {textureID = 1})
,((\icons/addContent.png\,False),TextureObject {textureID = 2})
,((\icons/addElsewhereLink.png\,False),TextureObject
{textureID = 3})]
, times = fromList
[(61314,(\span font_desc='sans
8'294.0/span\,AlignLeft,Nothing,WrapWholeWords,False,0.0,0.0))
,(61316,(\icons/addBookmark.png\,False)),(61318,(\icons/addCircle.png\,False))
,(61320,(\icons/addContent.png\,False)),(61322,(\icons/addElsewhereLink.png\,False))]
, now = 61323
, maxsize = 1024768000
, size = 4
, decimation = 0
}
Sometimes the problem is self-correcting. Sometimes it is most
certainly not. But I don't understand how my code can possibly allow
for this.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Weird and entirely random problem...
Hi,
I'm presuming the problem with your result is that the span... String
is in the times map, and not in the store map (you weren't clear on the
exact problem).
I took a look at the code, here's my thoughts on why this occurs. If
you start by putting something in the cache with key foo, an entry is
created in the times map, say: fromList [(0, foo)]. If you then get
the item from the cache, you add another item to the times map, giving
you: fromList [(0, foo), (1, foo)]. Another get operation, and
you'll have fromList [(0, foo), (1, foo), (2, foo)]. If you now
call free on the cache, it finds the value associated with the minimum
key: foo. But it only deletes the minimum key in the times map,
leaving: fromList [(1, foo), (2, foo)]. Thus you can have entries
in the times map without them being in the store. put would clear them
out (perhaps this was the self-correction you saw), but get adds one
each item, and free only clears one. So you either need to fix get, or
free.
Does that help, or was your question something else entirely? :-)
BTW, IntMap.fromList . filter (f . snd) . IntMap.toList is more
concisely (and efficiently) written as: IntMap.filter f
Thanks,
Neil.
Jeff Heard wrote:
The code that causes it is here:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5731#a5731
This is the strangest thing. Occasionally, using nothing but gets and
puts and frees on a non-full Cache will result in this:
Cache {
store = fromList
[((\icons/addBookmark.png\,False),TextureObject {textureID = 4})
,((\icons/addCircle.png\,False),TextureObject {textureID = 1})
,((\icons/addContent.png\,False),TextureObject {textureID = 2})
,((\icons/addElsewhereLink.png\,False),TextureObject
{textureID = 3})]
, times = fromList
[(61314,(\span font_desc='sans
8'294.0/span\,AlignLeft,Nothing,WrapWholeWords,False,0.0,0.0))
,(61316,(\icons/addBookmark.png\,False)),(61318,(\icons/addCircle.png\,False))
,(61320,(\icons/addContent.png\,False)),(61322,(\icons/addElsewhereLink.png\,False))]
, now = 61323
, maxsize = 1024768000
, size = 4
, decimation = 0
}
Sometimes the problem is self-correcting. Sometimes it is most
certainly not. But I don't understand how my code can possibly allow
for this.
___
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] Weird and entirely random problem...
That works, yes... thanks!
On Wed, Jun 10, 2009 at 12:58 PM, Neil Brownnc...@kent.ac.uk wrote:
Hi,
I'm presuming the problem with your result is that the span... String is
in the times map, and not in the store map (you weren't clear on the exact
problem).
I took a look at the code, here's my thoughts on why this occurs. If you
start by putting something in the cache with key foo, an entry is created
in the times map, say: fromList [(0, foo)]. If you then get the item from
the cache, you add another item to the times map, giving you: fromList [(0,
foo), (1, foo)]. Another get operation, and you'll have fromList [(0,
foo), (1, foo), (2, foo)]. If you now call free on the cache, it
finds the value associated with the minimum key: foo. But it only deletes
the minimum key in the times map, leaving: fromList [(1, foo), (2,
foo)]. Thus you can have entries in the times map without them being in
the store. put would clear them out (perhaps this was the self-correction
you saw), but get adds one each item, and free only clears one. So you
either need to fix get, or free.
Does that help, or was your question something else entirely? :-)
BTW, IntMap.fromList . filter (f . snd) . IntMap.toList is more concisely
(and efficiently) written as: IntMap.filter f
Thanks,
Neil.
Jeff Heard wrote:
The code that causes it is here:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=5731#a5731
This is the strangest thing. Occasionally, using nothing but gets and
puts and frees on a non-full Cache will result in this:
Cache {
store = fromList
[((\icons/addBookmark.png\,False),TextureObject {textureID =
4})
,((\icons/addCircle.png\,False),TextureObject {textureID = 1})
,((\icons/addContent.png\,False),TextureObject {textureID = 2})
,((\icons/addElsewhereLink.png\,False),TextureObject
{textureID = 3})]
, times = fromList
[(61314,(\span font_desc='sans
8'294.0/span\,AlignLeft,Nothing,WrapWholeWords,False,0.0,0.0))
,(61316,(\icons/addBookmark.png\,False)),(61318,(\icons/addCircle.png\,False))
,(61320,(\icons/addContent.png\,False)),(61322,(\icons/addElsewhereLink.png\,False))]
, now = 61323
, maxsize = 1024768000
, size = 4
, decimation = 0
}
Sometimes the problem is self-correcting. Sometimes it is most
certainly not. But I don't understand how my code can possibly allow
for this.
___
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
[Haskell-cafe] Hac phi accommodation: register by June 15 for reduced rate!
Hi all, This is a quick reminder for people interested in attending Hac phi who have not yet reserved a hotel room: if you'd like to reserve a room at Club Quarters at the reduced rate ($114/night single, $129/night double), we ask that you send a note to Daniel Wagner (dan...@wagner-home.com) by this Monday, June 15th. To register, or for more infomation about Hac phi, visit the wiki page [1]. Thanks, and we look forward to seeing you at the hackathon! The Hac phi Team [1] http://haskell.org/haskellwiki/Hac_%CF%86 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: [Haskell] ANNOUNCE: testrunner-0.9
When I run Example.lhs for test-framework I get [0] [1] in the test results, just as you show on your web page. If I run Example.lhs under ghci rather than compiled, I find the [0] [1] mingled with the test results in random ways. This leads me to believe that whatever is printing out [0] [1] is running is a separate thread. Does this [0] [1] have any meaning? If not, how do I get rid of it? Thanks, -Rod On Mon, 8 Jun 2009 19:07:52 +0100 Max Bolingbroke batterseapo...@hotmail.com wrote: 2009/6/8 Reinier Lamers tux_roc...@reinier.de: I checked out testpack and that did not meet my requirements. I don't know if I considered test-framework. If I did, it may be that I was turned off by the fact that the 'home page' link on cabal just goes to a web presentation of the source tree on github. Reinier, You are quite right that this is a weakness. I've been meaning to put a site together for a while, and your comment gave me the impetus to do it: http://batterseapower.github.com/test-framework/ That's much friendlier! All the best, Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe The following line is added for your protection and will be used for analysis if this message is reported as spam: (Raytheon Analysis: IP=128.36.229.215; e-from=haskell-cafe-boun...@haskell.org; from=batterseapo...@hotmail.com; date=Jun 8, 2009 6:08:07 PM; subject=[Haskell-cafe] Re: [Haskell] ANNOUNCE: testrunner-0.9) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Building a tree?
Here's a function from Data.Tree: unfoldTree :: (b - (a, [b])) - b - Tree a Build a tree from a seed value Could someone please give me a brief example of usage. Michael ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Building a tree?
On Wed, 10 Jun 2009, michael rice wrote: Here's a function from Data.Tree: unfoldTree :: (b - (a, [b])) - b - Tree a Build a tree from a seed value Could someone please give me a brief example of usage. unfoldTree (\n - (chr (n + ord 'a'), replicate n (n-1))) 3 Or did you expect a real world example? :-) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Building a tree?
michael rice wrote: Here's a function from Data.Tree: unfoldTree :: (b - (a, [b])) - b - Tree a Build a tree from a seed value Could someone please give me a brief example of usage. Data.Tree let t = unfoldTree (\i - (show i, [i`div`2..i-1])) Data.Tree putStr . drawTree $ t 8 -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Building a tree?
michael rice wrote:
Here's a function from Data.Tree:
unfoldTree :: (b - (a, [b])) - b - Tree a
Build a tree from a seed value
Could someone please give me a brief example of usage.
In as far as understanding it, it may be easier if you look at the
generalized version of the anamorphism:
newtype Fix f = Fix { unFix :: f (Fix f) }
type Tree a = Fix (Node a)
data Node a b = Node a [b]
instance Functor (Node a) where
fmap f (Node a bs) = Node a (map f bs)
unfoldTree f = Fix . fmap (unfoldTree f) . f
--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: FlexibleContexts and FlexibleInstances
Hi Claus, What you describe is exactly how I would *want* things to work. It's nice to hear my wishes echoed from a user perspective. :-) On Wed, Jun 10, 2009 at 4:43 PM, Claus Reinkeclaus.rei...@talk21.com wrote: just a few comments from a user (who would really, really, like to be able to define pragma collections, so that he doesn't have to switch on half a dozen separate extensions every time;-). The following toy program requires MultiParamTypeClasses OR FlexibleContexts in order to be accepted by GHC(i): f :: (T a b) = a - Int f _ = 0 This of course assumes that we import the definition of T, we *must* have MultiParamTypeClasses enabled if we want to declare T. Both extensions thus enable classes with more than one argument to appear in contexts. Only MultiParamTypeClasses does (and neither extension is needed in the module defining 'f', if 'T' is imported, which suggests that MultiParamTypeClasses is propagated to importers - this isn't true for most other extensions). The documentation still points to -fglasgow-exts, so it doesn't seem to answer these questions.. Right you are - which seems very strange to me. GHC accepts the module defining 'f' with no flags at all, even though it is clearly not Haskell 98. I'd go so far as to say that's a bug (as opposed to just unwanted/unexpected behavior). f :: (T a ()) = a - Int f _ = 0 i.e. changing the second argument to T to () instead, means we now *must* have FlexibleInstances, in order to allow the non-tyvar argument. This is nothing surprising, this is what FlexibleInstances are supposed to do. You mean FlexibleContexts. Indeed I do. Now, FlexibleInstances *also* lifts the restriction on contexts, just like FlexibleContexts - but *only* for the contexts of instance declarations. No. FlexibleInstances is about instance *heads*, FlexibleContexts is about contexts everywhere (in practice, there are some bugs;-). Right, this is exactly what I *want* should happen, both as a user and as an implementor, but that's not how GHC does it. FlexibleInstances do enable FlexibleContexts for contexts in instance declarations - which I think is a wart. class T a b -- requires MultiParamTypeClasses instance T a a -- requires FlexibleInstances instance Eq () = T a [b] -- requires FlexibleContexts instance Eq [a] = T a b -- requires UndecidableInstances Agreed - but here you avoid the tricky cases like my 'f' above. ;-) What I would want, and what I believe you want as well, is the following: ** MultiParamTypeClasses: Enables more than one parameter in class declarations, instance heads and more than one argument to class assertions in contexts everywhere. Formally, it would mean the following changes to the Haskell 98 syntax: topdecl - class [scontext =] tycls tyvar1 ... tyvarn [where cdecls] (n =1) | instance [scontext =] qtycls inst1 ... instn [where idecls] (n =1) context - class | ( class1 , ... , classn ) (n=0) class - qtycls cls1 ... clsn(n=1) cls - tyvar | ( tyvar atype1 ... atypen ) (n=1) scontext- simpleclass | ( simpleclass1 , ... , simpleclassn ) (n=0) simpleclass - qtycls scls1 ... sclsn(n=1) scls - tyvar ** FlexibleContexts: Enables the use of non-tyvar (or tyvar applied to types) arguments to class assertions in contexts everywhere (orthogonal to whether there can be several arguments or just one). Formally it means the following syntactic changes to Haskell 98: fcontext- fclass | ( fclass1 , ... , fclassn ) (n=0) fclass - qtycls atype1 ... atypen (n=1) topdecl - data [fcontext =] simpletype = constrs [deriving] | newtype [fcontext =] simpletype = newconstr [deriving] | class [fcontext =] tycls tyvar [where cdecls] | instance [fcontext =] qtycls inst [where idecls] gendecl - vars :: [fcontext =] type for the single-argument case. (Note that I wrote type in my proposal in the OP, but it should of course be atype.) ** FlexibleInstances: Enables the use of arguments other than type constructors (possibly applied to tyvars) in instances *heads* (orthogonal to whether there can be one or more arguments, and what the context may look like). Formally it means the following syntactic changes to Haskell 98: topdecl - instance [scontext =] qtycls inst [where idecls] inst - atype for the single-parameter standard-context case. (Note again that it should be atype and not type as I wrote in the OP.) This of course only touches the syntactic part. It doesn't attempt to track things like 'instance (T a a) = R a b' that would be enabled by FlexibleContexts, nor does it attempt to track things like
[Haskell-cafe] a cool paper (.pdf) on Cabal?
Hello, Before I found a really cool paper on Cabal motivation and architecture. I can no longer find this paper. Any ideas/suggestions? Kind regards, Vasili ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Lightweight type-level dependent programming in Haskell
(Literate Haskell post)
{-# LANGUAGE GADTs, RankNTypes, TypeFamilies, ScopedTypeVariables,
FlexibleContexts #-}
module Dependent where
I recently discovered an interesting way of closing typeclasses while
playing with type-level peano naturals:
First we build peano integers at the type level:
data Z = Z
newtype S n = S n
And a couple of generally useful type-level combinators:
newtype I x = I { unI :: x }
newtype K x y = K { unK :: x }
(We could also include the S combinator, under a different name, but I
haven't needed it yet...)
This representation isn't closed; there's nothing forcing the n in
S n to be Z or S n. But we can make a typeclass easily:
class Nat n
instance Nat Z where ...
instance Nat n = Nat (S n) where ...
But again, this typeclass is open. What I recently realized is that
it's easy to close the typeclass by requiring instances to provide a
simple implementation of typecase:
class Nat n where
caseNat :: forall r. n - (n ~ Z = r) - (forall p. (n ~ S p, Nat p) = p
- r) - r
By parametricity, any non _|_ implementation of caseNat has to prove
either (n ~ Z), to call the first branch, or (n ~ S p) for some other
natural p, to call the second.
instance Nat Z where
caseNat _ z _ = z
instance Nat n = Nat (S n) where
caseNat (S n) _ s = s n
(Interesting side note: the S n pattern match is automatically lazy,
since S is a newtype)
Somewhat surprisingly, caseNat is sufficient to prove *dependent* induction:
induction :: forall p n. Nat n = n - p Z - (forall x. Nat x = p x - p (S
x)) - p n
induction n z s = caseNat n isZ isS where
isZ :: n ~ Z = p n
isZ = z
isS :: forall x. (n ~ S x, Nat x) = x - p n
isS x = s (induction x z s)
What does this function mean? Through the Curry-Howard lens, it says:
If we have a proof of P 0,
and a proof of (P x - P (x+1)) for any natural x,
then we can prove P n for any natural n!
The proof simply proceeds by case analysis on n; we know that the
proof terminates since the recursive step works at a strictly smaller
type, and Haskell types are all finite in size.
Now, of course, this isn't any different from case analysis on this GADT:
data Peano a where
Pz :: Peano Z
Ps :: Peano n - Peano (S n)
inductP :: forall n p. Peano n - p Z - (forall x. Peano x - p x - p (S
x)) - p n
inductP Pz z s = z
inductP (Ps n) z s = s n (inductP n z s)
In fact, the whole point of GADT case analysis is to introduce the
type-level coercions that caseNat makes explicit. So there's not a
huge gain here. There is one interesting benefit that the typeclass
answer gives you, however; you can let the compiler derive the proof
for you:
witnessNat :: forall n. Nat n = n
witnessNat = theWitness where
theWitness = unI $ induction (undefined `asTypeOf` theWitness) (I Z) (I . S
. unI)
Then we can optimize the implementation of witness to unsafeCoerce Z
after the typechecker agrees with our proof.
Another useful tool is existentials and witnesses; existentials allow
you to do value-level calculation on Nat; witnesses allow you to
construct a proof of Nat n and return it from a proof; there's no
other way to return that something is a member of a typeclass.
data AnyNat where AnyNat :: Nat n = n - AnyNat
data IsNat n where IsNat :: Nat n = IsNat n
mkNat :: Integer - AnyNat
mkNat x | x 0 = error Nat must be = 0
mkNat 0 = AnyNat Z
mkNat x = case (mkNat (x-1)) of (AnyNat n) - AnyNat (S n)
natToInteger :: Nat n = n - Integer
natToInteger n = unK $ induction n (K 0) (K . (+1) . unK)
prec_app = 11
instance Show AnyNat where
showsPrec p (AnyNat n) = showParen (p prec_app) (showString mkNat .
shows (natToInteger n))
Fun exercises:
data TEq a b where TEq :: (a ~ b) = TEq a b
1) Write a sized list GADT, and build some lists using combinators on
Nat. Here's an example:
myReplicate a = induction witnessNat Nil (Cons a)
For me, ghc correctly infers this function to have the type
myReplicate :: (Nat n) = a - List a n. It's nice that I don't have
to specify n anywhere!
Try implementing fold :: Nat n = (forall x. Nat x = a - p x - p (S
x)) - List a n - p n
2) (Easy) Prove that all sized lists have a length that is a natural number:
lengthIsNat :: SizedList a n - IsNat n
3) Prove that equality is decidable on naturals:
natEqDec :: forall x y. (Nat x, Nat y) = x - y - Maybe (TEq x y)
4) Write the standard plus type family, then prove:
plusIsNat :: forall x y. (Nat x, Nat y) = IsNat (Plus x y)
plusIsComm :: forall x y. (Nat x, Nat y) = TEq (Plus x y) (Plus y x)
(While doing this exercise, I was impressed at how good the type
coercion prover is)
5) (Challenge) Write definitions for instance Eq AnyNat and
instance Num AnyNat
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Debugging misbehaving multi-threaded programs
I've written a multi-threaded Haskell program that I'm trying to debug. Basically what's happening is the program runs for a while, and then at some point one of the threads goes crazy and spins the CPU while allocating memory; this proceeds until the system runs out of available memory. I can't fix this without figuring out what code is being executed in the loop (or at least which thread is misbehaving, which would narrow things down a lot). I was hopeful that I could compile the program with profiling support and then use +RTS -M100M along with some of the RTS profiling options and get profiling information on CPU and memory usage at the time that my program runs out of memory. The thinking here is that nearly all of the CPU time and heap space will be from the misbehaving thread, so at that point I could do more investigation into exactly what is happening. Unfortunately, this doesn't seem to work; whenever the program terminates due to running out of heap space, the generated .prof file is empty. Another strategy I tried was running the program in ghci and use -fbreak-on-exception and :trace; by hitting Ctrl-C I was hopeful I'd stop the program in whatever is looping (this is all described and suggested in the ghc docs). Unfortunately, this also didn't seem to work, because the Ctrl-C only stops the main thread. Does anyone have any tips for dealing this? Have other people run into similar problems? I'm out of ideas, so I'm open to any suggestions. -- Evan Klitzke e...@eklitzke.org :wq ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Lightweight type-level dependent programming in Haskell
I recently discovered an interesting way of closing typeclasses while playing with type-level peano naturals: class Nat n where caseNat :: forall r. n - (n ~ Z = r) - (forall p. (n ~ S p, Nat p) = p - r) - r I usually use this one: class Nat n where caseNat :: p Z - (forall m. Nat m = p (S m)) - p n instance Nat Z where caseNat pz _ = pz instance Nat n = Nat (S n) where caseNat _ psm = psm ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: a cool paper (.pdf) on Cabal?
On Wed, 10 Jun 2009 20:22:23 -0500, Vasili I. Galchin vigalc...@gmail.com wrote: Hello, Before I found a really cool paper on Cabal motivation and architecture. I can no longer find this paper. Any ideas/suggestions? Is this what you are looking for? The Haskell Cabal: A Common Architecture for Building Applications and Tools by Isaac Jones, Simon Peyton Jones, Simon Marlow, Malcolm Wallace, and Ross Patterson http://www.haskell.org/cabal/proposal/ -- Benjamin L. Russell -- Benjamin L. Russell / DekuDekuplex at Yahoo dot com http://dekudekuplex.wordpress.com/ Translator/Interpreter / Mobile: +011 81 80-3603-6725 Furuike ya, kawazu tobikomu mizu no oto. -- Matsuo Basho^ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: a cool paper (.pdf) on Cabal?
On Thu, 11 Jun 2009 13:48:27 +0900, Benjamin L.Russell dekudekup...@yahoo.com wrote: On Wed, 10 Jun 2009 20:22:23 -0500, Vasili I. Galchin vigalc...@gmail.com wrote: Hello, Before I found a really cool paper on Cabal motivation and architecture. I can no longer find this paper. Any ideas/suggestions? Is this what you are looking for? The Haskell Cabal: A Common Architecture for Building Applications and Tools by Isaac Jones, Simon Peyton Jones, Simon Marlow, Malcolm Wallace, and Ross Patterson http://www.haskell.org/cabal/proposal/ Sorry, I forgot that you had specified a .pdf paper in the title. Then perhaps the following paper is what you are really looking for: Haskell: Batteries Included by Duncan Coutts, Isaac Potoczny-Jones, and Don Stewart http://www.cse.unsw.edu.au/~dons/papers/haskell31-coutts.pdf -- Benjamin L. Russell -- Benjamin L. Russell / DekuDekuplex at Yahoo dot com http://dekudekuplex.wordpress.com/ Translator/Interpreter / Mobile: +011 81 80-3603-6725 Furuike ya, kawazu tobikomu mizu no oto. -- Matsuo Basho^ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
