Re: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
dons: wren: Neil Mitchell wrote: 2) The storage for String seems to be raw strings, which is nice. Would I get a substantial speedup by moving to bytestrings instead of strings? If I hashed the strings and stored common ones in a hash table is it likely to be a big win? Bytestrings should help. The big wins in this application are likely to be cache issues, though the improved memory/GC overhead is nice too. Here's a quick demo using Data.Binary directly. Now, let's read back in and decode it back to a Map main = do [f] - getArgs m - decodeFile f print (M.size (m :: M.Map B.ByteString Int)) print done Easy enough: $ time ./A dict +RTS -K20M 52848 done ./A dict +RTS -K20M 1.51s user 0.06s system 99% cpu 1.582 total Compressed dictionary is much smaller. Let's load it back in and unpickle it: main = do [f] - getArgs m - (decode . decompress) `fmap` L.readFile f print (M.size (m :: M.Map B.ByteString Int)) print done Also cute. But how does it run: $ time ./A dict.gz 52848 done ./A dict.gz 0.28s user 0.03s system 98% cpu 0.310 total Interesting. So extracting the Map from a compressed bytestring in memory is a fair bit faster than loading it directly, uncompressed from disk. Note the difference, as Duncan and Bulat pointed out, is a bit surprising. Perhaps the Map instance is a bit weird? We already know that bytestring IO is fine. Just serialising straight lists of pairs, import Data.Binary import Data.List import qualified Data.ByteString.Char8 as B import qualified Data.ByteString.Lazy as L import System.Environment import qualified Data.Map as M import Codec.Compression.GZip main = do [f] - getArgs s - B.readFile f let m = [ (head n, length n) | n - (group . B.lines $ s) ] L.writeFile dict.gz . encode $ m print done $ time ./binary /usr/share/dict/cracklib-small done ./binary /usr/share/dict/cracklib-small 0.13s user 0.04s system 99% cpu 0.173 total $ du -hs dict 1.3Mdict And reading them back in, main = do [f] - getArgs m - decode `fmap` L.readFile f print (length (m :: [(B.ByteString,Int)])) print done $ time ./binary dict 52848 done ./binary dict 0.04s user 0.01s system 99% cpu 0.047 total Is fast. So there's some complication in the Map serialisation. Adding in zlib, to check, main = do [f] - getArgs s - B.readFile f let m = [ (head n, length n) | n - (group . B.lines $ s) ] L.writeFile dict.gz . compress . encode $ m print done $ time ./binary /usr/share/dict/cracklib-small done ./binary /usr/share/dict/cracklib-small 0.25s user 0.03s system 100% cpu 0.277 total Compression takes longer, as expected, and reading it back in, main = do [f] - getArgs m - (decode . decompress) `fmap` L.readFile f print (length (m :: [(B.ByteString,Int)])) print done $ time ./binary dict.gz 52848 done ./binary dict.gz 0.03s user 0.01s system 98% cpu 0.040 total About the same. Looks like the Map reading/showing via association lists could do with further work. Anyone want to dig around in the Map instance? (There's also some patches for an alternative lazy Map serialisation, if people are keen to load maps -- happstack devs?). -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
On Tue, Feb 24, 2009 at 4:59 AM, Don Stewart d...@galois.com wrote: Looks like the Map reading/showing via association lists could do with further work. Anyone want to dig around in the Map instance? (There's also some patches for an alternative lazy Map serialisation, if people are keen to load maps -- happstack devs?). From binary-0.5: instance (Ord k, Binary k, Binary e) = Binary (Map.Map k e) where put m = put (Map.size m) mapM_ put (Map.toAscList m) get = liftM Map.fromDistinctAscList get instance Binary a = Binary [a] where put l = put (length l) mapM_ put l get= do n - get :: Get Int replicateM n get Can't get better, I think. Now, from containers-0.2.0.0: fromDistinctAscList :: [(k,a)] - Map k a fromDistinctAscList xs = build const (length xs) xs where -- 1) use continutations so that we use heap space instead of stack space. -- 2) special case for n==5 to build bushier trees. build c 0 xs' = c Tip xs' build c 5 xs' = case xs' of ((k1,x1):(k2,x2):(k3,x3):(k4,x4):(k5,x5):xx) - c (bin k4 x4 (bin k2 x2 (singleton k1 x1) (singleton k3 x3)) (singleton k5 x5)) xx _ - error fromDistinctAscList build build c n xs' = seq nr $ build (buildR nr c) nl xs' where nl = n `div` 2 nr = n - nl - 1 buildR n c l ((k,x):ys) = build (buildB l k x c) n ys buildR _ _ _ [] = error fromDistinctAscList buildR [] buildB l k x c r zs = c (bin k x l r) zs The builds seem fine, but we spot a (length xs) on the beginning. Maybe this is the culprit? We already know the size of the map (it was serialized), so it is just a matter of exporting fromDistinctAscSizedList :: Int - [(k, a)] - Map k a Too bad 'Map' is exported as an abstract data type and it's not straighforward to test this conjecture. Any ideas? -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: package for algebraic structures
On 2009-02-19, Wolfgang Jeltsch g9ks1...@acme.softbase.org wrote: In addition, I wouldn’t include algebraic structures in a *numerical* prelude since the cool thing about them is that they are so abstract that they are not only about numbers. But the thing is that to have the numerical classes support the proper abstractions we want them to support, we need to define the algebraic structures as well. So the rework goes together... -- Aaron Denney -- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Looping after compiling with cabal
Try rm-ing *.o, *.hi. Simon | -Original Message- | From: Henk-Jan van Tuyl [mailto:hjgt...@chello.nl] | Sent: 23 February 2009 20:46 | To: Simon Peyton-Jones; Haskell cafe | Subject: Re: [Haskell-cafe] Looping after compiling with cabal | | | I tried to compile with head, but I got the following error messages: | | [...]\Haskell\GUI\wxHaskell\wxFruit\wxFruit-0.1.2.testrunhaskell Setup | configurerunhaskell Setup buildrunhaskell Setup install | Configuring wxFruit-0.1.2... | Preprocessing library wxFruit-0.1.2... | Preprocessing executables for wxFruit-0.1.2... | Building wxFruit-0.1.2... | [1 of 1] Compiling WXFruit ( WXFruit.hs, dist\build\WXFruit.o ) | | WXFruit.hs:14:0: | Bad interface file: | [...]\Haskell\GUI\wxHaskell\wxhaskell-0.11.0\lib\imports\Graphics\UI\WX.hi | mismatched interface file versions (wanted 610120090216, got | 6101) | Setup: C:\Program Files\Haskell\doc\wxFruit-0.1.2\.copyFile6036.tmp: | copyFile: permission denied (Toegang geweigerd.) | | What should I do differently? | | The problem must be |http://hackage.haskell.org/trac/ghc/ticket/2722 | , I solved the loop by defining |id = arr Prelude.id | instead of: |id = arr id | | Regards, | Henk-Jan van Tuyl | | | -- | http://functor.bamikanarie.com | http://Van.Tuyl.eu/ | -- | | | | On Mon, 23 Feb 2009 14:54:01 +0100, Simon Peyton-Jones | simo...@microsoft.com wrote: | | I suspect this may be an instance of | http://hackage.haskell.org/trac/ghc/ticket/2985 | | Or (less likely) | http://hackage.haskell.org/trac/ghc/ticket/2722 | | Can you try with the HEAD? Or the 6.10 branch (which includes the fix | for #2985)? | | Simon | | | -Original Message- | | From: haskell-cafe-boun...@haskell.org | [mailto:haskell-cafe-boun...@haskell.org] On | | Behalf Of Henk-Jan van Tuyl | | Sent: 16 February 2009 12:04 | | To: Haskell cafe | | Subject: [Haskell-cafe] Looping after compiling with cabal | | | | | | L.S., | | | | I have updated wxFruit to compile with GHC 6.10.1, but when I compil | using | | the commands: | |runhaskell Setup configurerunhaskell Setup buildrunhaskell | | Setup install | | and run paddle.exe, I get the message: | |paddle: loop | | | | If I compile with: | |ghc --make paddle | | , the game starts normally. | | | | Any idea how I can solve this? | | | | Some more data: | | Using: | |Yampa-0.9.2.3 | |wxFruit-0.1.1 from Hackage, updated | |GHC 6.10.1 | |Windows XP | | | | Compile sessions: | | | | [...]\Haskell\GUI\wxHaskell\wxFruit-0.1.1.updatedghc --make paddle | | [1 of 2] Compiling WXFruit ( WXFruit.hs, WXFruit.o ) | | [2 of 2] Compiling Main ( paddle.hs, paddle.o ) | | Linking paddle.exe ... | | | | This paddle.exe works fine | | | | | | [...]\Haskell\GUI\wxHaskell\wxFruit-0.1.1.updatedrunhaskell Setup | | configurerunhaskell Setup buildrunhaskell Setup install | | Configuring wxFruit-0.1.2... | | Preprocessing library wxFruit-0.1.2... | | Preprocessing executables for wxFruit-0.1.2... | | Building wxFruit-0.1.2... | | [1 of 1] Compiling WXFruit ( WXFruit.hs, dist\build\WXFruit.o | ) | | C:\Programs\ghc\ghc-6.10.1\bin\ar.exe: creating | | dist\build\libHSwxFruit-0.1.2.a | | [1 of 2] Compiling WXFruit ( WXFruit.hs, | | dist\build\paddle\paddle-tmp\WXFruit.o ) | | Linking dist\build\paddle\paddle.exe ... | | Installing library in C:\Program Files\Haskell\wxFruit-0.1.2\ghc-6.10.1 | | Installing executable(s) in C:\Program Files\Haskell\bin | | Registering wxFruit-0.1.2... | | Reading package info from dist\\installed-pkg-config ... done. | | Writing new package config file... done. | | | | [...]\Haskell\GUI\wxHaskell\wxFruit-0.1.1.updatedcd dist\build\paddle | | | | | [...]\Haskell\GUI\wxHaskell\wxFruit-0.1.1.updated\dist\build\paddlepaddle | | paddle: loop | | | | -- | | Regards, | | Henk-Jan van Tuyl | | | -- | ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
felipe.lessa: On Tue, Feb 24, 2009 at 4:59 AM, Don Stewart d...@galois.com wrote: Looks like the Map reading/showing via association lists could do with further work. Anyone want to dig around in the Map instance? (There's also some patches for an alternative lazy Map serialisation, if people are keen to load maps -- happstack devs?). From binary-0.5: instance (Ord k, Binary k, Binary e) = Binary (Map.Map k e) where put m = put (Map.size m) mapM_ put (Map.toAscList m) get = liftM Map.fromDistinctAscList get instance Binary a = Binary [a] where put l = put (length l) mapM_ put l get= do n - get :: Get Int replicateM n get Can't get better, I think. Now, from containers-0.2.0.0: fromDistinctAscList :: [(k,a)] - Map k a fromDistinctAscList xs = build const (length xs) xs where -- 1) use continutations so that we use heap space instead of stack space. -- 2) special case for n==5 to build bushier trees. build c 0 xs' = c Tip xs' build c 5 xs' = case xs' of ((k1,x1):(k2,x2):(k3,x3):(k4,x4):(k5,x5):xx) - c (bin k4 x4 (bin k2 x2 (singleton k1 x1) (singleton k3 x3)) (singleton k5 x5)) xx _ - error fromDistinctAscList build build c n xs' = seq nr $ build (buildR nr c) nl xs' where nl = n `div` 2 nr = n - nl - 1 buildR n c l ((k,x):ys) = build (buildB l k x c) n ys buildR _ _ _ [] = error fromDistinctAscList buildR [] buildB l k x c r zs = c (bin k x l r) zs The builds seem fine, but we spot a (length xs) on the beginning. Maybe this is the culprit? We already know the size of the map (it was serialized), so it is just a matter of exporting fromDistinctAscSizedList :: Int - [(k, a)] - Map k a Too bad 'Map' is exported as an abstract data type and it's not straighforward to test this conjecture. Any ideas? This idea was the motivation for the new Seq instance, which uses internals to build quickly. Encoding to disk, the dictionary, $ time ./binary /usr/share/dict/cracklib-small done ./binary /usr/share/dict/cracklib-small 0.07s user 0.01s system 94% cpu 0.088 total Decoding, $ time ./binary dict.gz 52848 done ./binary dict.gz 0.07s user 0.01s system 97% cpu 0.079 total instance (Binary e) = Binary (Seq.Seq e) where put s = put (Seq.length s) Fold.mapM_ put s get = do n - get :: Get Int rep Seq.empty n get where rep xs 0 _ = return $! xs rep xs n g = xs `seq` n `seq` do x - g rep (xs Seq.| x) (n-1) g Just a lot better. :) So ... Data.Map, we're looking at you! -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
On Tue, Feb 24, 2009 at 5:36 AM, Don Stewart d...@galois.com wrote: This idea was the motivation for the new Seq instance, which uses internals to build quickly. The problem is that fromDistinctAscList is the best we can do right now. We don't have something like (|) that runs in O(1) time, and trying to insert each element would give O(n log n) instead of O(n). In fact, we don't even know if length is the culprit, although I'm highly suspicious of it. Maybe there should be Data.Map.Internal like Data.ByteString.Internal so we can mess with the datatypes directly but without strong API compatibility guarantees? -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Pickling a finite map (Binary + zlib) [was: Data.Binary poor read performance]
Felipe Lessa wrote: The builds seem fine, but we spot a (length xs) on the beginning. Maybe this is the culprit? We already know the size of the map (it was serialized), so it is just a matter of exporting fromDistinctAscSizedList :: Int - [(k, a)] - Map k a Excellent idea, what does stop you? fromDistinctAscList is already a function with a precondition that is not checked. Too bad 'Map' is exported as an abstract data type and it's not straighforward to test this conjecture. Any ideas? One really doesn't want to see the actual implementation (except for debugging or tuning purposes), but maybe conversions to and from a fully (and uniquely) balanced binary tree are desirable. (a basic binary tree data type is still missing on hackage). I think, equal maps should not yield different serialization results just because the internal tree structure happens to be different, but that's of course debatable. Cheers Christian Maybe the discussion should be continued on librar...@haskell.org? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
Hello Felipe, Tuesday, February 24, 2009, 11:24:19 AM, you wrote: Too bad 'Map' is exported as an abstract data type and it's not straighforward to test this conjecture. Any ideas? just make a copy of its implementation to test btw, i always thought that it should be a way to overcome any export lists and go directly to module internals. limiting export is the way to protect programmer from errors, not security feature, and it should be left to programmer to decide when he don't need it. compilers should just be able to check whether some module/library imported abstractly or with internals too. this will render useless all those .Internals modules that now we need to add everywhere -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ANN: bug fix for regex-tdfa, version 0.97.4 (and regex-ast)
Hello, The regex-tdfa package has had a series of bug fix releases (0.97.1 and 2 and 3 and now 4). This 0.97.4 releases finishes fixing the bug that was only mostly fixed in the 0.97.1 release. An example of the fixed bug: Apply the regex pattern (BB(B?))+(B?) to the text . The BB in the pattern should be used twice and both B? should match nothing. My code grouped the + wrong and matched the BB once and then both the B? matched a B. The case fixed here was not initially caught because of how I search for unknown bugs. I use Arbitrary from QuickCheck to generate random patterns and strings to search, and compare regex-tdfa to another POSIX engine. Because I am on OS X, I am limited by the the native POSIX libraries bugs: this bug in regex-tdfa was triggered only when the native POSIX was also buggy. But the source of most of my unit tests is ATT research [1], and they have a libast with a POSIX implementation. I have adapted my regex-* wrapper packages to make a regex-ast Haskell interface, but the difficulties with the ATT headers prevent me from releasing this on hackage. This regex-ast has given me access to a less buggy POSIX back-end, and randomized testing has led to catching the bug fixed here (as well as a few bug reports back to ATT). So while regex-tdfa will not win many speed contests, it is the only POSIX regular expression library I have running that passes all the unit tests. [1] http://www.research.att.com/sw/download/ http://www.research.att.com/~gsf/testregex/ http://www.research.att.com/~gsf/testregex/re-interpretation.html ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
2009/2/24 Bulat Ziganshin bulat.zigans...@gmail.com: Hello Felipe, Tuesday, February 24, 2009, 11:24:19 AM, you wrote: Too bad 'Map' is exported as an abstract data type and it's not straighforward to test this conjecture. Any ideas? just make a copy of its implementation to test btw, i always thought that it should be a way to overcome any export lists and go directly to module internals. limiting export is the way to protect programmer from errors, not security feature, and it should be left to programmer to decide when he don't need it. compilers should just be able to check whether some module/library imported abstractly or with internals too. this will render useless all those .Internals modules that now we need to add everywhere I agree in principle, but GHC also uses that knowledge to optimize the code better - if a function is exported it has to produce the most polymorphic possible code for its type, if it isn't it can specialize better... that sort of thing. So it's not for security purposes, it's for technical reasons; you can't override the export list externally because the information you'd need to use the functions simply doesn't exist. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Export restrictions :) Re[4]: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
Hello Svein, Tuesday, February 24, 2009, 3:47:44 PM, you wrote: btw, i always thought that it should be a way to overcome any export lists and go directly to module internals. limiting export is the way to protect programmer from errors, not security feature, and it should be left to programmer to decide when he don't need it. compilers should just be able to check whether some module/library imported abstractly or with internals too. this will render useless all those .Internals modules that now we need to add everywhere I agree in principle, but GHC also uses that knowledge to optimize the code better - if a function is exported it has to produce the most polymorphic possible code for its type, if it isn't it can specialize better... that sort of thing. So it's not for security purposes, it's for technical reasons; you can't override the export list externally because the information you'd need to use the functions simply doesn't exist. well, obvious answer is that ghc should optimize according to export specs AND add original function definition to the .o file -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] controlling timeout for Network.Socket.connect - how?
It's hard to belive, that nobody ever tackled/solved the subj. problem. I
still can delay a bit solving it, in hope somebody would share experience.
Regards,
Belka
Belka wrote:
Hello, communion people!
I have a problem and ask for an advice.
I'm dealing with sockets on *Linux* platform (Network.Socket). The problem
is that I can't fully control timeout for (connect :: Socket - SockAddr
- IO ()) operation.
On my system the timeout is - 3 seconds - I want to be able to change that
in run-time. Well I managed to find out how to make it LESS THAN 3 seconds
- using System.Timeout. But how to make timeout bigger (for example 9
seconds) is a mystery.
(Notice: in order to achieve 9 seconds timeout - just repeating *connect*
3 times won't be effective for long-slow-way-connections. So it's not a
solution.)
The source code of Network.Socket.connect, taken from darcs:
-
-- Connecting a socket
--
-- Make a connection to an already opened socket on a given machine
-- and port. assumes that we have already called createSocket,
-- otherwise it will fail.
--
-- This is the dual to $bindSocket$. The {\em server} process will
-- usually bind to a port number, the {\em client} will then connect
-- to the same port number. Port numbers of user applications are
-- normally agreed in advance, otherwise we must rely on some meta
-- protocol for telling the other side what port number we have been
-- allocated.
connect :: Socket -- Unconnected Socket
- SockAddr -- Socket address stuff
- IO ()
connect sock@(MkSocket s _family _stype _protocol socketStatus) addr = do
modifyMVar_ socketStatus $ \currentStatus - do
if currentStatus /= NotConnected
then
ioError (userError (connect: can't peform connect on socket in status
++
show currentStatus))
else do
withSockAddr addr $ \p_addr sz - do
let connectLoop = do
r - c_connect s p_addr (fromIntegral sz)
if r == -1
then do
rc - c_getLastError
case rc of
10093 - do -- WSANOTINITIALISED
withSocketsDo (return ())
r - c_connect s p_addr (fromIntegral sz)
if r == -1
then (c_getLastError = throwSocketError connect)
else return r
_ - throwSocketError connect rc
else return r
connectBlocked = do
#if !defined(__HUGS__)
threadWaitWrite (fromIntegral s)
#endif
err - getSocketOption sock SoError
if (err == 0)
then return 0
else do ioError (errnoToIOError connect
(Errno (fromIntegral err))
Nothing Nothing)
connectLoop
return Connected
-
I know that controlling timeout is somehow connected to select(2) (I'm
currently investigating this matter...), but it's not in the Network or
Network.Socket libs (but in the libs that they FFI with).
Hope I won't have to rewrite these low-level functions __
Could anybody, please share some experience on how to adjust timeout for
*connect*?
Thanks in advance,
Best regards,
Belka
--
View this message in context:
http://www.nabble.com/controlling-timeout-for-Network.Socket.connect---how--tp22139581p22181071.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: Re[2]: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe]Data.Binary poor read performance]
btw, i always thought that it should be a way to overcome any export lists and go directly to module internals. limiting export is the way to protect programmer from errors, not security feature, and it should be left to programmer to decide when he don't need it. compilers should just be able to check whether some module/library imported abstractly or with internals too. this will render useless all those .Internals modules that now we need to add everywhere You're not alone!-) This has been called Open Implementation (OI, a pre-cursor of aspect-oriented programming): http://www2.parc.com/csl/groups/sda/projects/oi/ They argue for an explicit auxiliary interface instead of full access to module internals. Since these same folks worked on meta-object protocols as well (at the meta-level, the boundaries can be bypassed entirely), that suggestion probably comes from experience. They do allow for the auxiliary interface to use meta-programming style features, though that depends on the language in question (in Haskell, type classes or type functions might be used instead, but rewrite rules and Template Haskell are also available). Open Implementation Design Guidelines http://www2.parc.com/csl/groups/sda/publications/papers/Kiczales-ICSE97/ is a short paper discussing a Set API/Open Implementation example. I agree in principle, but GHC also uses that knowledge to optimize the code better - if a function is exported it has to produce the most polymorphic possible code for its type, if it isn't it can specialize better... that sort of thing. That refers to optimization in the provider module. As the OI people argued, optimization in the client modules also needs to be taken into account. If the default one-size-fits-all-uses implementation behind the default API doesn't work well enough, there'll be a proliferation of library variants. If there is a way to fine-tune the implementation via an auxiliary API, much of that can be avoided. In other words, instead of half a dozen Maps and a dozen Array variants, there'd just be one of each, but with auxiliary interfaces that would allow client code to choose and tune the most suitable implementations behind the main interfaces. It isn't magic, though: if, say, even the auxiliary API doesn't allow you to say thanks, but I know the length already, you're still stuck. But it does help to think about designing 2 APIs (the default functionality one and the auxiliary fine-tuning one) instead of offering only the choice of 1 API or full access to internals. Claus ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Help with Bird problem 3.3.3
I'm working my way through Bird's _Introduction to Functional
Programming Using Haskell_. I'd appreciate any help with problem
3.3.3, which is:
Division of natural numbers can be specified by the condition (n *
m) / n = m for all positive n and all m. Construct a program for
division and prove that it meets the specification.
The required construction relies on the following definitions:
data Nat= Zero| Succ Nat
(+) :: Nat - Nat
m + Zero= m
m + Succ n = Succ (m + n)
(*) :: Nat - Nat
m * Zero= Zero
m * Succ n = m * n + m
Proceeding as Bird does in Sec. 3.2.2, where he derives the definition
of - from the specification (m + n) - n = m, I've so far gotten
the first case, in which m matches the pattern Zero, simply by (i)
substituting Zero for m in the specification, (ii) substituting Succ n
for n in the specification (solely because n is constrained to be
positive), and (iii) reducing by applying the first equation of *:
Case Zero:
(Succ n * Zero) / Succ n = Zero
≡ {first equation of *}
Zero / Succ n = Zero
Easy enough, and completely intuitive, since we expect Zero divided by
any non-Zero finite number to be Zero. The next case, in which m
matches the pattern Succ m, is where I get stuck, and I really have
no intuition about what the definition is supposed to be. My first
step is to substitute Succ m for m in the given specification, and
to substitute Succ n for n in the specification (for the same reason,
as above, that n is constrained to be positive), and then to use the
definition of * to reduce the equation:
Case Succ m:
Succ n * Succ m / Succ n = Succ m
≡ {second equation of *}
(Succ n * m + Succ n) / Succ n = Succ m
Where do I go from here? Thank you so much.___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Cabal: local documentation
Hello, Can cabal automatically generate local documentation for packages I install? It'd be awesome if it generated a page like [1] for locally installed packages. Thanks, Martijn. [1] http://www.haskell.org/ghc/dist/current/docs/libraries/ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal: local documentation
Just pass '--enable-documentation' to 'cabal install'. On *nix they're generated at ~/.cabal/share/doc. HTH, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Hac5 projects page
Hello, on http://www.haskell.org/haskellwiki/Hac5/Projects, you can list a project under “Project descriptions” and under “Experiences”. What’s the difference? Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Hac5 projects page
Wolfgang Jeltsch wrote: on http://www.haskell.org/haskellwiki/Hac5/Projects, you can list a project under Project descriptions and under Experiences. What's the difference? A project description is something you plan to work on, and an experience is something you could help other people with if they were to work on it. Ganesh === Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html === ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hac5 projects page
on http://www.haskell.org/haskellwiki/Hac5/Projects, you can list a project under “Project descriptions” and under “Experiences”. What’s the difference? Project descriptions are supposed to be projects you're currently working on or want to work on during the Hackathon. Experiences are not necessarily projects (and feel free to update the description on the page to reflect that), but general Haskell-related things you are familiar with. So, if for example I am looking for someone with a lot of experience in writing library bindings using the FFI, I could look in that list if anyone attending might be able to help me ... HTH, Andres -- Andres Loeh, Universiteit Utrecht mailto:and...@cs.uu.nl mailto:m...@andres-loeh.de http://www.andres-loeh.de ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Re: package for algebraic structures
Am Dienstag, 24. Februar 2009 09:30 schrieb Aaron Denney: On 2009-02-19, Wolfgang Jeltsch g9ks1...@acme.softbase.org wrote: In addition, I wouldn’t include algebraic structures in a *numerical* prelude since the cool thing about them is that they are so abstract that they are not only about numbers. But the thing is that to have the numerical classes support the proper abstractions we want them to support, we need to define the algebraic structures as well. So the rework goes together... Of course! It’s just that having algebraic structures in a separate algebra package is in my opinion a better idea than having them in a numeric prelude. Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal: local documentation
2009/2/24 Felipe Lessa felipe.le...@gmail.com: Just pass '--enable-documentation' to 'cabal install'. On *nix they're generated at ~/.cabal/share/doc. Or edit ~/.cabal/config and set the documentation key to True ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
Don Stewart wrote: dons: [...] Just serialising straight lists of pairs, [...] And reading them back in, main = do [f] - getArgs m - decode `fmap` L.readFile f print (length (m :: [(B.ByteString,Int)])) print done Well, you don't actually read the whole list here, just its length: instance Binary a = Binary [a] where put l = put (length l) mapM_ put l get= do n - get :: Get Int replicateM n get To demonstrate, this works: main = do L.writeFile v (encode (42 :: Int)) m - decode `fmap` L.readFile v print (length (m :: [Int])) So instead, we should try something like this: import Control.Parallel.Strategies instance NFData B.ByteString where rnf bs = bs `seq` () main = do [f] - getArgs m - decode `fmap` L.readFile f print (rnf m `seq` length (m :: [(B.ByteString,Int)])) My timings: reading list, without rnf: 0.04s with rnf: 0.16s reading a Data.Map: 0.52s with rnf: 0.62s Bertram ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Help with another Bird problem (3.3.4)
Could someone provide a solution to do the following problem from Bird: The function log can be specified by the condition that log (2^m) = m for all m. Construct a program for log and prove that it meets the specification. Note that this problem doesn't specify a domain, unlike problem 3.3.3, which specified Nat as the domain. Thanks. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
Hello, On Tue, Feb 24, 2009 at 2:36 AM, Don Stewart d...@galois.com wrote: This idea was the motivation for the new Seq instance, which uses internals to build quickly. Encoding to disk, the dictionary, $ time ./binary /usr/share/dict/cracklib-small done ./binary /usr/share/dict/cracklib-small 0.07s user 0.01s system 94% cpu 0.088 total Decoding, $ time ./binary dict.gz 52848 done ./binary dict.gz 0.07s user 0.01s system 97% cpu 0.079 total instance (Binary e) = Binary (Seq.Seq e) where put s = put (Seq.length s) Fold.mapM_ put s get = do n - get :: Get Int rep Seq.empty n get where rep xs 0 _ = return $! xs rep xs n g = xs `seq` n `seq` do x - g rep (xs Seq.| x) (n-1) g Just a lot better. :) So ... Data.Map, we're looking at you! Indeed, that was the motivation for writing the patch for Seq. [Ross, thank you again for the help.] I had performance issues with lists, but noticed that switching to Sequence wasn't helping at all. This new definition takes advantage of the features that Seq has and List doesn't. Regarding Map, I like Felipe's idea of having a separate Internal. I know that Lemmih has a few other implementations of Map (compactMap, BerkeleyDB). If I remember correctly, he made BerkeleyDB an instance of Binary. That can probably give us some insight too. Paulo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pickling a finite map (Binary + zlib) [was: [Haskell-cafe] Data.Binary poor read performance]
Felipe Lessa wrote: On Tue, Feb 24, 2009 at 4:59 AM, Don Stewart d...@galois.com wrote: Looks like the Map reading/showing via association lists could do with further work. Anyone want to dig around in the Map instance? (There's also some patches for an alternative lazy Map serialisation, if people are keen to load maps -- happstack devs?). From binary-0.5: instance (Ord k, Binary k, Binary e) = Binary (Map.Map k e) where put m = put (Map.size m) mapM_ put (Map.toAscList m) get = liftM Map.fromDistinctAscList get instance Binary a = Binary [a] where put l = put (length l) mapM_ put l get= do n - get :: Get Int replicateM n get Can't get better, I think. We can improve it slightly (about 20% runtime in dons example [*]): instance (Ord k, Binary k, Binary e) = Binary (Map.Map k e) where get = liftM (Map.fromDistinctAscList . map strictValue) get where strictValue (k,v) = (v `seq` k, v) The point is that Data.Map.Map is strict in the keys, but not in the values of the map. In the case of deserialisation this means the values will be thunks that hang on to the Daya.Binary buffer. Now, from containers-0.2.0.0: fromDistinctAscList :: [(k,a)] - Map k a fromDistinctAscList xs = build const (length xs) xs where -- 1) use continutations so that we use heap space instead of stack space. -- 2) special case for n==5 to build bushier trees. build c 0 xs' = c Tip xs' build c 5 xs' = case xs' of ((k1,x1):(k2,x2):(k3,x3):(k4,x4):(k5,x5):xx) - c (bin k4 x4 (bin k2 x2 (singleton k1 x1) (singleton k3 x3)) (singleton k5 x5)) xx _ - error fromDistinctAscList build build c n xs' = seq nr $ build (buildR nr c) nl xs' where nl = n `div` 2 nr = n - nl - 1 buildR n c l ((k,x):ys) = build (buildB l k x c) n ys buildR _ _ _ [] = error fromDistinctAscList buildR [] buildB l k x c r zs = c (bin k x l r) zs The builds seem fine, but we spot a (length xs) on the beginning. Maybe this is the culprit? We already know the size of the map (it was serialized), so it is just a matter of exporting fromDistinctAscSizedList :: Int - [(k, a)] - Map k a Eliminating the 'length' call helps, too, improving runtime by another about 5%. The result is still a factor of 1.7 slower than reading the list of key/value pairs. Bertram [*] Notes on timings: 1) I used `rnf` for all timings, as in my previous mail. 2) I noticed that in my previous measurements, the GC time for the Data.Map tests was excessively large (70% and more), so I used +RTS -H32M this time. This resulted in a significant runtime improvement of about 30%. 3) Do your own measurements! Some code to play with is available here: http://int-e.home.tlink.de/haskell/MapTest.hs http://int-e.home.tlink.de/haskell/Map.hs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] controlling timeout for Network.Socket.connect - how?
Belka ha scritto: Hello, communion people! I have a problem and ask for an advice. I'm dealing with sockets on *Linux* platform (Network.Socket). The problem is that I can't fully control timeout for (connect :: Socket - SockAddr - IO ()) operation. On my system the timeout is - 3 seconds - What system? Is the timeout the same with a plain C program? connect timeout is typically 75 seconds. Also note that system timeout is only used when the socket is in blocking mode. [...] I know that controlling timeout is somehow connected to select(2) Yes. The only working method is to set the socket to non blocking mode, and use select (or poll/epoll/kqueue). [...] Manlio Perillo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] MPTC inheritance
Please forgive me if I'm still mentally contaminated by the OO way of seeing (and discussing) the universe, but I'm trying to figure out how to inherit an interface from a multi-parameter type class. I have a Graph class that's parameterisable by Node and Edge type: class (Node a, Edge b) = Graph a b where (lots of stuff that you can do with Graph a b) Now, I'd like to build a FooGraph on top of this that adds additional capabilities: class (Graph a b) = FooGraph a b where (lots of additional stuff) but this isn't allowed (kind mismatch). Of couse, I can do: class (Node a, Edge b) = FooGraph a b but this means that I have to manually replicate the Graph a b operations in the FooGraph a b class definition, which is (a) work that the machine should (?) be able to do for me, and (b) fragile. Any pointers / wisdom would be very much appreciated. - Derek ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] ONeillPrimes.hs - priority queue broken?
Hi,
I've recently tried to use the priority queue from the
ONeillPrimes.hs, which is famous for being a very fast prime
generator: actually, I translated the code to Scheme and dropped the
values, to end up with a key-only heap implementation.
However, the code didn't work quite well, and I decided to check the
haskell code itself.
Turns out that it is broken.
module PQ where
import Test.QuickCheck
data PriorityQ k v = Lf
| Br {-# UNPACK #-} !k v !(PriorityQ k v) !(PriorityQ k v)
deriving (Eq, Ord, Read, Show)
emptyPQ :: PriorityQ k v
emptyPQ = Lf
isEmptyPQ :: PriorityQ k v - Bool
isEmptyPQ Lf = True
isEmptyPQ _ = False
minKeyValuePQ :: PriorityQ k v - (k, v)
minKeyValuePQ (Br k v _ _)= (k,v)
minKeyValuePQ _ = error Empty heap!
minKeyPQ :: PriorityQ k v - k
minKeyPQ (Br k v _ _) = k
minKeyPQ _= error Empty heap!
minValuePQ :: PriorityQ k v - v
minValuePQ (Br k v _ _) = v
minValuePQ _ = error Empty heap!
insertPQ :: Ord k = k - v - PriorityQ k v - PriorityQ k v
insertPQ wk wv (Br vk vv t1 t2)
| wk = vk = Br wk wv (insertPQ vk vv t2) t1
| otherwise = Br vk vv (insertPQ wk wv t2) t1
insertPQ wk wv Lf = Br wk wv Lf Lf
siftdown :: Ord k = k - v - PriorityQ k v - PriorityQ k v - PriorityQ k v
siftdown wk wv Lf _ = Br wk wv Lf Lf
siftdown wk wv (t @ (Br vk vv _ _)) Lf
| wk = vk = Br wk wv t Lf
| otherwise = Br vk vv (Br wk wv Lf Lf) Lf
siftdown wk wv (t1 @ (Br vk1 vv1 p1 q1)) (t2 @ (Br vk2 vv2 p2 q2))
| wk = vk1 wk = vk2= Br wk wv t1 t2
| vk1 = vk2= Br vk1 vv1 (siftdown wk wv p1 q1) t2
| otherwise = Br vk2 vv2 t1 (siftdown wk wv p2 q2)
deleteMinAndInsertPQ :: Ord k = k - v - PriorityQ k v - PriorityQ k v
deleteMinAndInsertPQ wk wv Lf = error Empty PriorityQ
deleteMinAndInsertPQ wk wv (Br _ _ t1 t2) = siftdown wk wv t1 t2
leftrem :: PriorityQ k v - (k, v, PriorityQ k v)
leftrem (Br vk vv Lf Lf) = (vk, vv, Lf)
leftrem (Br vk vv t1 t2) = (wk, wv, Br vk vv t t2) where
(wk, wv, t) = leftrem t1
leftrem _= error Empty heap!
deleteMinPQ :: Ord k = PriorityQ k v - PriorityQ k v
deleteMinPQ (Br vk vv Lf _) = Lf
deleteMinPQ (Br vk vv t1 t2) = siftdown wk wv t2 t where
(wk,wv,t) = leftrem t1
deleteMinPQ _ = error Empty heap!
toDescList :: Ord k = PriorityQ k v - [(k,v)]
toDescList q | isEmptyPQ q = []
| otherwise = (minKeyValuePQ q) : toDescList (deleteMinPQ q)
fromList :: Ord k = [(k,v)] - PriorityQ k v
fromList = foldr (uncurry insertPQ) emptyPQ
Here goes a test:
*PQ let s = map fst . toDescList . fromList . (`zip` (repeat ())) ::
[Int]-[Int]
*PQ s [4,3,1,2]
[1,2,3,4]
Looks fine.
*PQ s [3,1,4,1,5,9,2,6,5,3,5,8]
[1,1,2*** Exception: Empty heap!
OK, probably it doesn't like duplicates.
*PQ s [3,1,4,5,9,2,6,8,10]
[1,2,3,4,5,9,10]
Whoops, 6 and 8 are lost.
So, the morale is: don't use the priority queue from ONeillPrimes in
your projects. It works for primes by a lucky chance.
I haven't yet figured out, however, what exactly the bug is.
--
Eugene Kirpichov
Web IR developer, market.yandex.ru
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Pickling a finite map (Binary + zlib) [was: Data.Binary poor read performance]
fromDistinctAscList :: [(k,a)] - Map k a fromDistinctAscList xs = build const (length xs) xs where -- 1) use continutations so that we use heap space instead of stack space. -- 2) special case for n==5 to build bushier trees. build c 0 xs' = c Tip xs' build c 5 xs' = case xs' of ((k1,x1):(k2,x2):(k3,x3):(k4,x4):(k5,x5):xx) - c (bin k4 x4 (bin k2 x2 (singleton k1 x1) (singleton k3 x3)) (singleton k5 x5)) xx By the way, did anyone test if (or when) this n==5 case bushier trees gains something? Thanks Christian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MPTC inheritance
There's nothing wrong with the definition of FooGraph. That's how you do it. -- Lennart On Tue, Feb 24, 2009 at 6:09 PM, Derek Gladding de...@solidmath.com wrote: Please forgive me if I'm still mentally contaminated by the OO way of seeing (and discussing) the universe, but I'm trying to figure out how to inherit an interface from a multi-parameter type class. I have a Graph class that's parameterisable by Node and Edge type: class (Node a, Edge b) = Graph a b where (lots of stuff that you can do with Graph a b) Now, I'd like to build a FooGraph on top of this that adds additional capabilities: class (Graph a b) = FooGraph a b where (lots of additional stuff) but this isn't allowed (kind mismatch). Of couse, I can do: class (Node a, Edge b) = FooGraph a b but this means that I have to manually replicate the Graph a b operations in the FooGraph a b class definition, which is (a) work that the machine should (?) be able to do for me, and (b) fragile. Any pointers / wisdom would be very much appreciated. - Derek ___ 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] MPTC inheritance - was operator error
Thanks to the kind replies I got off-list, I figured out that this was actually operator error on my part. class (Node a, Edge b) = Graph a b was actually class (Node a, Edge b) = Graph g a b but this was in code I'd written quite some time ago and I've written a lot of day-job C++ in the intervening period. Main lesson learned: Read the ghc error message carefully, it contains all the information you need. Thankyou once again. - Derek Derek Gladding wrote: Please forgive me if I'm still mentally contaminated by the OO way of seeing (and discussing) the universe, but I'm trying to figure out how to inherit an interface from a multi-parameter type class. I have a Graph class that's parameterisable by Node and Edge type: class (Node a, Edge b) = Graph a b where (lots of stuff that you can do with Graph a b) Now, I'd like to build a FooGraph on top of this that adds additional capabilities: class (Graph a b) = FooGraph a b where (lots of additional stuff) but this isn't allowed (kind mismatch). Of couse, I can do: class (Node a, Edge b) = FooGraph a b but this means that I have to manually replicate the Graph a b operations in the FooGraph a b class definition, which is (a) work that the machine should (?) be able to do for me, and (b) fragile. Any pointers / wisdom would be very much appreciated. - Derek ___ 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] MPTC inheritance
Derek Gladding wrote: Please forgive me if I'm still mentally contaminated by the OO way of seeing (and discussing) the universe, but I'm trying to figure out how to inherit an interface from a multi-parameter type class. [...] but this isn't allowed (kind mismatch). Kinds are a meta-type system for types. Because Haskell has such a rich type system, the types themselves need a type-like system. These are kinds. You never declare kinds (apart from certain language extensions not in use here): the compiler infers them. This suggests that your problem is in the types lower down. Probably you are using a or b in a way that implies they take a type argument in one place (kind * - *) and not in another place (kind *). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] New version of Hieroglyph released: Hieroglyph 1.1 is on hackage
For those of you who don't read Reddit: Changes are minor right now. The main thing is that I'm now using Russell O'Connor's excellent Data.Colour library. The only other changes were to make H. compile with Gtk2Hs 0.10.x and to make it a bit easier to integrate Gtk2Hs guis with Hieroglyph and vice versa. Enjoy! -- Jeff ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Hoogle and Network.Socket
On 2009 Feb 21, at 20:47, Jonathan Cast wrote: On Sat, 2009-02-21 at 07:25 -0700, John A. De Goes wrote: Not showing platform-specific packages by default *might* make package writers more likely to develop cross-platform packages. We've heard many times someone say, I don't know if it works on Windows, never really thought of that. Um, why *should* I think of that? I have to second this; I'm a Unix sysadmin, 98% of the time if I'm writing a program it's for Unix *and* requires POSIX APIxs, and even if it could apply to Windows the program needed there would be very significantly different. And we have a Windows group for that. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] The community is more important than the product
On 2009 Feb 21, at 18:59, Don Stewart wrote: http://haskell.org/haskellwiki/Protect_the_community Random notes on how to maintain tone, focus and productivity in an online community I took a few years ago. http://shirky.com/writings/group_enemy.html A group is its own worst enemy -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Haskellers on Twitter!
On 2009 Feb 23, at 11:26, Andrew Wagner wrote: Modified. Is this how you want it to show? That works, yes. -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help with another Bird problem (3.3.4)
On Tue, Feb 24, 2009 at 9:53 AM, Peter Hilal pe...@hilalcapital.com wrote: Could someone provide a solution to do the following problem from Bird: The function log can be specified by the condition that log (2^m) = m for all m. Construct a program for log and prove that it meets the specification. Well, here is the least solution on Nat: log n = head [ m | m - [0..], 2^m == n ] This meets the specification, and is _|_ everywhere else :-) The proof is trivial. Luke ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Binary poor read performance
wren ng thornton wrote:
If you have many identical strings then you will save lots by memoizing
your strings into Integers, and then serializing that memo table and the
integerized version of your data structure. The amount of savings
decreases as the number of duplications decrease, though since you don't
need the memo table itself you should be able to serialize it in a way
that doesn't have much overhead.
I had problems with the size of the allocated heap space after serializing
and loading data with the binary package. The reason was that
binary does not support sharing of identical elements and considered a
restricted solution for strings and certain other data types first, but
came up with a generic solution in the end.
(I did it just last weekend).
I put the Binary monad in a state transformer with maps for memoization:
type PutShared = St.StateT (Map Object Int, Int) PutM ()
type GetShared = St.StateT (IntMap Object) Bin.Get
In addition to standard get ant put methods:
class (Typeable α, Ord α, Eq α) ⇒ BinaryShared α where
put :: α → PutShared
get :: GetShared α
I added putShared and getShared methods with memoization:
putShared :: (α → PutShared) → α → PutShared
getShared :: GetShared α → GetShared α
For types that I don't want memoization I can either refer to the underlying
binary monad for primitive types, e.g.:
instance BinaryShared Int where
put = lift∘Bin.put
get = lift Bin.get
or stay in the BinaryShared monad for types of which I may memoize
components, e.g.:
instance (BinaryShared a, BinaryShared b) ⇒ BinaryShared (a,b) where
put (a,b) = put a ≫ put b
get = liftM2 (,) get get
And for types for which I want memoization, I wrap it with putShared and
getShared ,e.g:
instance BinaryShared a ⇒ BinaryShared [a] where
put= putShared (λl → lift (Bin.put (length l)) ≫ mapM_ put l)
get= getShared (do
n ← lift (Bin.get :: Bin.Get Int)
replicateM n get)
This save 1/3 of heap space to my application. I didn't measure time.
Maybe it would be useful to have something like this in the binary module.
Jürgen
PS: And here is the dirty implementation, in the case someone finds it
useful:
putShared :: (α → PutShared) → α → PutShared
putShared fput v = do
(dict, unique) ← St.get
case (ObjC v) `Map.lookup` dict of
Just i → lift (Bin.putWord8 0 ≫ putWord64be (fromIntegral i))
Nothing → do
St.put (dict,unique + 1)
lift (Bin.putWord8 1)
lift (putWord64be (fromIntegral unique))
fput v
(dict2, unique2) ← St.get
let newDict = Map.insert (ObjC v) unique dict2
St.put (newDict,unique2)
getShared :: GetShared α → GetShared α
getShared f = do
dict ← St.get
w ← lift Bin.getWord8
case w of
0 → do
i ← lift (liftM fromIntegral (getWord64be))
case IMap.lookup i dict of
Just (ObjC obj) → return (forceJust (cast obj)
Shared≫getShared: Cast failed)
Nothing → error ◊ Shared≫getShared : Dont find in Map
⊕ show i
1 → do
i ← lift (liftM fromIntegral (getWord64be))
obj ← f
dict2 ← St.get
St.put (IMap.insert i (ObjC obj) dict2)
return obj
_ → error ◊ Shared≫getShared : Encoding error
data Object = ∀ α. (Typeable α, Ord α, Eq α) ⇒ ObjC {unObj :: α}
instance Eq Object where
(ObjC a) ≡ (ObjC b) = if typeOf a ≠ typeOf b
then False
else (Just a) ≡ cast b -- can someone
explain to me why this works?
instance Ord Object where
compare (ObjC a) (ObjC b) = if typeOf a ≠ typeOf b
then compare
((unsafePerformIO∘typeRepKey∘typeOf) a)
((unsafePerformIO∘typeRepKey∘typeOf) b)
else compare (Just a) (cast b)
encodeSer :: BinaryShared a ⇒ a → L.ByteString
encodeSer v = runPut (evalStateT (put v) (Map.empty,0))
decodeSer :: BinaryShared α ⇒ L.ByteString → α
decodeSer = runGet (evalStateT get IMap.empty)
--
View this message in context:
http://www.nabble.com/Data.Binary-poor-read-performance-tp22167466p22192337.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] ONeillPrimes.hs - priority queue broken?
Am Dienstag, 24. Februar 2009 19:16 schrieb Eugene Kirpichov:
Hi,
I've recently tried to use the priority queue from the
ONeillPrimes.hs, which is famous for being a very fast prime
generator: actually, I translated the code to Scheme and dropped the
values, to end up with a key-only heap implementation.
However, the code didn't work quite well, and I decided to check the
haskell code itself.
Turns out that it is broken.
Indeed.
module PQ where
import Test.QuickCheck
data PriorityQ k v = Lf
| Br {-# UNPACK #-} !k v !(PriorityQ k v) !(PriorityQ k
| v)
deriving (Eq, Ord, Read, Show)
emptyPQ :: PriorityQ k v
emptyPQ = Lf
isEmptyPQ :: PriorityQ k v - Bool
isEmptyPQ Lf = True
isEmptyPQ _ = False
minKeyValuePQ :: PriorityQ k v - (k, v)
minKeyValuePQ (Br k v _ _)= (k,v)
minKeyValuePQ _ = error Empty heap!
minKeyPQ :: PriorityQ k v - k
minKeyPQ (Br k v _ _) = k
minKeyPQ _= error Empty heap!
minValuePQ :: PriorityQ k v - v
minValuePQ (Br k v _ _) = v
minValuePQ _ = error Empty heap!
insertPQ :: Ord k = k - v - PriorityQ k v - PriorityQ k v
insertPQ wk wv (Br vk vv t1 t2)
| wk = vk = Br wk wv (insertPQ vk vv t2) t1
| otherwise = Br vk vv (insertPQ wk wv t2) t1
insertPQ wk wv Lf = Br wk wv Lf Lf
siftdown :: Ord k = k - v - PriorityQ k v - PriorityQ k v - PriorityQ
k v siftdown wk wv Lf _ = Br wk wv Lf Lf
siftdown wk wv (t @ (Br vk vv _ _)) Lf
| wk = vk = Br wk wv t Lf
| otherwise = Br vk vv (Br wk wv Lf Lf) Lf
siftdown wk wv (t1 @ (Br vk1 vv1 p1 q1)) (t2 @ (Br vk2 vv2 p2 q2))
| wk = vk1 wk = vk2= Br wk wv t1 t2
| vk1 = vk2= Br vk1 vv1 (siftdown wk wv p1 q1) t2
| otherwise = Br vk2 vv2 t1 (siftdown wk wv p2 q2)
deleteMinAndInsertPQ :: Ord k = k - v - PriorityQ k v - PriorityQ k v
deleteMinAndInsertPQ wk wv Lf = error Empty PriorityQ
deleteMinAndInsertPQ wk wv (Br _ _ t1 t2) = siftdown wk wv t1 t2
leftrem :: PriorityQ k v - (k, v, PriorityQ k v)
leftrem (Br vk vv Lf Lf) = (vk, vv, Lf)
leftrem (Br vk vv t1 t2) = (wk, wv, Br vk vv t t2) where
(wk, wv, t) = leftrem t1
leftrem _= error Empty heap!
deleteMinPQ :: Ord k = PriorityQ k v - PriorityQ k v
deleteMinPQ (Br vk vv Lf _) = Lf
deleteMinPQ (Br vk vv t1 t2) = siftdown wk wv t2 t where
(wk,wv,t) = leftrem t1
deleteMinPQ _ = error Empty heap!
toDescList :: Ord k = PriorityQ k v - [(k,v)]
toDescList q | isEmptyPQ q = []
| otherwise = (minKeyValuePQ q) : toDescList (deleteMinPQ q)
fromList :: Ord k = [(k,v)] - PriorityQ k v
fromList = foldr (uncurry insertPQ) emptyPQ
Here goes a test:
*PQ let s = map fst . toDescList . fromList . (`zip` (repeat ())) ::
[Int]-[Int]
*PQ s [4,3,1,2]
[1,2,3,4]
Looks fine.
*PQ s [3,1,4,1,5,9,2,6,5,3,5,8]
[1,1,2*** Exception: Empty heap!
OK, probably it doesn't like duplicates.
That is not the problem.
*PQ s [3,1,4,5,9,2,6,8,10]
[1,2,3,4,5,9,10]
Whoops, 6 and 8 are lost.
So, the morale is: don't use the priority queue from ONeillPrimes in
your projects. It works for primes by a lucky chance.
I haven't yet figured out, however, what exactly the bug is.
The problem is that deleteMinPQ and siftdown assume that if the left subqueue
is empty then so is the right, but that assumption is sometimes wrong:
*PQ fromList [(k,k) | k - [1 .. 7]]
Br 1 1 (Br 2 2 (Br 4 4 Lf Lf) (Br 6 6 Lf Lf)) (Br 3 3 (Br 5 5 Lf Lf) (Br 7 7
Lf Lf))
*PQ deleteMinPQ it
Br 2 2 (Br 3 3 (Br 5 5 Lf Lf) (Br 7 7 Lf Lf)) (Br 4 4 Lf Lf)
*PQ deleteMinPQ it
Br 3 3 (Br 4 4 Lf Lf) (Br 5 5 Lf Lf)
*PQ deleteMinPQ it
Br 4 4 (Br 5 5 Lf Lf) Lf
*PQ deleteMinPQ it
Br 5 5 Lf Lf
*PQ deleteMinPQ it
Lf
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help with Bird problem 3.3.3
On Tue, Feb 24, 2009 at 10:25:56AM -0500, Peter Hilal wrote: Where do I go from here? Thank you so much. A hint: I don't think you can do it by recursion on (/). You'll need an auxiliary function. Then prove that your function satisfies the constraint. Phil (Unless there's some clever way to repeatedly divide which comes out with the right answer that I'm not seeing of course...) -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Binary poor read performance
jnf: wren ng thornton wrote: If you have many identical strings then you will save lots by memoizing your strings into Integers, and then serializing that memo table and the integerized version of your data structure. The amount of savings decreases as the number of duplications decrease, though since you don't need the memo table itself you should be able to serialize it in a way that doesn't have much overhead. I had problems with the size of the allocated heap space after serializing and loading data with the binary package. The reason was that binary does not support sharing of identical elements and considered a restricted solution for strings and certain other data types first, but came up with a generic solution in the end. (I did it just last weekend). And this is exactly the intended path -- that people will release their own special instances for doing more elaborate parsing/printing tricks! I put the Binary monad in a state transformer with maps for memoization: type PutShared = St.StateT (Map Object Int, Int) PutM () type GetShared = St.StateT (IntMap Object) Bin.Get In addition to standard get ant put methods: class (Typeable α, Ord α, Eq α) ⇒ BinaryShared α where put :: α → PutShared get :: GetShared α I added putShared and getShared methods with memoization: putShared :: (α → PutShared) → α → PutShared getShared :: GetShared α → GetShared α For types that I don't want memoization I can either refer to the underlying binary monad for primitive types, e.g.: instance BinaryShared Int where put = lift∘Bin.put get = lift Bin.get or stay in the BinaryShared monad for types of which I may memoize components, e.g.: instance (BinaryShared a, BinaryShared b) ⇒ BinaryShared (a,b) where put (a,b) = put a ≫ put b get = liftM2 (,) get get And for types for which I want memoization, I wrap it with putShared and getShared ,e.g: instance BinaryShared a ⇒ BinaryShared [a] where put= putShared (λl → lift (Bin.put (length l)) ≫ mapM_ put l) get= getShared (do n ← lift (Bin.get :: Bin.Get Int) replicateM n get) This save 1/3 of heap space to my application. I didn't measure time. Maybe it would be useful to have something like this in the binary module. Very nice. Maybe even upload these useful instances in a little binary-extras package? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] emacs cedet support for haskell?
Hi, I've googled around for possible haskell support in emacs cedet, but couldn't find any. From cedet's website, it claims to support the following Language Parsers Parsers that have already been implemented: Emacs Lisp, Java, C/C++, C#, Python, Erlang, awk, Makefile, Scheme, HTML, Texinfo, Javascript, dot. Also: Semantic's own grammar format (.by or .wy) Is there any plan to support haskell in the near future? Best, Xiao-Yong -- c/*__o/* \ * (__ */\ ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Data.Binary poor read performance
On Tue, Feb 24, 2009 at 7:42 PM, jutaro j...@arcor.de wrote: instance Eq Object where (ObjC a) ≡ (ObjC b) = if typeOf a ≠ typeOf b then False else (Just a) ≡ cast b -- can someone explain to me why this works? In fact, can't you just say instance Eq Object where ObjC a == ObjC b = Just a == cast b ? -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Cabal: local documentation
On Tue, 2009-02-24 at 17:42 +0100, Svein Ove Aas wrote: 2009/2/24 Felipe Lessa felipe.le...@gmail.com: Just pass '--enable-documentation' to 'cabal install'. On *nix they're generated at ~/.cabal/share/doc. Or edit ~/.cabal/config and set the documentation key to True However this does not maintain a complete module index like I think Martijn is after. It would be great if someone volunteered to implement that. There's a ticket open for it: http://hackage.haskell.org/trac/hackage/ticket/206 One question is where to put a central index. This is especially true for the case of global installations. For per-user installs it's probably fine to use ~/.cabal/share/doc/index.html or something, but for the case of /usr/local that's certainly not ok. Needs some thought. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] IntMap documentation error
On Mon, 2009-02-23 at 17:22 -0600, Louis Wasserman wrote: In the documentation for Data.IntMap updateMin, a piece of example code both communicates incorrect intuition, and fails to even compile. updateMin :: (a - a) - IntMap a - IntMap a updateMin (\ _ - Nothing) (fromList [(5,a), (3,b)]) -- code straight from the docs interactive:1:49: Couldn't match expected type `Maybe a' against inferred type `[Char]' In the expression: a In the expression: (5, a) In the first argument of `fromList', namely `[(5, a), (3, b)]' As a side note, the sort of operation implied by the example code was really what I was looking for in the documentation -- but such a method no longer exists in IntMap. ::sad:: Who do I tell this to / how do I ask to get it fixed? Open a ticket in the ghc trac: http://hackage.haskell.org/trac/ghc/ set the component to libraries other. Paste in your description and if you can, attach a darcs patch to the ticket. More generally, to work out where to send things check the hackage page. Most packages list a maintainer or author and some are now specifying a bug reports url. Currently for the containers package it's not all that helpful, it only lists a maintainer email address as librar...@haskell.org. Though that would also have been a place to start to get the above advice. The next release of all the core packages will also list their bug-report urls and these will appear on their hackage pages. Duncan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Help with Bird problem 3.3.3
Try starting with
(m * n) / m = n -- given m /= 0
Then do case analysis on n.
I found this process quite enlightening, thanks for posting.
-- ryan
2009/2/24 Peter Hilal pe...@hilalcapital.com:
I'm working my way through Bird's _Introduction to Functional Programming
Using Haskell_. I'd appreciate any help with problem 3.3.3, which is:
Division of natural numbers can be specified by the condition (n * m) / n =
m for all positive n and all m. Construct a program for division and prove
that it meets the specification.
The required construction relies on the following definitions:
data Nat= Zero| Succ Nat
(+) :: Nat - Nat
m + Zero= m
m + Succ n = Succ (m + n)
(*) :: Nat - Nat
m * Zero= Zero
m * Succ n = m * n + m
Proceeding as Bird does in Sec. 3.2.2, where he derives the definition of
- from the specification (m + n) - n = m, I've so far gotten the first
case, in which m matches the pattern Zero, simply by (i) substituting Zero
for m in the specification, (ii) substituting Succ n for n in the
specification (solely because n is constrained to be positive), and (iii)
reducing by applying the first equation of *:
Case Zero:
(Succ n * Zero) / Succ n = Zero
≡ {first equation of *}
Zero / Succ n = Zero
Easy enough, and completely intuitive, since we expect Zero divided by any
non-Zero finite number to be Zero. The next case, in which m matches the
pattern Succ m, is where I get stuck, and I really have no intuition about
what the definition is supposed to be. My first step is to substitute Succ
m for m in the given specification, and to substitute Succ n for n in the
specification (for the same reason, as above, that n is constrained to be
positive), and then to use the definition of * to reduce the equation:
Case Succ m:
Succ n * Succ m / Succ n = Succ m
≡ {second equation of *}
(Succ n * m + Succ n) / Succ n = Succ m
Where do I go from here? Thank you so much.
___
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] ONeillPrimes.hs - priority queue broken?
Eugene Kirpichov wrote:
Hi,
I've recently tried to use the priority queue from the
ONeillPrimes.hs, which is famous for being a very fast prime
generator: actually, I translated the code to Scheme and dropped the
values, to end up with a key-only heap implementation.
However, the code didn't work quite well, and I decided to check the
haskell code itself.
Turns out that it is broken.
module PQ where
import Test.QuickCheck
data PriorityQ k v = Lf
| Br {-# UNPACK #-} !k v !(PriorityQ k v) !(PriorityQ k v)
deriving (Eq, Ord, Read, Show)
Let
size Lf = 0
size (Br _ _ l r) = 1 + sizePQ l + sizePQ r
be the size of the priority queue.
To work, the code maintains heap order and the invariant that the left
subtree is at least as large as the right one, and at most one element
larger.
validSize Lf = True
validSize (Br _ _ l r) = validSize l validSize r 0 = d d = 1
where d = size l - size r
This invariant justifies the assumption that Daniel Fischer pointed out.
The code is careful to maintain this invariant, but it is broken in one
place:
leftrem :: PriorityQ k v - (k, v, PriorityQ k v)
leftrem (Br vk vv Lf Lf) = (vk, vv, Lf)
(Why not this?)
leftrem (Br vk vv Lf _) = (vk, vv, Lf)
leftrem (Br vk vv t1 t2) = (wk, wv, Br vk vv t t2) where
(wk, wv, t) = leftrem t1
Here, the left subtree is replaced by one that is one element smaller.
This breaks the invariant if the two original subtrees had equal size.
The bug is easy to fix; just swap the two subtrees on the right side:
leftrem (Br vk vv t1 t2) = (wk, wv, Br vk vv t2 t) where
(wk, wv, t) = leftrem t1
leftrem _= error Empty heap!
*PQ s [3,1,4,1,5,9,2,6,5,3,5,8]
[1,1,2*** Exception: Empty heap!
*PQ s [3,1,4,1,5,9,2,6,5,3,5,8]
[1,1,2,3,3,4,5,5,5,6,8,9]
HTH,
Bertram
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Indentation Question.
Hello All~
I have been reading the book Haskell for real programmers and am
presently on chapter 03.
There was a small program demonstrated by the author on let. The
problem is that when I cut and paste authors code into eclipse, the
program works fine, where as when I write my own copy of the program I
am getting an error. I figured out that when I remove the function any
one function lend or bend, the file compiles and runs fine.
My question is why does the Haskell compiler complains, in the case 2
functions with the same signature and logic, even though their names are
different.
module Lending where
{-- snippet lend --}
lend amount balance = let reserve= 100
newBalance = balance - amount
in if balance reserve
then Nothing
else Just newBalance
{-- /snippet lend --}
bend amount balance = let reserver = 100
newBalance=balance-amount
in if balance reserver
then Nothing
else Just newBalance
Regards
-Vivek Ramaswamy-
Disclaimer: This e-mail, including any attachment(s) hereto, is intended
only for the individual or entity to whom it is addressed. It may
contain proprietary, confidential or privileged information or attorney
work product belonging to Fidelity Business Services India Pvt. Ltd.
(FBS India) or its affiliates. If you are not the intended recipient of
this e-mail, or if you have otherwise received this e-mail in error,
please immediately notify the sender via return e-mail and permanently
delete the original mail, any print outs and any copies, including any
attachments. Any dissemination, distribution, alteration or copying of
this e-mail is strictly prohibited. The originator of this e-mail does
not guarantee the security of this message and will not be responsible
for any damages arising from any dissemination, distribution, alteration
or copying of this message and/or any attachments to this message by a
third party or as a result of any virus being passed on. Any comments or
statements made in this are not necessarily those of FBS India or any
other Fidelity entity. All e-mails sent from or to FBS India may be
subject to our monitoring and recording procedures.
..
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: Indentation Question.
Ramaswamy, Vivek vivek.ramasw...@fmr.com writes:
Hello All~
I have been reading the book ?Haskell for real programmers? and am presently
on
chapter 03.
There was a small program demonstrated by the author on ?let?. The problem is
that when I cut and paste authors code into eclipse, the program works fine,
where as when I write my own copy of the program I am getting an error. I
figured out that when I remove the function any one function lend or bend, the
file compiles and runs fine.
My question is why does the Haskell compiler complains, in the case 2
functions
with the same signature and logic, even though their names are different.
module Lending where
{-- snippet lend --}
lend amount balance = let reserve= 100
newBalance = balance - amount
in if balance reserve
then Nothing
else Just newBalance
{-- /snippet lend --}
bend amount balance = let reserver = 100
newBalance=balance-amount
The problem is here
each element in a let clause should be indented to the same level, that
is
let foo = bar
baz = qux
is legal. foo and baz are both defined. But
let foo = bar
baz = qux
is not legal, the compiler thinks baz = qux is part of the statement
`foo = bar`, like `foo = bar baz = qux`. Also
let foo = bar
baz = qux
is not legal, since the compiler thinks the let clause is over and
expects the keyword `in`
in if balance reserver
then Nothing
else Just newBalance
Regards
-Vivek Ramaswamy-
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] MapReduce reverse engineered
Hello, Here is an interesting paper of Google's MapReduce reverse engineered into Haskell. I apologize if already posted . http://www.cs.vu.nl/~ralf/MapReduce/ Kind regards, Vasili ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ONeillPrimes.hs - priority queue broken?
Eugene Kirpichov wrote:
module PQ where
import Test.QuickCheck
data PriorityQ k v = Lf
| Br {-# UNPACK #-} !k v !(PriorityQ k v) !(PriorityQ k v)
deriving (Eq, Ord, Read, Show)
For the record, we can exploit the invariant that the sizes of the left
and right subtrees have difference 0 or 1 to implement 'size' in better
than O(n) time, where n is the size of the heap:
-- Return number of elements in the priority queue.
-- /O(log(n)^2)/
size :: PriorityQ k v - Int
size Lf = 0
size (Br _ _ t1 t2) = 2*n + rest n t1 t2 where
n = size t2
-- rest n p q, where n = size q, and size p - size q = 0 or 1
-- returns 1 + size p - size q.
rest :: Int - PriorityQ k v - PriorityQ k v - Int
rest 0 Lf _ = 1
rest 0 _ _ = 2
rest n (Br _ _ p1 p2) (Br _ _ q1 q2) = case r of
0 - rest d p1 q1 -- subtree sizes: (d or d+1), d; d, d
1 - rest d p2 q2 -- subtree sizes: d+1, (d or d+1); d+1, d
where (d, r) = (n-1) `quotRem` 2
Of course we can reduce the cost to O(1) by annotating the heap with its
size, but that is less interesting, and incurs a little overhead in the
other heap operations.
Bertram
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Re: The community is more important than the product
On Sat, 21 Feb 2009 15:59:54 -0800, Don Stewart d...@galois.com wrote: http://haskell.org/haskellwiki/Protect_the_community Random notes on how to maintain tone, focus and productivity in an online community I took a few years ago. Might be some material there if anyone's seeking to help ensure we remain a constructive, effective community. To quote Simon Peyton-Jones (see the fourth unbolded paragraph in Computerworld - The A-Z of Programming Languages: Haskell at http://www.computerworld.com.au/article/261007/-z_programming_languages_haskell?pp=10); viz.: What I’m really trying to say is that the fact Haskell hasn’t become a real mainstream programming language, used by millions of developers, has allowed us to become much more nimble, and from a research point of view, that’s great. We have lots of users so we get lots of experience from them. What you want is to have a lot of users but not too many from a research point of view -- hence the avoid success at all costs. Avoid success at all costs! -- 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
