[Haskell-cafe] type trickery
Hello haskell-cafe! After making data Number = Zero | Succ Number an instance of Integral, I wondered how I could do the same with galois fields. So starting with Z mod p, I figured I'd need something like this data GF = GF Integer Integer so that each element of the finite field would remember p. However I can't think of a way to use the typesystem to ensure that p is always the same. I think that would need an infinite number of different types, but the type hackers here probably know something better. Adrian PGP.sig Description: Signierter Teil der Nachricht ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] type trickery
On Dec 20, 2007 9:34 AM, Adrian Neumann [EMAIL PROTECTED] wrote: Hello haskell-cafe! After making data Number = Zero | Succ Number an instance of Integral, I wondered how I could do the same with galois fields. So starting with Z mod p, I figured I'd need something like this data GF = GF Integer Integer so that each element of the finite field would remember p. However I can't think of a way to use the typesystem to ensure that p is always the same. I think that would need an infinite number of different types, but the type hackers here probably know something better. Yes, you can have some fun by taking your Number definition to the type level: data Zero-- phantom type, no implementation data Succ a -- same class Runtimify a where runtimify :: a - Integer instance Runtimify Zero where runtimify _ = 0 instance (Runtimify a) = Runtimify (Succ a) where runtimify _ = 1 + runtimify (undefined :: a) data GF p = GF Integer instance (Runtimify p) = Num (GF p) where -- you fill in the rest :-) Note that p is encoded in only a type variable, so you'll have to use runtimify (sorry for the silly name) to get it out. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
Joost Behrends wrote: since about three weeks i am learning Haskell now. One of my first exercises is to decompose an Integer into its primefactors. How about separating the candidate prime numbers from the recursion factorize :: Integer - [Integer] factorize = f primes' where primes' = 2:[3,5..] f (p:ps) n | r == 0= p : f (p:ps) q | p*p n = [n] | otherwise = f ps n where (q,r) = n `divMod` p For a faster factorization, just plug in a better primes' . Regards, apfelmus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Class deriving in GHC 6.8
Hello all!
How come in GHC 6.6 I could to write
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-}
data Foo = Foo deriving Show
data Bar c = Bar (c Foo) deriving Show
but in GHC 6.8.2 I get the error
No instance for (Show (c Foo))
arising from the 'deriving' clause of a data type declaration
at Ert.hs:3:0-37
Possible fix: add an instance declaration for (Show (c Foo))
When deriving the instance for (Show (Bar c))
Thanks,
/ Emil
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Haskell performance
Don, and others, This thread triggered something I've had at the back of my mind for some time. The traffic on Haskell Cafe suggests that there is a lot of interest in the performance of Haskell programs. However, at the moment we don't have any good *performance* regression tests for GHC. We have zillions of behavioural regression tests (this program should compile, this one should fail), but nothing much on performance. We have the nofib suite, but it's pretty static these days. Peter's set of benchmarks are great (if very specific to strings etc, but that's fine), and it'd be a pity of they now sink beneath the waves. What would be v helpful would be a regression suite aimed at performance, that benchmarked GHC (and perhaps other Haskell compilers) against a set of programs, regularly, and published the results on a web page, highlighting regressions. Kind of like the Shootout, only just for Haskell, and with many more programs. Like Hackage, it should be easy to add a new program. It'd be good to measure run-time, but allocation count, peak memory use, code size, compilation time are also good (and rather more stable) numbers to capture. Does anyone feel like doing this? It'd be a great service. No need to know anything much about GHC. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Don Stewart | Sent: 16 December 2007 23:22 | To: Peter Lund | Cc: haskell-cafe | Subject: Re: [Haskell-cafe] [RFC] benchmarks of bytestrings, teaser | | I've had a look at how some of the code was being compiled for | strict and lazy bytestrings, and also which rules weren't firing. | With some small tweaks the code seems back in good shape. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Dynamic typing of polymorphic functions
Alfonso Acosta wrote:
mapSY :: (Typeable a, Typeable b) = (a - b) - Signal a - Signal b
mapSY f (Signal primSig) = Signal (PrimSignal (MapSY (toDyn f) primSig))
The following process would be really useful but its compilation
obviously fails:
mapSnd :: Signal (a, a) - Signal a
mapSnd = mapSY snd
Could not deduce (Typeable a) from the context () arising from a
use of `mapSY'
Possible fix:
add (Typeable a) to the context of the type signature for `mapSnd'
It seems the compiler's complaint is reasonable. The signature of the
mapSY function says that mapSY may only be applied _provided_ that type
variables 'a' and 'b' are instantiated to the types that are members
of Typeable. That is, mapSY has a condition on its use. When you
write
mapSndInt :: Signal (Int, Int) - Signal Int
mapSndInt = mapSY (snd :: (Int, Int) - Int)
the condition is satisfied: 'a' and 'b' are instantiated to Int, and
Int is a member of Typeable. The definition of mapSnd has no
constraint. The compiler is upset: mapSY requires a condition, and
mapSnd does not provide any, and there is no obvious way how an
obligation Typeable a could have been satisfied otherwise. So, writing
mapSnd :: Typeable a = Signal (a, a) - Signal a
mapSnd = mapSY snd
is the logical thing to do.
Well, strangely enough, adding the Typeable a constraint hushed GHC
but an error was instead triggered at runtime.
Perhaps the latter is the real problem. If one switches to dynamic
typing, the type errors show up as run-time errors. I believe the
typing of eval is a bit odd (and also not very useful). The following
code seems to work. It also shows how to apply a polymorphic function,
pairing, to to signals of any type. Here's a test:
signal3 = cons const0 (cons const0 const1)
*Foo :t signal3
signal3 :: Signal (Int, (Int, Float))
test1 = mapSnd signal3
test1 :: Signal (Int, Float)
test12 = beval test1
*Foo :t test12
test12 :: (Int, Float)
*Foo test12
(0,1.0)
{-# OPTIONS -fglasgow-exts #-}
module Foo where
import Data.Typeable
import Data.Dynamic
-- the phantom type parameter makes signal typing consistent
newtype Signal a = Signal PrimSignal
newtype PrimSignal = PrimSignal (Proc (PrimSignal))
data Proc input = MapSY Dynamic -- The processing function
input -- The process input
-- the rest of the processes are omitted
| Const Dynamic
| Cons Dynamic input input
eval :: PrimSignal - Dynamic
-- evaluates the output of a process for one input
eval (PrimSignal (MapSY dynF dynIn)) = dynApp dynF (eval dynIn)
eval (PrimSignal (Cons cns a1 a2)) = dynApp (dynApp cns (eval a1)) (eval a2)
eval (PrimSignal (Const inp)) = inp
-- better eval
beval :: Typeable a = Signal a - a
beval (Signal s) = maybe undefined id (fromDynamic (eval s))
-- sample signals
const0 :: Signal Int
const0 = Signal (PrimSignal (Const (toDyn (0::Int
const1 :: Signal Float
const1 = Signal (PrimSignal (Const (toDyn (1::Float
-- the map process constructor
mapSY :: (Typeable a, Typeable b) = (a - b) - Signal a - Signal b
mapSY f (Signal primSig) = Signal (PrimSignal (MapSY (toDyn f) primSig))
add1 :: Signal Int - Signal Int
add1 = mapSY ((+1) :: Int - Int)
mapSndInt :: Signal (Int, Int) - Signal Int
mapSndInt = mapSY (snd :: (Int, Int) - Int)
-- it is important to give the signature to (,) below: we pack the cons
-- function of the right type!
cons :: forall a b. (Typeable a, Typeable b) =
Signal a - Signal b - Signal (a,b)
cons (Signal sig1) (Signal sig2) =
Signal (PrimSignal (Cons (toDyn ((,)::a-b-(a,b))) sig1 sig2))
mapSnd :: (Typeable a, Typeable b) = Signal (b, a) - Signal a
mapSnd = mapSY snd
signal3 = cons const0 (cons const0 const1)
-- *Foo :t signal3
-- signal3 :: Signal (Int, (Int, Float))
test1 = mapSnd signal3
-- test1 :: Signal (Int, Float)
test11 = let Signal s = test1 in eval s
-- *Foo test11
-- (Int,Float)
-- Too bad. But we can do better.
test12 = beval test1
{-
*Foo :t test12
test12 :: (Int, Float)
*Foo test12
(0,1.0)
-}
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class deriving in GHC 6.8
After looking more closely at user's manual, I just found that the following
works:
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-}
data Foo = Foo deriving Show
data Bar c = Bar (c Foo)
deriving instance Show (c Foo) = Show (Bar c)
/ Emil
On 2007-12-20 11:18, Emil Axelsson wrote:
Hello all!
How come in GHC 6.6 I could to write
{-# OPTIONS_GHC -fglasgow-exts -fallow-undecidable-instances #-}
data Foo = Foo deriving Show
data Bar c = Bar (c Foo) deriving Show
but in GHC 6.8.2 I get the error
No instance for (Show (c Foo))
arising from the 'deriving' clause of a data type declaration
at Ert.hs:3:0-37
Possible fix: add an instance declaration for (Show (c Foo))
When deriving the instance for (Show (Bar c))
Thanks,
/ Emil
___
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] Haskell performance
* Simon Peyton-Jones wrote: Does anyone feel like doing this? It'd be a great service. No need to know anything much about GHC. I'd like to do that. For a lecture I'm already generated performance tests for various sorting algorithms. It's designed about a function performance :: Size - IO RunsPerSecond. So with unsafePerformIO it is a good candidate for quickCheck. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: type trickery
Adrian Neumann wrote: I figured I'd need something like this data GF = GF Integer Integer so that each element of the finite field would remember p. However I can't think of a way to use the typesystem to ensure that p is always the same. You might like: Vectro: Haskell library for statically typed linear algebra http://ofb.net/~frederik/stla/ which marks each element of a vector space with its dimension. The type system makes sure that you can only add vectors of the same dimension (the type system does even more: it computes the dimension of a result of multiplying a vector by a non-square matrix, for example). I think that would need an infinite number of different types, You think correctly. Haskell already has the infinite number of different types (e.g., the infinite number of function types). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] [RFC] Preliminary benchmark graphs
I added Don's three benchmarks and redid all my benchmarks with: ghc 6.6.1 ghc 6.8.2 ghc 6.8.2 + bytestring 0.9.0.2 ghc 6.9.20071119 ghc 6.9.20071119 + bytestring 0.9.0.2 ghc head-as-of-yesterday-around-noon ghc head-as-of-yesterday-around-noon + bytestring 0.9.0.2 I tried to get the draft emails with intro, methodology, discussion, and conclusion completed yesterday but my brain simply wasn't up to it. Unfortunately, it still isn't quite up to it :( Since the perfect is the enemy of the good, I'll post the graphs for all the above 7 runs now. The rest will be forthcoming when I can think straight again, hopefully some time in the evening. I have scripts to help me install precisely the ghc version I want (and to make it easy to duplicate my results). I also have scripts to run the benchmarks, get correct memory measurements (-sstderr doesn't seem trustworthy), check the validity of each timing measurement, generate I/O traces, generate reports, and finally merging reports from different runs with or without rescaling. This attached report uses rescaling since I'm compiling different compiler/library combinations on the same machine. One thing that shows up very clearly in the graphs is that the memory situation is bad and that Don's recent fix only really solves the problem on 6.8.2, not on head. Another thing is that the backend really lets us down. I have hand-tweaked a simple byte counting benchmark and a simple space counting benchmark through increasing degrees of refinement from the banal to the heroic and timed those, too. It seems like improved register use alone would halve the run time. Add a sprinkling of MMX heroics and things get even better (but that's not realistic or even a good idea at the moment). The reason why lazy bytestrings perform so badly, speed-wise, is most likely a backend that doesn't do hoisting of bounds checks out of loops. -Peter charybdis ghc 6.6.1 AMD Athlon(tm) 64 Processor 3000+ 2009.160 MHz TESTKIND=THOROUGH SUFFIX= charybdis ghc 6.8.2 AMD Athlon(tm) 64 Processor 3000+ 2009.160 MHz TESTKIND=THOROUGH SUFFIX= charybdis ghc 6.8.2 AMD Athlon(tm) 64 Processor 3000+ 2009.160 MHz TESTKIND=THOROUGH SUFFIX=-bs0.9.0.2 charybdis ghc 6.9.20071119 AMD Athlon(tm) 64 Processor 3000+ 2009.160 MHz TESTKIND=THOROUGH SUFFIX= charybdis ghc 6.9.20071119 AMD Athlon(tm) 64 Processor 3000+ 2009.160 MHz TESTKIND=THOROUGH SUFFIX=-bs0.9.0.2 charybdis ghc 6.9.20071217 AMD Athlon(tm) 64 Processor 3000+ 2009.160 MHz TESTKIND=THOROUGH SUFFIX= charybdis ghc 6.9.20071217 AMD Athlon(tm) 64 Processor 3000+ 2009.160 MHz TESTKIND=THOROUGH SUFFIX=-bs0.9.0.2 Time (byte counting) std avg dev slack hs/byte-bsacc: 1.020 40‰ 0.0 █▏| -- 0.703 5‰ 0.4 ███▌ | -- 0.702 7‰ 0.3 ███▌ | -- 0.705 7‰ 0.1 ███▋ | -- 0.712 3‰ 0.1 ███▋ | -- 0.706 7‰ 0.1 ███▋ | -- 0.707 7‰ 0.9 ███▋ | hs/byte-bsfoldlx:0.789 3‰ 0.3 | -- 0.993 2‰ 0.2 █ | -- 1.102 1‰ 0.2 █▋| -- 1.002 1‰ 0.5 █▏| -- 1.112 1‰ 0.3 █▋| -- 1.024 2‰ 0.2 █▏| -- 1.111 1‰ 0.1 █▋| hs/byte-bsfoldrx:0.813 3‰ 0.1 ▏ | -- 1.102 2‰ 0.3 █▋| -- 1.100 1‰ 0.1 █▋| -- 1.112 2‰ 0.1 █▋| -- 1.114 1‰ 0.4 █▋| -- 1.113 2‰ 0.5 █▋| -- 1.112 1‰ 0.2 █▋| hs/byte-bsl---acc: 3.599 13‰ 0.0 ██▎ | -- 2.609 17‰ 0.0 █▎| -- 2.560 15‰ 0.1 █ | -- 2.595 14‰ 0.1 █▏| -- 2.574 16‰ 0.1 █ | -- 2.613 12‰ 0.2 █▎| -- 2.656 44‰ 0.1 █▌| hs/byte-x-acc-1: 4.606 5‰
Re: [Haskell-cafe] Haskell performance
Simon Peyton-Jones [EMAIL PROTECTED] wrote: What would be v helpful would be a regression suite aimed at performance, that benchmarked GHC (and perhaps other Haskell compilers) against a set of programs, regularly, and published the results on a web page, highlighting regressions. Something along these lines already exists - the nobench suite. darcs get http://www.cse.unsw.edu.au/~dons/code/nobench It originally compared ghc, ghci, hugs, nhc98, hbc, and jhc. (Currently the results at http://www.cse.unsw.edu.au/~dons/nobench.html compare only variations of ghc fusion rules.) I have just been setting up my own local copy - initial results at http://www.cs.york.ac.uk/fp/nobench/powerpc/results.html where I intend to compare ghc from each of the 6.4, 6.6 and 6.8 branches, against nhc98 and any other compilers I can get working. I have powerpc, intel, and possibly sparc machines available. Like Hackage, it should be easy to add a new program. Is submitting a patch against the darcs repo sufficiently easy? Should we move the master darcs repo to somewhere more accessible, like code.haskell.org? It'd be good to measure run-time, Done... but allocation count, peak memory use, code size, compilation time are also good (and rather more stable) numbers to capture. Nobench does already collect code size, but does not yet display it in the results table. I specifically want to collect compile time as well. Not sure what the best way to measure allocation and peak memory use are? Regards, Malcolm ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell performance
On Thu, 2007-12-20 at 10:37 +, Simon Peyton-Jones wrote: Don, and others, This thread triggered something I've had at the back of my mind for some time. The traffic on Haskell Cafe suggests that there is a lot of interest in the performance of Haskell programs. However, at the moment we don't have any good *performance* regression tests for GHC. We have zillions of behavioural regression tests (this program should compile, this one should fail), but nothing much on performance. We have the nofib suite, but it's pretty static these days. Peter's set of benchmarks are great (if very specific to strings etc, but that's fine), and it'd be a pity of they now sink beneath the waves. They won't! I have set up a mercurial repository on http://vax64.dyndns.org/repo/hg/ together with the ghc install scripts I've used. Once the basic string performance is under control, I intend to expand it with more advanced parsing, with I/O, and with backend stuff. I like Parsec. But it seems to hang on to a bit more memory than it should and I think it should be faster than it is. Fast I/O is not simple, and to do it really well, one probably needs to use threading and mmap() in combination. mmap() alone is usually not very performant unless the file has already been cached by the operating system. And the backend. Ouch. The frontend is absolutely fantastic and does heroic stuff -- but the backend... apart from having many phases, it doesn't do much ;) What would be v helpful would be a regression suite aimed at performance, that benchmarked GHC (and perhaps other Haskell compilers) against a set of programs, regularly, and published the results on a web page, highlighting regressions. Kind of like the Shootout, only just for Haskell, and with many more programs. I don't see why a lot of that couldn't be added to the framework I have. It's GPLv2 :) Like Hackage, it should be easy to add a new program. It'd be good to measure run-time, but allocation count, peak memory use, code size, My framework captures the allocation count but it doesn't use it for anything. It gets its peak memory info from /proc/self/status (which it captures, together with /proc/self/maps, through a LD_PRELOAD trick). '-sstderr' seemed a bit unreliable in my experience, so I fell back to asking the operating system. Making sure one gets stable times + a good estimate of the quality of the measurements is also important (which my code already does). compilation time are also good (and rather more stable) numbers to capture. Does anyone feel like doing this? It'd be a great service. No need to know anything much about GHC. I think I've made a start but this is clearly not something I'm willing to take on by myself. -Peter ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [HXT] Simple question
Hi Fernand, Everything works fine except for the fact that all the nodes « this /this » (that is, a space (an XML text node whose contents are a single space character) within a this element node) get transformed to a « this/ » element I can't really reproduce this: A simple ghci session gives the following: --- [EMAIL PROTECTED]:~/haskell/hxt/curr/examples/arrows/HelloWorld ghci HelloWorld.hs GHCi, version 6.8.1: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling Main ( HelloWorld.hs, interpreted ) Ok, modules loaded: Main. *Main runX $ (readString [(a_validate,v_0)] x /x writeDocumentToString []) Loading ... ... [?xml version=\1.0\ encoding=\UTF-8\?\nx /x] *Main runX $ ( readString [(a_validate,v_0)] x /x setTraceLevel 4 traceDoc doc after reading setTraceLevel 0 writeDocumentToString []) -- (1) doc after reading x /x content of: x /x == ---XTag / | source=\x /x\ | encoding=UNICODE | transfer-URI=string: | transfer-Message=OK | transfer-Status=200 | transfer-Encoding=UNICODE | +---XTag x | +---XText [?xml version=\1.0\ encoding=\UTF-8\?\nx /x] *Main -- So there is a text node containing the space char after parsing and it stays in the output document. Cheer, Uwe -- Web: http://www.fh-wedel.de/~si/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [HXT] Simple question
I can't really reproduce this: A simple ghci session gives the following: --- [EMAIL PROTECTED]:~/haskell/hxt/curr/examples/arrows/HelloWorld ghci HelloWorld.hs GHCi, version 6.8.1: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. [1 of 1] Compiling Main ( HelloWorld.hs, interpreted ) Ok, modules loaded: Main. *Main runX $ (readString [(a_validate,v_0)] x /x writeDocumentToString []) Loading ... ... [?xml version=\1.0\ encoding=\UTF-8\?\nx /x] Try xy /y/x and a_indent writing option. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [HXT] Simple question
Hi Miguel, Hmmm, with 'readString ... this /this' everything works fine, but with 'readString ... itemsthis /this/items' it doesn't. Seems to be a bug in HXT. I don't see the bug: -- *Main runX $ ( readString [(a_validate,v_0)] itemsthis /this/items setTraceLevel 4 traceDoc doc after reading setTraceLevel 0 writeDocumentToString []) -- (1) doc after reading items this/ /items content of: itemsthis /this/items === ---XTag / | source=\itemsthis /this/items\ | encoding=UNICODE | transfer-URI=string: | transfer-Message=OK | transfer-Status=200 | transfer-Encoding=UNICODE | +---XTag items | +---XTag this | +---XText [?xml version=\1.0\ encoding=\UTF-8\?\nitemsthis /this/items] *Main - the space remains there and not element with empty contents occurs Cheers, Uwe -- Web: http://www.fh-wedel.de/~si/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance
* Malcolm Wallace wrote: Something along these lines already exists - the nobench suite. Ok, your turn. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Knowledge
jlw501 wrote: I'm new to functional programming and Haskell and I love its expressive ability! I've been trying to formalize the following function for time. Given people and a piece of information, can all people know the same thing? Anyway, this is just a bit of fun... but can anyone help me reduce it or talk about strictness and junk as I'd like to make a blog on it? I don't think your representation of unknown information is reasonable. Haskell is not lazy enough to make it work out: Prelude True || undefined True Prelude undefined || True *** Exception: Prelude.undefined From a logic perspective, unknown || true == true || unknown == true. But this behaviour is impossible to implement in Haskell with unknown = undefined, because you don't know in advance wich argument you should inspect first. if you choose the undefined one, you will loop forever without knowing the other argument would have been true. In theoretical computer science, you would use a growing resource bound to simulate the parallel evaluation of the two arguments. Maybe you can use multithreading to implement the same trick in Haskell, but it remains a trick. So what can you do instead? I would encode the idea of unknown information using an algebraic data type: data Modal a = Known a | Unknown deriving Show We can express knowing that something is true as (Known True), not knowing anything as (Unknown) and knowing something as (Known undefined). The advantage of this aproach is that we can define our operations as strict or nonstrict as we want by pattern matching on the Modal constructors. () :: Modal Bool - Modal Bool - Modal Bool Known True Known True = Known True Known False _ = Known False _Known False = Known False __ = Unknown (|||) :: Modal Bool - Modal Bool - Modal Bool Known False ||| Known False = Known False Known True ||| _ = Known True _ ||| Known True = Known True _ ||| _ = Unknown not' :: Modal Bool - Modal Bool not' (Known True) = Known False not' (Known False) = Known True not' Unknown = Unknown By strictness, I'm not talking about Haskell strictness, but about Modal strictness, that is: A function (f :: Modal a - Modal b) is Modal strict if and only if f Unknown = Unknown A nice property of modal strictness is that we can test for it. given a total function f, we can use isModalStrict :: (Modal a - Modal b) - Bool isModalStrict f = case f Unknown of Unknown - True _ - False to so wether it is strict. The results are as expected: *Truth isModalStrict not' True *Truth isModalStrict (Known True |||) False *Truth isModalStrict (Known True ) True *Truth isModalStrict ( Known False) False Let's compare the last case to the representation unknown = undefined: *Truth ( False) undefined *** Exception: Prelude.undefined As expected, ( False) is Haskell strict, but ( Known False) not Modal strict. I don't know if this will help you, in the end you may find that Haskell is a programming language, not a theorem prover. But at least for me, it seems better to encode information explicitly instead of using undefined to encode something. Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [HXT] Simple question
Prelude Text.XML.HXT.Arrow runX $ ( readString [(a_validate,v_0)] xy /y/x setTraceLevel 4 traceDoc doc after reading s etTraceLevel 0 writeDocumentToString [(a_indent, v_1)]) -- (1) doc after reading x y/ /x content of: xy /y/x = ---XTag / | source=\xy /y/x\ | encoding=UNICODE | transfer-URI=string: | transfer-Message=OK | transfer-Status=200 | transfer-Encoding=UNICODE | +---XTag x | +---XTag y | +---XText [?xml version=\1.0\ encoding=\UTF-8\?\nx\n y/\n/x\n] We can see that the text node is here, but the y node is displayed as an empty node ! Thank you everyone, I report this to the HXT team. Fernand ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: #haskell works
Tim Chevalier wrote: On 12/14/07, Dan Piponi [EMAIL PROTECTED] wrote: There have been some great improvements in array handling recently. I decided to have a look at the assembly language generated by some simple array manipulation code and understand why C is at least twice as fast as ghc 6.8.1. One the one hand it was disappointing to see that the Haskell register allocator seems a bit inept and was loading data into registers that should never have been spilled out of registers in the first place. Someone who knows the backend better than I do can correct me if I'm wrong, but it's my understanding that GHC 6.8.1 doesn't even attempt to do any register allocation on x86. So -- register allocator? What register allocator? That's not entirely true - there is a fairly decent linear-scan register allocator in GHC http://darcs.haskell.org/ghc/compiler/nativeGen/RegAllocLinear.hs the main bottleneck is not the quality of the register allocation (at least, not yet). The first problem is that in order to get good performance when compiling via C we've had to lock various global variables into registers (the heap pointer, stack pointer etc.), which leaves too few registers free for argument passing on x86, so the stack is used too much. This is probably why people often say that the register allocator sucks - in fact it is really the calling convention that sucks. There is some other stupidness such as reloading values from the stack, though. Another problem is that the backend doesn't turn recursion into loops (i.e. backward jumps), so those crappy calling conventions are used around every loop. If we fixed that - which is pretty easy, we've tried it - then the bottleneck becomes the lack of loop optimisations in the native code generator, and we also run into the limitations of the current register allocator. Fortunately the latter has been fixed: Ben Lippmeier has written a graph-colouring allocator, and it's available for trying out in GHC HEAD. Fixing it all properly means some fairly significant architectural changes, and dropping the via-C backend (except for bootstrapping on new platforms), which is what we'll be doing in 6.10. I'd expect to see some dramatic improvements for those tight loops, in ByteString for example, but for typical Haskell code and GHC itself I'll be pleased if we get 10%. We'll see. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell performance
Malcolm Wallace wrote: Simon Peyton-Jones [EMAIL PROTECTED] wrote: What would be v helpful would be a regression suite aimed at performance, that benchmarked GHC (and perhaps other Haskell compilers) against a set of programs, regularly, and published the results on a web page, highlighting regressions. Something along these lines already exists - the nobench suite. darcs get http://www.cse.unsw.edu.au/~dons/code/nobench It originally compared ghc, ghci, hugs, nhc98, hbc, and jhc. (Currently the results at http://www.cse.unsw.edu.au/~dons/nobench.html compare only variations of ghc fusion rules.) I have just been setting up my own local copy - initial results at http://www.cs.york.ac.uk/fp/nobench/powerpc/results.html where I intend to compare ghc from each of the 6.4, 6.6 and 6.8 branches, against nhc98 and any other compilers I can get working. I have powerpc, intel, and possibly sparc machines available. That's great. BTW, GHC has a performance bug affecting calendar at the moment: http://hackage.haskell.org/trac/ghc/ticket/1168 The best GHC options for this program might therefore be -O2 -fno-state-hack. Or perhaps just -O0. Like Hackage, it should be easy to add a new program. Is submitting a patch against the darcs repo sufficiently easy? Should we move the master darcs repo to somewhere more accessible, like code.haskell.org? Yes, please do. When I have a chance I'd like to help out. It'd be good to measure run-time, Done... but allocation count, peak memory use, code size, compilation time are also good (and rather more stable) numbers to capture. Nobench does already collect code size, but does not yet display it in the results table. I specifically want to collect compile time as well. Not sure what the best way to measure allocation and peak memory use are? With GHC you need to use +RTS -s and then slurp in the prog.stat file. You can also get allocations, peak memory use, and separate mutator/GC times this way. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell performance
Simon Marlow wrote: Nobench does already collect code size, but does not yet display it in the results table. I specifically want to collect compile time as well. Not sure what the best way to measure allocation and peak memory use are? With GHC you need to use +RTS -s and then slurp in the prog.stat file. You can also get allocations, peak memory use, and separate mutator/GC times this way. Oh, and one more thing. We have this program called nofib-analyse in GHC's source tree: http://darcs.haskell.org/ghc/utils/nofib-analyse which takes the output from a couple of nofib runs and generates nice tables, in ASCII or LaTeX (for including in papers, see e.g. our pointer-tagging paper from ICFP'07). The only reason we haven't switched to using nobench for GHC is the existence of this tool. Unfortuantely it relies on specifics of the output generated by a nofib run, and uses a Perl script, etc. etc. The point is, it needs some non-trivial porting. I'm pointing this out just in case you or anyone else felt enthusiastic enough to port this to nobench, and to hopefully head off any duplication of effort. Failing that, I'll probably get around to porting it myself at some point. Cheers, Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Storable types
Hi, I'm newbie in Haskell, and I have some doubts... In this programming language, do we have storable values? Case affirmative, what are the storable types in Haskell, and how can I implement then... thanks! -- Clerton Ribeiro de Araujo Filho Graduando em Ciência da Computação Integrante do PET - Programa de Educação Tutorial Integrante do LIA - Laboratório de Inteligência Artificial Universidade Federal de Campina Grande - UFCG ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Storable types
Hallo fellow Brazilian, Clerton Filho escreveu: Hi, I'm newbie in Haskell, and I have some doubts... In this programming language, do we have storable values? Case affirmative, what are the storable types in Haskell, and how can I implement then... What exactly is a storable type? -alex ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Storable types
On Thu, 20 Dec 2007, Alex Sandro Queiroz e Silva wrote: Hallo fellow Brazilian, Clerton Filho escreveu: Hi, I'm newbie in Haskell, and I have some doubts... In this programming language, do we have storable values? Case affirmative, what are the storable types in Haskell, and how can I implement then... What exactly is a storable type? I guess you mean: http://haskell.org/ghc/docs/latest/html/libraries/base/Foreign-Storable.html A type becomes storable by implementing the Storable methods, namely sizeOf, aligment, peek, poke. To this end you can convert to and access the Storable methods of CInt, CDouble and friends. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Storable types
Clerton Filho wrote: Hi, I'm newbie in Haskell, and I have some doubts... In this programming language, do we have storable values? Case affirmative, what are the storable types in Haskell, and how can I implement then... Not entirely sure what you mean. There is a haskell typeclass called Storable, but it probably isn't what you mean. If you want persistence, serialisation, we have two options: Read/Show is simple, slow and text-based. It's very helpful for debugging but not for high performance. Data.Binary is fast, configurable and binary. That's a good solution for high-throughput persistence. If you need versioning support, then the upper layer of Binary isn't for you. But the guts of binary, called Get and Put, make it simple to write your own versioned persistence. Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: #haskell works
On 12/20/07, Simon Marlow [EMAIL PROTECTED] wrote: That's not entirely true - there is a fairly decent linear-scan register allocator in GHC http://darcs.haskell.org/ghc/compiler/nativeGen/RegAllocLinear.hs the main bottleneck is not the quality of the register allocation (at least, not yet). The first problem is that in order to get good performance when compiling via C we've had to lock various global variables into registers (the heap pointer, stack pointer etc.), which leaves too few registers free for argument passing on x86, so the stack is used too much. This is probably why people often say that the register allocator sucks - in fact it is really the calling convention that sucks. There is some other stupidness such as reloading values from the stack, though. [snipped further reasons] Thanks for enlightening me. (I had been opting to believe the various rumor and hearsay floating around rather than actually reading the source :-) One reason why I care about this is that over the summer I was trying to do some performance measurements for House. One of the experiments I did was measuring how long it took to run a loop of Haskell code that just did a no-op FFI call. This was still ten times slower than a loop in C that called the same no-op function. I looked at the generated code (with the native-code backend), noticed the issues you mentioned above (reloading values from the stack, and so on), and concluded that there was probably a good reason why the backend was being worked on actively. The -fvia-C code wasn't much better. However, this was with GHC 6.2, so obviously this suggests that porting House to a newer GHC version might be worthwhile for us to do :-) Cheers, Tim -- Tim Chevalier * catamorphism.org * Often in error, never in doubt Dare to be naive.--R. Buckminster Fuller ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [HXT] Simple question
Hi Miguel, Try xy /y/x and a_indent writing option. yes, with the indent option set, whitespace becomes insignificant and will change during formating, and so the contents of the inner element reduces to empty Turn of the indentation and you get the result you want. Cheers, Uwe -- Web: http://www.fh-wedel.de/~si/ Sitz der Gesellschaft: Wedel Registergericht: Amtsgericht Pinneberg HRB 1578 Geschaeftsfuehrung: Prof. Dr. Dirk Harms ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
I'm really inexperienced at this :
---
{-# OPTIONS_GHC -fglasgow-exts -funbox-strict-fields
-fallow-undecidable-instances -O2 #-}
class Gadget g where
fInit :: g - a - g
data FString = FString !Int !String deriving Show
instance Gadget FString where
fInit (FString n _) s = FString n (take n s)
-
I get the error message :
Couldn't match expected type `String' against inferred type `a'
`a' is a rigid type variable bound by
the type signature for `fInit' at Gadget.hs:4:17
In the second argument of `FString', namely `s'
In the expression: FString n s
In the definition of `fInit': fInit (FString n _) s = FString n s
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Creating a type for a subset of the integers
On Wed, 19 Dec 2007 02:00:53 -0500, Jules Bean [EMAIL PROTECTED] wrote: Brad Larsen wrote: Hi there list, How would one go about creating a new type for a subset of the integers, for (contrived) example just the even integers? I was thinking of making a new type newtype EvenInt = EvenInt Integer but the problem with this is that it accepts any integer, even odd ones. So to prevent this, the module does not export the constructor for it---rather, the module exports a function `mkEvenInt' that creates an EvenInt if the given value is acceptable or raises an error otherwise. What's the right way to do this? Thanks! There are two ways: (1) Have a representation which admits invalid values, and provide combinators which only perfect validity, and prove that consumers using your combinators can't produce invalid values. (2) Have a cleverly designed representation such that every representation is valid. An example here, for (2) would be to store n/2; there is a bijection between 'Integer' and 'EvenInt' given by n/2. To make sure I understand, an example of (1) would be to export only a ``smart constructor'' that somehow converts invalid values to valid ones (say, add 1 to arguments that are odd)? In your example of 2, how would you go about storing n/2? Store just n as in (newtype EvenInt = EvenInt Integer) and then write all functions that deal with EvenInts so that they account for the division by two? In real, more complex problems, (2) often isn't possible and we resort to (1). E.g. the representation of balanced trees (AVL? RedBlack?) admits invalid values (both unbalanced trees and out-of-order trees) and we rely on the reduced set of combinators never to generate one. Jules In my particular case, or what I actually want to do, is define a finite segment of the integers (0-42, say) as a new type and have that checked at compile time. Any way of doing this w/o defining Peano numbers or a whole bunch of nullary constructors (i.e. I'm hoping to be able to define a type whose constructor will accept only Integer arguments between 0 and 42)? Thanks! Brad ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
david48 wrote:
| I'm really inexperienced at this :
class Gadget g where
fInit :: g - a - g
data FString = FString !Int !String deriving Show
instance Gadget FString where
fInit (FString n _) s = FString n (take n s)
The types of:
fInit :: g - a - g
and:
take :: Int - [a] - [a]
cause the mismatched types error.
You're trying to apply 'take n' to a value of type 'a' ('take n'
requires [a]), moreover putting the value of 'take n s' into the FString
further constrains its type to be [Char] == String.
So either fix the Gadget g class, or fix the Gadget FString instance.
Claude
--
http://claudiusmaximus.goto10.org
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Creating a type for a subset of the integers
Brad Larsen wrote: On Wed, 19 Dec 2007 02:00:53 -0500, Jules Bean [EMAIL PROTECTED] wrote: Brad Larsen wrote: Hi there list, How would one go about creating a new type for a subset of the integers, for (contrived) example just the even integers? I was thinking of making a new type newtype EvenInt = EvenInt Integer but the problem with this is that it accepts any integer, even odd ones. So to prevent this, the module does not export the constructor for it---rather, the module exports a function `mkEvenInt' that creates an EvenInt if the given value is acceptable or raises an error otherwise. What's the right way to do this? Thanks! There are two ways: (1) Have a representation which admits invalid values, and provide combinators which only perfect validity, and prove that consumers using your combinators can't produce invalid values. (2) Have a cleverly designed representation such that every representation is valid. An example here, for (2) would be to store n/2; there is a bijection between 'Integer' and 'EvenInt' given by n/2. To make sure I understand, an example of (1) would be to export only a ``smart constructor'' that somehow converts invalid values to valid ones (say, add 1 to arguments that are odd)? I just meant one that throws a runtime error if they are not. In your example of 2, how would you go about storing n/2? Store just n as in (newtype EvenInt = EvenInt Integer) and then write all functions that deal with EvenInts so that they account for the division by two? You would store n/2. So 8 would be represented as EvenInt 4, 14 as EvenInt 7. Then you write the num instance to account for the division. Check out the num instance in Data.Fixed for an example. In real, more complex problems, (2) often isn't possible and we resort to (1). E.g. the representation of balanced trees (AVL? RedBlack?) admits invalid values (both unbalanced trees and out-of-order trees) and we rely on the reduced set of combinators never to generate one. Jules In my particular case, or what I actually want to do, is define a finite segment of the integers (0-42, say) as a new type and have that checked at compile time. Any way of doing this w/o defining Peano numbers or a whole bunch of nullary constructors (i.e. I'm hoping to be able to define a type whose constructor will accept only Integer arguments between 0 and 42)? Not at compile-time, no. The best you can do is runtime error. There is no compile-time facility to check that an Int lies in a particular range. Consider, for example, that the int might not be known at compiletime: do id - myThreadID return (MkSmallInt id) ^^ how can the compiler know? In general, of course, the question of calculating if an int is under 42 at compile time is the question of partial evaluation. Partial evaluation at compile time is flat-out impossible for IO actions, and although it's possible for pure functions, GHC doesn't do it to any significant extent. (It would make the compiler potentially non-terminating, of course!) Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
On Dec 20, 2007 5:03 PM, Claude Heiland-Allen
[EMAIL PROTECTED] wrote:
You're trying to apply 'take n' to a value of type 'a' ('take n'
requires [a]), moreover putting the value of 'take n s' into the FString
further constrains its type to be [Char] == String.
First of all, thanks a lot for your reply.
I thought that in this case my type a was String ( which I know is [Char] )
since I give fInit a value of type g ( FString n _ ) and a value of type a ( s )
and I return a value of type g ( FString n (take n s) )
David
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
david48 wrote: class Gadget g where fInit :: g - a - g data FString = FString !Int !String deriving Show instance Gadget FString where at this point fInit has this type: FString - a - FString fInit (FString n _) s = FString n (take n s) but your implementation has this type FString - String - FString These types are incompatible, your fInit implementation should be able to work with whatever type a the caller has choosen to provide. Maybe you should try one of class Gadget g where fInit :: g - String - g or class Gadget g a where fInit :: g - a - g instead. Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
Tillmann Rendel wrote: david48 wrote: class Gadget g where fInit :: g - a - g Tillman's two suggestions (below) are probably your answer. Just to say what everyone else has said in a bunch of different ways: your class says that for ANY Gadget, fInit will work with ANY OTHER type a. This doesn't seem to be what you want. There are three things you might want: 1. Maybe you want a to always be String. Easy. fInit :: g - String - g 2. Maybe you want lots of possible different as for each g. Then you make a a parameter of the class too. 3. Maybe you want just one particular a for each g. I.e. g determines a. Then you can proceed as for (2), but add the functional dependency | g - a These types are incompatible, your fInit implementation should be able to work with whatever type a the caller has choosen to provide. Maybe you should try one of class Gadget g where fInit :: g - String - g or class Gadget g a where fInit :: g - a - g ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
On Dec 20, 2007 5:26 PM, Tillmann Rendel [EMAIL PROTECTED] wrote: at this point fInit has this type: FString - a - FString fInit (FString n _) s = FString n (take n s) but your implementation has this type FString - String - FString These types are incompatible, your fInit implementation should be able to work with whatever type a the caller has choosen to provide. Maybe That was a very clear explanation of what's wrong, thanks a lot ! you should try one of class Gadget g where fInit :: g - String - g This will not do, I want instances of gadget that work with other values than string. or class Gadget g a where fInit :: g - a - g A bit of explanation. I want types of class Gadget to be able to hold values of some type. for example, some of the types in the class Gadget would hold strings, some would hold Integers. With a variable of a type belonging to the class Gadget, I want to be able to - Initialise it - Fetch the value it holds - Have the user input the value - Display the value To keep it simple, in this example I only kept the funtion to initialise. So it seems I have to use the multiparameter class version, but I'm stuck here as well : class Gadget g a where fInit :: g - a - g data FString = FString !Int !String deriving Show instance Gadget FString String where fInit (FString n _) s = FString n (take n s) fString :: Int - FString fString n = FString n -- *Main :r [1 of 1] Compiling Main ( Gadget.hs, interpreted ) Ok, modules loaded: Main. *Main fString 5 interactive:1:0: Couldn't match expected type `[Char] - t' against inferred type `FString' In the expression: fString 5 In the definition of `it': it = fString 5 *Main ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
On Dec 20, 2007 5:44 PM, david48 [EMAIL PROTECTED] wrote: fString :: Int - FString fString n = FString n Oo do I feel dumb for writing this ! Problem solved :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Class/Instance : what am I doing wrong in this example ?
On Dec 20, 2007 5:36 PM, Jules Bean [EMAIL PROTECTED] wrote: 2. Maybe you want lots of possible different as for each g. Then you make a a parameter of the class too. 3. Maybe you want just one particular a for each g. I.e. g determines a. Then you can proceed as for (2), but add the functional dependency | g - a Practically, what would be the difference between 2. and 3. ? David. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] [RFC] Preliminary benchmark graphs
firefly: I added Don's three benchmarks and redid all my benchmarks with: ghc 6.6.1 ghc 6.8.2 ghc 6.8.2 + bytestring 0.9.0.2 ghc 6.9.20071119 ghc 6.9.20071119 + bytestring 0.9.0.2 ghc head-as-of-yesterday-around-noon ghc head-as-of-yesterday-around-noon + bytestring 0.9.0.2 One thing that shows up very clearly in the graphs is that the memory situation is bad and that Don's recent fix only really solves the problem on 6.8.2, not on head. Can you pinpoint specific programs, with either ghc 6.8.2 or head, that allocate too much? That's likely to be a library issue that I can address in ByteString. I'd need the source program, whether it is with ghc 6.8.2 or ghc head, and what compiler flags (and input size). Low level loop/performance issues go to SimonM (i.e. if its allocating fine, the core is perfect, but just too slow). -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Haskell performance
simonpj: Don, and others, This thread triggered something I've had at the back of my mind for some time. The traffic on Haskell Cafe suggests that there is a lot of interest in the performance of Haskell programs. However, at the moment we don't have any good *performance* regression tests for GHC. We have zillions of behavioural regression tests (this program should compile, this one should fail), but nothing much on performance. We have the nofib suite, but it's pretty static these days. Peter's set of benchmarks are great (if very specific to strings etc, but that's fine), and it'd be a pity of they now sink beneath the waves. What would be v helpful would be a regression suite aimed at performance, that benchmarked GHC (and perhaps other Haskell compilers) against a set of programs, regularly, and published the results on a web page, highlighting regressions. Kind of like the Shootout, only just for Haskell, and with many more programs. Like Hackage, it should be easy to add a new program. It'd be good to measure run-time, but allocation count, peak memory use, code size, compilation time are also good (and rather more stable) numbers to capture. Does anyone feel like doing this? It'd be a great service. No need to know anything much about GHC. Ok, so I should revive nobench then, I suspect. http://www.cse.unsw.edu.au/~dons/nobench/x86_64/results.html that kind of thing? I'll see now far I can get updating the graph for the current suite of compilers. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskell performance
Malcolm.Wallace: Simon Peyton-Jones [EMAIL PROTECTED] wrote: What would be v helpful would be a regression suite aimed at performance, that benchmarked GHC (and perhaps other Haskell compilers) against a set of programs, regularly, and published the results on a web page, highlighting regressions. Something along these lines already exists - the nobench suite. darcs get http://www.cse.unsw.edu.au/~dons/code/nobench It originally compared ghc, ghci, hugs, nhc98, hbc, and jhc. (Currently the results at http://www.cse.unsw.edu.au/~dons/nobench.html compare only variations of ghc fusion rules.) I have just been setting up my own local copy - initial results at http://www.cs.york.ac.uk/fp/nobench/powerpc/results.html where I intend to compare ghc from each of the 6.4, 6.6 and 6.8 branches, against nhc98 and any other compilers I can get working. I have powerpc, intel, and possibly sparc machines available. Like Hackage, it should be easy to add a new program. Is submitting a patch against the darcs repo sufficiently easy? Should we move the master darcs repo to somewhere more accessible, like code.haskell.org? It'd be good to measure run-time, Done... but allocation count, peak memory use, code size, compilation time are also good (and rather more stable) numbers to capture. Nobench does already collect code size, but does not yet display it in the results table. I specifically want to collect compile time as well. Not sure what the best way to measure allocation and peak memory use are? Yeah, this is hard. There are various non-portable perl scripts for this kind of thing, or +RTS -sstderr -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell performance
simonmarhaskell: Malcolm Wallace wrote: Simon Peyton-Jones [EMAIL PROTECTED] wrote: What would be v helpful would be a regression suite aimed at performance, that benchmarked GHC (and perhaps other Haskell compilers) against a set of programs, regularly, and published the results on a web page, highlighting regressions. Something along these lines already exists - the nobench suite. darcs get http://www.cse.unsw.edu.au/~dons/code/nobench It originally compared ghc, ghci, hugs, nhc98, hbc, and jhc. (Currently the results at http://www.cse.unsw.edu.au/~dons/nobench.html compare only variations of ghc fusion rules.) I have just been setting up my own local copy - initial results at http://www.cs.york.ac.uk/fp/nobench/powerpc/results.html where I intend to compare ghc from each of the 6.4, 6.6 and 6.8 branches, against nhc98 and any other compilers I can get working. I have powerpc, intel, and possibly sparc machines available. That's great. BTW, GHC has a performance bug affecting calendar at the moment: http://hackage.haskell.org/trac/ghc/ticket/1168 The best GHC options for this program might therefore be -O2 -fno-state-hack. Or perhaps just -O0. Like Hackage, it should be easy to add a new program. Is submitting a patch against the darcs repo sufficiently easy? Should we move the master darcs repo to somewhere more accessible, like code.haskell.org? Yes, please do. When I have a chance I'd like to help out. Malcolm, can you just take the darcs repo, and move it to code.haskell.org? -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell performance
On Thursday 20 December 2007 19:02, Don Stewart wrote: Ok, so I should revive nobench then, I suspect. http://www.cse.unsw.edu.au/~dons/nobench/x86_64/results.html that kind of thing? Many of those benchmarks look good. However, I suggest avoiding trivially reducible problems like computing constants (e, pi, primes, fib) and redundant operations (binary trees). Make sure programs accept a non-trivial input (even if it is just an int over a wide range). Avoid unnecessary repeats (e.g. atom.hs). This will mean that transformations that improve performance on the benchmark suite will be more likely to improve the performance of real programs. I would recommend adding: 1. FFT. 2. Graph traversal, e.g. nth-nearest neighbor. These should be 100LOC each. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/products/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell performance
jon: On Thursday 20 December 2007 19:02, Don Stewart wrote: Ok, so I should revive nobench then, I suspect. http://www.cse.unsw.edu.au/~dons/nobench/x86_64/results.html that kind of thing? Many of those benchmarks look good. However, I suggest avoiding trivially reducible problems like computing constants (e, pi, primes, fib) and redundant operations (binary trees). Make sure programs accept a non-trivial input (even if it is just an int over a wide range). Avoid unnecessary repeats (e.g. atom.hs). This will mean that transformations that improve performance on the benchmark suite will be more likely to improve the performance of real programs. This is a long recognised issue. The benchmark suite is a variant of the nofib suite, described here: http://citeseer.ist.psu.edu/partain93nofib.html which breaks the programs up into imaginary, spectral and real categories of programs. I would recommend adding: 1. FFT. 2. Graph traversal, e.g. nth-nearest neighbor. These should be 100LOC each. Sounds good. Patches can be sent via darcs. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: Haskell performance
However, I suggest avoiding trivially reducible problems like computing constants (e, pi, primes, fib) and redundant operations (binary trees). Make sure programs accept a non-trivial input (even if it is just an int over a wide range). Avoid unnecessary repeats (e.g. atom.hs). This will mean that transformations that improve performance on the benchmark suite will be more likely to improve the performance of real programs. May I suggest using pureMD5 as one of the benchmarks? It makes sense in my mind that a tool with a real use and consistent run times be used. Not sure if I would consider the rolled (concise) or unrolled (ugly) version a better fit (or both). The rolled version showed excellent speed increase due to pointer tagging (17sec down from 27sec for hashing 200MB). On the other hand, the unrolled version is the obvious 'make as ugly a Haskell program as you can to complete with C'. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] instance Monad Either?
According to this http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors Either is an instance of class Monad, but when I try to use the do notation I get a compiler error. What's going on? E. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] instance Monad Either?
On 12/20/07, Eric [EMAIL PROTECTED] wrote: According to this http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors Either is an instance of class Monad, but when I try to use the do notation I get a compiler error. What's going on? Near the bottom of that page is a comment by Luis Cabellos. Does that comment bring you any closer to enlightenment? Cheers! --Tom Phoenix ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] instance Monad Either?
Tom Phoenix wrote: On 12/20/07, Eric [EMAIL PROTECTED] wrote: According to this http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors Either is an instance of class Monad, but when I try to use the do notation I get a compiler error. What's going on? Near the bottom of that page is a comment by Luis Cabellos. Does that comment bring you any closer to enlightenment? It works now. Thanks! E. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Is there some place where I can find the hs-curses doc ?
It seems I can't find it. David. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there some place where I can find the hs-curses doc ?
dav.vire+haskell: It seems I can't find it. hscurses, Stefan Wehr's package of the curses binding is pre-hackage and pre-cabal, so you can only get the source: http://www.informatik.uni-freiburg.de/~wehr/haskell/ there's another curses binding in hmp3, http://www.cse.unsw.edu.au/~dons/code/hmp3/Curses.hsc that i keep meaning to package up, but never do. both these modules use the curses man pages as the main source of documentation. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] instance Monad Either?
Eric wrote: According to this http://www.randomhacks.net/articles/2007/03/10/haskell-8-ways-to-report-errors Either is an instance of class Monad, but when I try to use the do notation I get a compiler error. What's going on? Try to import Control.Monad.Error to get a Monad instance for Either. Actually, the instance is for (Error a = Either a), So it's more like the 5. aproach on that page. But since there is an instance Error String you can use (Either String) as a Monad (or a MonadError): import Control.Monad.Error test1 :: Either String Int test1 = do [x, y, z] - return [3] return 42 test2 :: MonadError e m = m Int test2 = do [x, y, z] - return [3] return 42 *Main test Left Pattern match failure in do expression at test.hs:5:2-10 *Main test2 :: Either String Int Left Pattern match failure in do expression at test.hs:11:2-10 *Main test2 :: IO Int *** Exception: user error (Pattern match failure in do expression at test.hs:11:2-10) Tillmann ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Is there some place where I can find the hs-curses doc ?
On Dec 20, 2007 11:24 PM, Don Stewart [EMAIL PROTECTED] wrote: there's another curses binding in hmp3, http://www.cse.unsw.edu.au/~dons/code/hmp3/Curses.hsc that i keep meaning to package up, but never do. Thanks ! There's quite a lot of stuff I don't understand in Curses.hsc ( the use of # chars for example in #const or (P.packAddress initscr##) or (#type bool) ) I hope the FFI libs have the answers in the doc. David. P.S. Sorry for not prefixing the title with [Haskell-cafe] -- I'll try to remember it next time. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
Albert Y. C. Lai trebla at vex.net writes: Theoretically the recursions in oddFactors k n | otherwise = oddFactors (k+2) n and (*) divisions y |divisor y = bound y = divisions (divstep y) do not cost stack space. They are tail recursions too! In general similar tail recursions do not cost stack space. Some programs using them use a lot of stack space, but that is because of non-strictness, not because of tail recursion itself. And such non-strictness is absent here due to the way the parameters have to be evaluated for all sorts of decisions before further recursive calls. Thanks for all that benchwork (and especially your exponent 61). I must admit, that i ran the (*) version in ghci only (not having compiled it to a standalone version). Maybe ghci is configured wrongly on my system. As i remember, i tried (*) twice, coming near to memory exhaustion and not awaiting the result. I would really like a non-monadic version. What is interesting also is how near your 19 minutes came to my 17 (Windows XP, 2.2GHZ, 512MB). And the comparations to Daniels code seem to imply, that my named fields in DivIter are not very expensive, if at all. Is there documentation of tail recursion anywhere ? I searched (googling with site:www.haskell.org) and didn't find anything else than entries in mailing lists. Cheers, Joost ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: MonadFix
apfelmus apfelmus at quantentunnel.de writes: How about separating the candidate prime numbers from the recursion factorize :: Integer - [Integer] factorize = f primes' where primes' = 2:[3,5..] f (p:ps) n | r == 0= p : f (p:ps) q | p*p n = [n] | otherwise = f ps n where (q,r) = n `divMod` p Providing effectively primes' for that is simply impossible (besides: p intsqrt n must stay, otherwise you have the expensive p*p at every step) talking about really big numbers as i did in my post. There are no fast generators iterating just through the primes firstly, and these lists get much too big also (for 2^120 you cannot even begin to use a list of the primes up to 2^(any appropriate x) ). What can be done is to iterate through odd numbers meeting as many primes as possible. We could do this: iterdivisors x | x == 0 = 3 | x == 1 = 5 | otherwise x = iterdivisors (x-1) + ((cycle [2,4]) !! x) This gives 7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,63,67 ... i.e. exactly all primes and odds with greater primefactors as 3. We can improve that cycle avoiding the multiples of 5: ... | otherwise x = iterdivisors (x-1) + ((cycle [2,4,2,4,2,4,6,2,6] !! x) and we can do better by avoiding the multiples of 7 and so on (the length of these lists grows fast - it gets multiplied by every new avoided prime -, but we could provide that lists programmatically). And we must be sure, that cycle doesn't eat up memory for each new pass through the list. And we should use a more efficient representaion for the list of summands than a list. This is the first front. But the title of my post and much more interesting topic for learning Haskell is, how to avoid memory exhaustion by recursion. THIS was my intention and the reason why i erroneously brought MonadFix into the game. The recursion i described as follows divisions = do y - get if divisor y = bound y then do put ( divstep y ) divisions else return y makes a DESTRUCTIVE UPDATE of the DivIters (by put) and this kind of recursion seems not to remember itself (as i have understood, that is achieved by tail recursion). I just didn't like making DivIters to States. It's kind of lying code. However it worked and improved performance by a factor around 10 (or oo - perhaps a normal recursion exhausts 512MB memory for 2^120+1, as it will do for much smaller Integers, if they are prime) not to talk about footprint. Compiled for running standalone, it took 17 minutes, an equivalent python script 2 hours. This factor near 7 is not fully satisfactory. There are more workarounds beside the State monad for having destructive updates with Haskell. There are IORefs, there are updatable arrays and more. THAT is my question: Is this (only basically) the most efficient way to get them here ? Or is there still a way of getting a tail recursive Haskell function for iterating through the DivIters (outside any monads) ?? I would not get stroke dead by surprise if yes, but i couldn't find any. Cheers, Joost ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: MonadFix
On 12/20/07, Joost Behrends [EMAIL PROTECTED] wrote:
makes a DESTRUCTIVE UPDATE of the DivIters (by put) and this kind of
recursion
seems not to remember itself (as i have understood, that is achieved by
tail recursion). I just didn't like making DivIters to States.
It's kind of lying code.
I just want to point out that this isn't true; put in the State monad
doesn't do any destructive update at all (unlike, for example, IORef).
You can tell this for yourself by looking at the type of State s a in
Control.Monad.State:
http://haskell.org/ghc/docs/latest/html/libraries/mtl/src/Control-Monad-State-Lazy.html
newtype State s a = State { runState :: s - (a,s) }
That is, your divisions function of type
divisions :: State DivIter DivIter
is equivalent to the type
runState divisions :: DivIter - (DivIter, DivIter)
and the code is the same as if you'd just passed the DivIter directly along.
-- ryan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] upgrading regex in GHC 6.8.2
Hello, I have an application that uses/used Text.Regex and have just updated GHC from 6.6.1 to 6.8.2 and it seems that Text.Regex is gone, so I'm trying to install the replacement from Hackage. First of all, the procedure is quite tedious as one has to install the hierarchy of dependencies manually but apparently there are moves to automate this process. The procedure stalled on regex-base-0.92. I fixed the build-depends in regex-base.cabal to: Build-Depends:base = 2.0, mtl, containers = 0.1.0.1, bytestring, array following information I found via an internet search but on runghc Setup.hs install it says: Setup.hs: Error: Could not find module: Text.Regex.Base with any suffix: [hi] It seems that it is necessary to remove the Text.Regex.Base and Text.Regex.Base.Impl entries from the Exposed-Modules: line but then regex-posix build complains that it can't find Text.Regex.Base. I tried various hackery like compiling Text/Regex/Base.hs manually but even when Text/Regex/Base.hi exists, the runghc Setup.hs install error message above still occurs. What is happening ? -- _ Michael Mounteney,+618 4311 11547 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Optimizing cellular automata the beauty of unlifted types
I'm curious how much of the unboxing helped performance and how much didn't. In my experience playing with this stuff, GHC's strictness analyzer has consistently been really excellent, given the right hints. Unboxed tuples are generally a win, but GHC was often smarter at unboxing ints than I was. Also, higher-order functions can be used fine, assuming they're not awful recursive, as long as you set GHC's unfolding threshold high enough. You can also manually force their inlining, to really get control. I found there tended to be a sweet spot for any given program, where much higher or lower would degrade performance. As far as removing the word2int# and soforth, you could probably just use words throughout? Also, as we discovered the other week, you may want to be careful with bang patterns, as forcing strictness on already evaluated values takes some time. Although, SPJ did point out that this was significantly improved in the new GHC. But yes, I found that going through and manually unboxing a working implementation with the help of type errors was actually a sort of relaxing and zenlike exercise. --S On Dec 20, 2007, at 6:07 PM, Justin Bailey wrote: I'm back with another version of my cellular automata simulator. Since the last iteration I discovered GHC's unlifted types and the primitive operations that go with them. Using these types, rather than Ints, sped my code up by 2x or more. http://hpaste.org/4151#a2 -- first half of program http://hpaste.org/4151#a3 -- remaining (note 3 lines or so from first half are repeated) The key observation came from looking at the Core files, which showed a lot of int2word# and word2int# conversions going on. Figuring out how to remove those led me to the unlifted types. Coding with these types is not easy (for example, I couldn't see a way to write a Word# value directly - I had to write stuff like int2Word# 1#), but because I had an existing algorithm to guide me, combined with type checking, it was a fairly straightforward implementation. At first I felt kind of bad about using these operations, but then I noticed they are used pretty heavily by GHC itself. If it's good enough for GHC, it's good enough for me. The 2x performance gain didn't hurt either. Finally, the safety that comes from using the ST monad is just awesome. I've got low-level bit munging combined with high-level abstraction where I need it. So cool! I was disappointed to find early on that using higher-order functions in tight loops was a performance killer. It's unfortunate because I started with a very elegant, short implementation based on a simple Ring buffer and map. The current version is certainly harder to understand and has some weird limitations. However, having the simple implementation let me use quickcheck to compare their results on random rules and inputs, which gave me high confidence that my complex implemenation is correct. One thing I absolutely love about this program is its memory performance. It manages to stay within 1 - 10 MB of memory, depending on how much output is produced. How cool is that? On Dec 3, 2007 2:44 AM, Mirko Rahn [EMAIL PROTECTED] wrote: It is interesting, that the naive implementation ... is only 3 times slower than your quite complex, hard to follow and hard to debug implementation. Now the naive implementation is 100x slower, so I don't feel so bad about this comment any more. As always, I prefer to write most code in Haskell, quick, easy, nice, reasonable fast, ... If speed matters, I switch to some lower level language, as you did staying inside Haskell. I have to take exception here - I *want* to write my code in Haskell. If Haskell isn't fast enough to beat the C implementation, I'd rather find a way to make my Haskell program faster than switch to some other language. Justin ___ 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] upgrading regex in GHC 6.8.2
On Fri, 2007-12-21 at 13:58 +1030, Michael Mounteney wrote: Hello, I have an application that uses/used Text.Regex and have just updated GHC from 6.6.1 to 6.8.2 and it seems that Text.Regex is gone, so I'm trying to install the replacement from Hackage. First of all, the procedure is quite tedious as one has to install the hierarchy of dependencies manually but apparently there are moves to automate this process. Yes. You can try cabal-install now if you like: http://haskell.org/cabal/code.html though be prepared to report bugs and limitations: http://hackage.haskell.org/trac/hackage That said, I use it all the time now. It's much quicker than manually downloading and configuring everything. The procedure stalled on regex-base-0.92. None of the 0.9x versions have been updated for the base-3 library that comes with ghc-6.8 now. Instead try using: regex-base-0.72.0.1 regex-posix-0.72.0.2 regex-compat-0.71.0.1 These versions work with ghc-6.8 and earlier. These would be the latest versions if it were not for the 0.9x series. We need some way to tell hackage or cabal-install that the latest version is not necessarily the best or recommended version. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Smart Constructor Puzzle
I'm playing around with smart constructors, and I have encountered a weird puzzle. My goal is to do vector arithmetic. I'm using smart constructors so that I can store a vector as a list and use the type system to staticly enforce the length of a vector. So my first step is to define Peano numbers at the type level. data PZero = PZero deriving (Show) data PSucc a = PSucc a deriving (Show) type P1 = PSucc PZero type P2 = PSucc P1 type P3 = PSucc P2 -- etc Next, I define a vector type and tag it with a Peano number. data Vec s t = Vec [t] deriving (Eq, Ord, Show, Read) Now I can define a few smart constructors. vec0 :: Vec PZero t vec0 = Vec [] vec1 :: t - Vec P1 t vec1 x = Vec [x] vec2 :: t - t - Vec P2 t vec2 x y = Vec [x, y] vec3 :: t - t - t - Vec P3 t vec3 x y z = Vec [x, y, z] Now here's the puzzle. I want to create a function vecLength that accepts a vector and returns its length. The catch is that I want to calculate the length based on the /type/ of the vector, without looking at the number of elements in the list. So I started by defining a class that allows me to convert a Peano number to an integer. I couldn't figure out how to define a function that converts the type directly to an integer, so I am using a two-step process. Given a Peano type /t/, I would use the expression pToInt (pGetValue :: t). class Peano t where pGetValue :: t pToInt :: t - Int instance Peano PZero where pGetValue = PZero pToInt _ = 0 instance (Peano t) = Peano (PSucc t) where pGetValue = PSucc pGetValue pToInt (PSucc a) = 1 + pToInt a Finally, I tried to define vecLength, but I am getting an error. vecLength :: (Peano s) = Vec s t - Int vecLength _ = pToInt (pGetValue :: s) Could not deduce (Peano s1) from the context () arising from a use of `pGetValue' Possible fix: add (Peano s1) to the context of the polymorphic type `forall s. s' In the first argument of `pToInt', namely `(pGetValue :: s)' In the expression: pToInt (pGetValue :: s) In the definition of `vecLength': vecLength _ = pToInt (pGetValue :: s) Any suggestions? -- Ron ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Smart Constructor Puzzle
On Dec 21, 2007 4:39 AM, Ronald Guida [EMAIL PROTECTED] wrote: Finally, I tried to define vecLength, but I am getting an error. vecLength :: (Peano s) = Vec s t - Int vecLength _ = pToInt (pGetValue :: s) The s in (pGetValue :: s) is different from the s in (Peano s). Use the scoped type variables extension: vecLength :: forall s. (Peano s) = Vec s t - Int vecLength _ = pToInt (pGetValue :: s) The forall introduces a scope for s, which type signatures usually do not. Luke Could not deduce (Peano s1) from the context () arising from a use of `pGetValue' Possible fix: add (Peano s1) to the context of the polymorphic type `forall s. s' In the first argument of `pToInt', namely `(pGetValue :: s)' In the expression: pToInt (pGetValue :: s) In the definition of `vecLength': vecLength _ = pToInt (pGetValue :: s) Any suggestions? -- Ron ___ 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] Smart Constructor Puzzle
Ronald Guida wrote:
I'm playing around with smart constructors, and I have encountered a
weird puzzle.
My goal is to do vector arithmetic. I'm using smart constructors so
that I can store a vector as a list and use the type system to
staticly enforce the length of a vector.
So my first step is to define Peano numbers at the type level.
data PZero = PZero deriving (Show)
data PSucc a = PSucc a deriving (Show)
type P1 = PSucc PZero
type P2 = PSucc P1
type P3 = PSucc P2
-- etc
Next, I define a vector type and tag it with a Peano number.
data Vec s t = Vec [t] deriving (Eq, Ord, Show, Read)
Now I can define a few smart constructors.
vec0 :: Vec PZero t
vec0 = Vec []
vec1 :: t - Vec P1 t
vec1 x = Vec [x]
vec2 :: t - t - Vec P2 t
vec2 x y = Vec [x, y]
vec3 :: t - t - t - Vec P3 t
vec3 x y z = Vec [x, y, z]
Now here's the puzzle. I want to create a function vecLength that
accepts a vector and returns its length. The catch is that I want to
calculate the length based on the /type/ of the vector, without
looking at the number of elements in the list.
So I started by defining a class that allows me to convert a Peano
number to an integer. I couldn't figure out how to define a function
that converts the type directly to an integer, so I am using a
two-step process. Given a Peano type /t/, I would use the expression
pToInt (pGetValue :: t).
class Peano t where
pGetValue :: t
pToInt :: t - Int
instance Peano PZero where
pGetValue = PZero
pToInt _ = 0
instance (Peano t) = Peano (PSucc t) where
pGetValue = PSucc pGetValue
pToInt (PSucc a) = 1 + pToInt a
Finally, I tried to define vecLength, but I am getting an error.
vecLength :: (Peano s) = Vec s t - Int
vecLength _ = pToInt (pGetValue :: s)
Could not deduce (Peano s1) from the context ()
arising from a use of `pGetValue'
Possible fix:
add (Peano s1) to the context of the polymorphic type `forall s. s'
In the first argument of `pToInt', namely `(pGetValue :: s)'
In the expression: pToInt (pGetValue :: s)
In the definition of `vecLength':
vecLength _ = pToInt (pGetValue :: s)
Any suggestions?
The type 's' is not available outside the type signature. There is an
extension, ScopedTypeVariables that does just this, allowing you to write:
{-# LANGUAGE ScopedTypeVariables #-}
vecLength :: forall s. (Peano s) = Vec s t - Int
vecLength _ = pToInt (pGetValue :: s)
An alternative is to use a 'fake' function to force a value to be of type s
vecLength :: (Peano s) = Vec s t - Int
vecLength v = pToInt (phantomType v)
phantomType :: Vec s t - s
phantomType = undefined
Also, undefined and type signatures are the key to writing short classes in
these situations:
class ToInt a where
toInt :: a - Int
instance ToInt PZero where
toInt _ = 0
instance ToInt a = ToInt (PSucc a) where
toInt _ = toInt (undefined :: a) + 1
Twan
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Smart Constructor Puzzle
On Thu, Dec 20, 2007 at 11:39:42PM -0500, Ronald Guida wrote: data PZero = PZero deriving (Show) data PSucc a = PSucc a deriving (Show) type P1 = PSucc PZero type P2 = PSucc P1 type P3 = PSucc P2 -- etc ... Now here's the puzzle. I want to create a function vecLength that accepts a vector and returns its length. The catch is that I want to calculate the length based on the /type/ of the vector, without looking at the number of elements in the list. So I started by defining a class that allows me to convert a Peano number to an integer. I couldn't figure out how to define a function that converts the type directly to an integer, so I am using a two-step process. Given a Peano type /t/, I would use the expression pToInt (pGetValue :: t). class Peano t where pGetValue :: t pToInt :: t - Int instance Peano PZero where pGetValue = PZero pToInt _ = 0 instance (Peano t) = Peano (PSucc t) where pGetValue = PSucc pGetValue pToInt (PSucc a) = 1 + pToInt a Finally, I tried to define vecLength, but I am getting an error. vecLength :: (Peano s) = Vec s t - Int vecLength _ = pToInt (pGetValue :: s) 1. pGetValue is unneccessary, undefined :: s will work just as well. This is a fairly standard approach; the precision values in Floating, bitSize :: Bits a = a - Int, and sizeOf :: Storable a = a - Int all work this way. Some Haskeller, notably Alex Jacobson, prefer to use a 'proxy' type to make this value irrelevance explicit: data Proxy s -- for H98, data Proxy s = Proxy_ !(Proxy s) 2. The reason this doesn't work is that the scope of s in the type signature is the type signature, and the scope of s in the other type signature is the other type signature. They are very different type variables, and you cannot assign the type forall s. s to pGetValue - it has class constraints. The effect you are trying to achieve cannot be directly achieved in H98 (this is considered one of H98's few major flaws)... 2a: Use GHC extentions (ScopedTypeVariables). This extends the scope of type variables to include the definition. For backwards compatibility, it only applies to new-style explicit quantification: vecLength :: forall s. Peano s = Vec s t - Int 2b: Use functions with type constraints to force relations between types: vecLength v = pToInt (vToPeano v) where vToPeano = undefined :: Vec s t - s Figuring out why this works should be enlightening, and it seems hard to explain, so I'm leaving it as an excersize. :) Stefan signature.asc Description: Digital signature ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] upgrading regex in GHC 6.8.2
Searchpath already does recursive module chasing accross the internet. If your module is available at a url in an unpacked module hierarchy or in a tgz file or if it is exposed in a darcs/svn/cvs etc repo, searchpath can retrieve it and put it on your local import path. The main limitations on using searchpath are that the packages you need may not yet have been added to the searchpath directory and it does not currently run cabal so if the module you import need some interesting build process you will need to handle them manually. The directory issue could be solved if someone were to write a small patch to hackage so that it exposes the database in the correct format. The cabal issue I think requires only a small modification to the searchpath code but I don't know cabal well enough to do it -Alex- Duncan Coutts wrote: On Fri, 2007-12-21 at 13:58 +1030, Michael Mounteney wrote: Hello, I have an application that uses/used Text.Regex and have just updated GHC from 6.6.1 to 6.8.2 and it seems that Text.Regex is gone, so I'm trying to install the replacement from Hackage. First of all, the procedure is quite tedious as one has to install the hierarchy of dependencies manually but apparently there are moves to automate this process. Yes. You can try cabal-install now if you like: http://haskell.org/cabal/code.html though be prepared to report bugs and limitations: http://hackage.haskell.org/trac/hackage That said, I use it all the time now. It's much quicker than manually downloading and configuring everything. The procedure stalled on regex-base-0.92. None of the 0.9x versions have been updated for the base-3 library that comes with ghc-6.8 now. Instead try using: regex-base-0.72.0.1 regex-posix-0.72.0.2 regex-compat-0.71.0.1 These versions work with ghc-6.8 and earlier. These would be the latest versions if it were not for the 0.9x series. We need some way to tell hackage or cabal-install that the latest version is not necessarily the best or recommended version. Duncan ___ 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
