July 2008 - Haskell-Cafe

Optimizing 'sequence'
by Gracjan Polak 23 Jul '08

23 Jul '08

Hi all, On the other day I noticed that we could optimize 'sequence' more. I needed it for my monadic parser. Below is my small experiment. Sequence from standard library needs 2.3s to finish (and additional stack space), my version uses only 0.65s and default stack. Is my version better or am I missing something obvious? -- standard sequence1 :: Monad m => [m a] -> m [a] sequence1 ms = foldr k (return []) ms where k m m' = do { x <- m; xs <- m'; return (x:xs) } -- accumulator version sequence2 :: Monad m => [m a] -> m [a] sequence2 ms = sequence' [] ms where sequence' vs [] = return (reverse vs) sequence' vs (m:ms) = m >>= (\v -> sequence' (v:vs) ms) main = do let l = map return [1..1000000] w <- sequence1 l print (sum w) return () gracjan@home:~/some_faster> time ./Some1 +RTS -K100M 500000500000 real 0m2.318s user 0m2.284s sys 0m0.032s gracjan@home:~/some_faster> time ./Some2 500000500000 real 0m0.652s user 0m0.592s sys 0m0.052s -- Gracjan

7 11

InterleavableIO
by Marco Túlio Gontijo e Silva 23 Jul '08

23 Jul '08

Hello, I've done a package based on the Jules Bean's e-mail [1] to Haskell-Café, with a more generalized implementation. In the original version, you could use InterleavableIO with StateT Int IO (), but not with StateT Int (ReaderT Char IO) (). In this version, this is possible. The package, interleavableIO, is available at [2]. I've also done an application that generates a version of a module with generalized parameters, called interleavableGen, available at [3]. This is very alpha, and interleavableGen has been tested only with Control.Exception yet. Comments are very welcome. Greetings. [1]: http://www.haskell.org/pipermail/haskell-cafe/2007-July/028501.html [2]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/interleavableIO-… [3]: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/interleavableGen… -- Marco Túlio Gontijo e Silva Página: http://marcotmarcot.googlepages.com/ Blog: http://marcotmarcot.blogspot.com/ Correio: marcot(a)riseup.net XMPP: marcot(a)jabber.org IRC: marcot(a)irc.freenode.net Telefone: 25151920 Celular: 98116720 Endereço: Rua Turfa, 639/701 Prado 30410-370 Belo Horizonte/MG Brasil

1 0

Newbie: Replacing substring?
by Dmitri O.Kondratiev 23 Jul '08

23 Jul '08

A few simple questions: What standard library function can be used to replace substring in a string (or sub-list in a list) ? I wrote my own version, please criticize: -- replace all occurances of "123" with "58" in a string: test = replStr "abc123def123gh123ikl" "123" "58" {-- In a string replace all occurances of an 'old' substring with a 'new' substring --} replStr str old new = foldr ((\newSub before after -> before ++ newSub ++ after) new) [] chunks where chunks = splitStr str old {-- Split string into a list of chunks. Chunks are substrings located in a string between 'sub' substrings --} splitStr str sub = mkChunkLst str sub [] where -- mkChunkLst 'src string' 'substr-to-extract' 'list of chunks' -- makes list of chunks located between 'substr-to-extract' pieces in src string mkChunkLst [] _ chunkLst = chunkLst mkChunkLst str sub chunkLst = mkChunkLst after sub (chunkLst ++ [chunk]) where (chunk, _, after) = takeOut str sub [] [] {-- Take out substring from a string. String is divided into: "before substr" ++ "match" ++ "after substr" where 'match' is substring to split out --} takeOut after [] before match = (before, match, after) takeOut [] _ before match = (before, match, []) takeOut (x:xs) (y:ys) before match | x == y = takeOut xs ys before (match ++ [x]) | otherwise = takeOut xs (y:ys) (before ++ match ++ [x]) [] -- Dmitri O. Kondratiev dokondr(a)gmail.com http://www.geocities.com/dkondr

4 5

ANN: list-extras 0.1.0
by wren ng thornton 23 Jul '08

23 Jul '08

hello all~ I'm pleased to announce the initial version of list-extras, a home for common not-so-common list functions. There are many simple but non-trivial functions for lists which Data.List lacks. Typically we write a version and include it in a larger project or store it in a local source tree for personal jobs. But neither of these approaches makes it easy to distribute the code and take advantage of open-source development for improving the code. Since I had code from both approaches, I'm taking the first step and putting a package out there. So far it's not too large though I'll be adding things as they come up. If you have functions you think would belong, feel free to contact me. list-extras includes: - Prelude.Listless This module provides the "Prelude" but removing all the list functions. This is helpful for modules that overload those function names to work for other types. - Data.List.Extras.LazyLength This module provides least-strict functions for getting a list's length and doing natural things with it. On GHC this module also uses rewrite rules to convert certain calls to 'length' into our least-strict versions. [We could do this inefficiently by defining a version of 'length' which returns a Peano integer, but this module is more efficient.] - Data.List.Extras.Pair This module provides safe zipping functions which will fail (return 'Nothing') on uneven length lists. [We could do this by getting the lengths first and comparing, but this module is less strict when the lengths are uneven, and we only traverse the lists once.] - Data.List.Extras.ArgMax This module provides variants of the 'maximum' and 'minimum' functions which return the element for which some function is maximized or minimized. [We could do this by a decorate-fold-undecorate pattern, but this version is more space efficient.] Links to the hackage and darcs copies of list-extras can be found at: http://code.haskell.org/~wren/ -- Live well, ~wren

2 1

Linux kernel/library question
by Galchin, Vasili 23 Jul '08

23 Jul '08

Hello, I am working on POSIX stuff. I have used Linux as my POSIX OS and have read source when I could find it. Does anybody in this group of Linux newsgroup where one can ask Linux-related implementation questions? Regards, Vasili

3 3

Re: [Haskell-cafe] BLAS Solve Example
by Patrick Perry 22 Jul '08

22 Jul '08

Sorry Darrin, the BLAS library only includes matrix multiplication and solving triangular systems. To solve a general system, you would need to use LAPACK, but there aren't any bindings for that library yet. I would suggest you take a look at the hmatrix package, which includes a lot more linear algebra than blas does.. Patrick

1 0

Portland & OSCon
by John Goerzen 22 Jul '08

22 Jul '08

Hi, OSCon is happening in Portland, OR starting 2 weeks from today, with probably the largest number of people there on July 23 and 24. I know there are a number of Haskellers that live in the Portland area, and I suspect a few more may be going to OSCon. Anyone interested in a Haskell gathering someplace? -- John

4 4

Building NDP with latest GHC
by Austin Seipp 22 Jul '08

22 Jul '08

Hi, After my last issue with GHC's HEAD, I tried checking it out again and getting the patches for the libraries and lo and behold, it worked. So now I'm up to date with the latest libraries and the compiler, but it appears that building NDP itself is proving to be troublesome. (This is on GHC 6.9.20080720, btw) I've pulled the latest ndp package from http://darcs.haskell.org/packages/ndp into ./libraries. Instructions that are listed in [1]: > % cd libraries > % darcs get http://darcs.haskell.org/packages/ndp/ > % make make.library.ndp > % cd ndp/examples > % make This fails on step 3; the Makefile in the libraries subdirectory doesn't recognize 'make.library.ndp' as a valid target. Instructions in the actual README that comes with package ndp: > cd ndp > make boot > make > cd examples > make This fails on the 'make boot' step, because if you look at the Makefile, it thinks the top of the GHC source tree is at '..', when it's actually '../..' in relation to ./libraries/ndp: > TOP=.. > include $(TOP)/mk/boilerplate.mk > include ndp.mk > ... rest of makefile ... No big deal in this case, just a fix of changing TOP to '../..' Having done that, however, now it fails because it it cannot correctly parse bootstrapping.conf which is located in ./libraries: > $ make boot > ../../mk/target.mk:454: warning: overriding commands for target `libHSndp' > ../../mk/package.mk:249: warning: ignoring old commands for target `libHSndp' > ../../mk/target.mk:454: warning: overriding commands for target `ghc-prim.a' > ../../mk/package.mk:249: warning: ignoring old commands for target `ghc-prim.a' > /Users/austinseipp/src/ghc-head/ghc/stage1-inplace/bin/ghc -M > -optdep-f -optdep.depend -osuf o -package-conf > /Users/austinseipp/src/ghc-head/libraries/bootstrapping.conf -H32m > -O -fasm -Rghc-timing -package-name ndp ghc-prim-0.1 -O -fgenerics > -package base -XGenerics -fglasgow-exts -fbang-patterns -O2 > -funbox-strict-fields -fdicts-cheap -fno-method-sharing > -fno-spec-constr-threshold -fmax-simplifier-iterations20 -threaded > -XTypeFamilies -fcpr-off > > ... lots of files trying to get compiled here ... > > <no location info>: > Warning: -fgenerics is deprecated: Use the Generics language > instead > > <no location info>: > Warning: -fbang-patterns is deprecated: Use the BangPatterns > language instead > ghc: > /Users/austinseipp/src/ghc-head/libraries/bootstrapping.conf:1:62: > parse error on input `"' > <<ghc: 41436660 bytes, 4 GCs, 118784/118784 avg/max bytes residency (1 > samples), 31M in use, 0.00 INIT (0.00 elapsed), 0.08 MUT (0.12 > elapsed), 0.01 GC (0.02 elapsed) :ghc>> > make: *** [depend] Error 1 For the record, the thing it fails on is the *first* occurance of a quotation mark, and that's here in bootstrapping.conf: > [InstalledPackageInfo {package = PackageIdentifier {pkgName = > "filepath", pkgVersion = ... So it's failing when it sees the quote at the start of "filepath" I have also attempted to follow the instructions at the top ./libraries/Makefile, which are: > # To do a fresh build: > # > # make clean > # make boot > # make > # > # To rebuild a particular library <package>: > # > # make clean.library.<package> > # make make.library.<package> > # > # or the following is equivalent: > # > # make remake.library.<package> > # > # To add a new library to the tree, do > # > # darcs get http://darcs.haskell.org/packages/foo > # [ -e foo/configure.ac ] && ( cd foo && autoreconf ) > # make make.library.foo As said above, 'make.library.ndp' does not work, doing a full clean, boot and then make again doesn't pick up NDP either, and in the last case (adding a new library,) it doesn't matter because there is no configure.ac at the top level of ./libraries/ndp I think I might simply have a *lot* of outdated information. For the record, this is what I want to try and compile: > {-# OPTIONS_GHC -fglasgow-exts -fparr -fvectorise #-} > module Main where > import GHC.PArr > > dotp :: Num a => [:a:] -> [:a:] -> a > dotp xs ys = sumP [:x * y | x <- xs, y <- ys :] > > main = print $ dotp [:1..5:] [:6..10:] Naturally when trying, it fails because DPH isn't there: > $ ~/ghc-head/bin/ghc --make dotp.hs > > <no location info>: > Warning: -fparr is deprecated: Use the PArr language instead > [1 of 1] Compiling Main ( dotp.hs, dotp.o ) > GHC error in desugarer lookup in main:Main: > Failed to load interface for `Data.Array.Parallel.Lifted.PArray': > no package matching dph-par was found > ghc: panic! (the 'impossible' happened) > (GHC version 6.9.20080720 for i386-apple-darwin): > initDs user error (IOEnv failure) > > Please report this as a GHC bug: > http://www.haskell.org/ghc/reportabug (This leads me to believe I actually want http://darcs.haskell.org/packages/dph, but it's not mentioned. Anywhere.) If I'm just doing everything wrong, I'd really appreciate knowing and I'd be *more* than happy to update the wiki pages so that more people can try it and have it build successfuly, because as it stands I'm coming to the conclusion that basically all the information in [1] is just old and flat-out wrong, and I'm completely of ideas on how to go about this. Thanks, Austin [1] http://haskell.org/haskellwiki/Data_Parallel_Haskell/PackageNDP

2 1

Trees (Rose Trees?)
by Ryan Bloor 21 Jul '08

21 Jul '08

hi I was curious as to whether my implementation of a Rose Tree and a sumTree function was correct. The aumTree adds up the elements of a tree. data Tree a = Leaf a | Node [Tree a] sumTree :: Tree Int -> Int sumTree (Node []) = 0 sumTree (Node xs) = sum (map sumTree xs) The problem with this is I get a pattern matching error. Am I representing trees right... see below. Also, would an empty tree be represented by ... Node [] with this implementation? How would I represent a tree of the form... Tree (Node 2(Node 6 Empty Empty) Empty) taken from a binary one. Like this? Node [ [Leaf 2], Node [ Leaf 6,Node[],Node[] ], Node[] ] Ryan _________________________________________________________________ Find the best and worst places on the planet http://clk.atdmt.com/UKM/go/101719807/direct/01/

2 1

Re: Extending the GSoC model
by Neil Mitchell 21 Jul '08

21 Jul '08

Hi Suggested by Andrew Wager on libraries@, moving to haskell-cafe@ since its a really interesting idea and libraries is probably not the best place for it. > Not sure if this is the best place to suggest this, but I was > wondering about the possibility of extending the model that we > currently use for Google's Summer of Code. > > The benefits: > 1.) A place to make suggestions for code you would never be able to > write, and somebody else might not think of > 2.) A place to see what's being worked on, but not yet done > 3.) A way for people who are less confident in their haskell-foo to find mentors > 4.) A way for people who are more confident in their haskell-foo to > contribute without spending a ton of time hacking up actual code > 5.) Overall, more (and higher-quality) libraries And my thoughts: 1) I think as long as the suggestions are small improvements to existing projects it could work really well. New projects are probably less likely to work without the original author having the original motivation. I have one of these for some of my projects: http://code.google.com/p/ndmitchell/issues/list - a bug tracker works quite well. 2) Bug trackers do this. 3, 4) Fantastic idea, coordinating via the IRC channel already gives some of this, but it could be made more direct. Also having a specific person to talk to, and to review/commit/integrate the work makes the work more useful. 5) Always a great idea. So I think these things could be achieved by integrating various bug trackers, ensuring lots of projects on hackage have bug trackrs, and some mailing list for people working on this to allow people to ask for mentors and mentors to be available to respond. My guess that if there are the people who want mentors, then mentors could be found - but the other way round won't happen. Thanks Neil

1 0