August 2007 - Haskell-Cafe

Bi-directional Maps
by Andrew Wagner 02 Sep '07

02 Sep '07

Hi folks! So, in writing my chess engine, I've been trying to maintain 2 Map objects. One maps squares on the board to Ints, the other maps Ints to actual Pieces. It occurred to me that it would be useful to explicitly have a Bi-directional Map, which does the maintenance of keeping the Maps synchronized behind the scenes. Thus, Bimap was born! I've taken the API for Data.Map (which you can find at ), and cannibalized it for Bimap. The new API is at http://hpaste.org/2344 . The idea is that if you have a Bimap k a, and you want to treat the k's as keys, and use a function like Data.Map.foo, it will be called Data.Map.left_foo in Bimap. And if they want to do the same thing, but using the a's as keys, then they simply use right_foo. The metaphor is that we can view it as a Map in 2 directions, manipulating it from the left (on the k's), or from the right (on the a's). Is this useful? Is there a better way? Is the API too big, and if so, how can it be pared down?

5 6

Ideas
by Andrew Coppin 02 Sep '07

02 Sep '07

How easy would it be to make / would anybody care / has somebody already made ... in Haskell? - Blogging software. (Because there isn't enough of it in the world yet.) - A wiki program. (Ditto.) - A general CMS. - An interactive function plotter. (GNUplot is nice, but it can't plot recursive functions...) - A "graphical programming tool". (You add boxes and put in lines, it constructs a "program" that you can run.)

16 40

Looking for suggestions to improve my algorithm
by David Frey 02 Sep '07

02 Sep '07

Hello Haskellers, I have been trying to learn a bit about Haskell by solving Project Euler problems. For those of you who don't know what Project Euler is, see http://projecteuler.net After solving problem 21, which is related to amicable pairs, I decided to attempt problem 95 since it is an extension of the same topic. The full description of problem 95 is here: http://projecteuler.net/index.php?section=problems&id=95 This is the summary: "Find the smallest member of the longest amicable chain with no element exceeding one million." I have attempted to solve this problem, but my solution is too resource hungry to search the full set of 1000000 numbers. I am hoping someone reading this list can suggest : - How I can improve my algorithm - An alternative algorithm that will be more efficient - Ways to profile a Haskell program to help me understand why my implementation is performing poorly. In addition to the question above, I would also be interested in comments on the style of the code. If there is a more idiomatic way to write portions of the code, I would like to see what it is. My solution is at the bottom of this e-mail. The program will probably run obscenely slow or die from stack overflow unless you replace [1..999999] with [1..somethingSmaller] in main. Thanks, David Frey --- BEGIN Main.hs --- module Main where import ProjectEuler (takeUntil, divisors) import qualified Data.Map as M import qualified Data.IntSet as I main = let initialContext = Context (I.fromList []) 0 0 in print $ cycleStart $ foldl checkForChain initialContext [1..999999] {- Idea: * Put all the numbers that have been visited into a map regardless of whether they are a part of a chain or not. * Store the min element in the cycle and the number of elements in the cycle * As you process, from 1->n if the stopping conditions for a sumOfDivisors result are: * has already been seen before * number is less than the start of this chain attempt * >= 1,000,000 -} data Context = Context {seenNum::I.IntSet, cycleStart::Int, cycleLength::Int} hasBeenSeen :: Int -> Context -> Bool hasBeenSeen n context = I.member n (seenNum context) markSeen :: Int -> Context -> Context markSeen n context = context { seenNum = (I.insert n (seenNum context)) } deleteFromSeen :: Int -> Context -> Context deleteFromSeen n context = context { seenNum = (I.delete n (seenNum context)) } {- - Examines the context to see if the input has potential to be a chain or not - based on whether the input number has been visited before. If it could be a - chain, an attempt is made to build the chain. -} checkForChain :: Context -> Int -> Context checkForChain context n = if hasBeenSeen n context then deleteFromSeen n context else buildChain context (sum $ divisors n) n [n] {- - Builds a chain until ones of the 3 stopping conditions are met or a chain is - found. If a chain is found the context will be updated with the new chain if - it is the longest. - - Stopping Conditions: - * Number has already been seen before - * Number is less than the start of this chain attempt - * Number >= 1,000,000 -} buildChain :: Context -> Int -> Int -> [Int] -> Context buildChain context candidate first cycleList = if elem candidate cycleList then foundChain (takeUntil ((==) candidate) cycleList) context else if candidate < first || candidate >= 1000000 || hasBeenSeen candidate context then context else buildChain (markSeen candidate context) (sum $ divisors candidate) first (candidate : cycleList) {- - Updates the context with the new longest chain and the start value if the - chain input parameter is longer than the one currently in the context. -} foundChain :: [Int] -> Context -> Context foundChain ls context = let l = length ls m = minimum ls in if l > (cycleLength context) then context { cycleLength = l, cycleStart = m } else if l == (cycleLength context) then let m = minimum ls in if m < (cycleStart context) then context { cycleStart = m } else context else context --- END Main.hs --- I put a bunch of common functions in ProjectEuler.hs. Here are the relevant functions for this problem: {- - Gets all of the proper divisors of a number. That is all divisors starting - from 1, but not including itself. -} divisors :: (Integral a) => a -> [a] divisors n = let p1 = [x | x <- [1 .. floor $ sqrt $ fromIntegral n], n `mod` x == 0] p2 = map (div n) (tail p1) in p1 `concatNoDupe` (reverse p2) where {- - Concatenate two lists. If the last element in the first list and the - first element in the second list are ==, produce only the value from - the first list in the output. -} concatNoDupe :: (Eq a) => [a] -> [a] -> [a] concatNoDupe [] ys = ys concatNoDupe [x] (y:ys) = if x == y then (y : ys) else (x : y : ys) concatNoDupe (x:xs) ys = x : (concatNoDupe xs ys) {- - Similar to takeWhile, but also takes the first element that fails the - predicate. -} takeUntil :: (a -> Bool) -> [a] -> [a] takeUntil pred (x:xs) = (x : if pred x then [] else takeUntil pred xs) takeUntil _ [] = []

6 8

defining mapPairs function
by Alexteslin 01 Sep '07

01 Sep '07

Hello, I just came across with this question on the exam and can not think of implementing it. mapPair :: (a -> a -> a) -> [a] -> [a] such that mapPairs f [x1, x2, x3, x4...] = [f x1 x2, f x3 x4,...] and if the list contains an odd number of elements, the last one is kept unchanged, for example mapPairs f [x1, x2, x3] = [f x1 x2, x3] Any ideas will be appreciated, thanks -- View this message in context: http://www.nabble.com/defining-mapPairs-function-tf4350356.html#a12395628 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

7 11

GHC 6.6.1 binary package for Ubuntu available?
by Sukit Tretriluxana 01 Sep '07

01 Sep '07

Hi, I am wondering if there is the binary package for GHC 6.6.1 for Ubuntu. I searched in the package manager and I only see the version 6.6. Thanks, Ed

3 4

Re: trouble compiling regex posix head (I think >0.92) on ghc 6.7
by Thomas Hartman 31 Aug '07

31 Aug '07

I darcs pulled cabal head to get latest cabal, removed -Werror from GHC-Options in the cabal file, removed HsRegexPosixConfig.h and tried again with the same result. It seems to really want that file. With, it installs, without, no install. $ darcs whatsnew { hunk ./regex-posix.cabal 16 -Build-Depends: regex-base >= 0.80, base >= 2.0 +Build-Depends: regex-base >= 0.80, base >= 2.0, array, containers, byt estring hunk ./regex-posix.cabal 32 -GHC-Options: -Wall -Werror -O2 +GHC-Options: -Wall -O2 hunk ./regex-posix.cabal 43 -Include-Dirs: include +Include-Dirs: include/regex } Chris Kuklewicz <haskell(a)list.mightyreason.com> 08/30/2007 12:34 PM To Thomas Hartman/ext/dbcom@DBAmericas cc haskell-cafe(a)haskell.org, "cvs-ghc(a)haskell.org" <cvs-ghc(a)haskell.org> Subject Re: trouble compiling regex posix head (I think >0.92) on ghc 6.7 Thomas Hartman wrote: > > I'm trying to compile regex-posix on ghc 6.7. (Ultimate goal: happs on > 6.7). I have not explored ghc 6.7. You should also try posting on the <glasgow-haskell-users(a)haskell.org> mailing list. > > First, I patched by changing the cabal file to be compatible with the > new libraries broken out of base. I also had to add HsRegexPosixConfig.h > to include/regex (I just copied it from somewhere else on my hard drive > where I guess it had been put by an earlier regex-posix install, I don't > know if it's compatible here but at least it permitted things to compile > further.) I had no idea what HsRegexPosixConfig was, and I have no such file at all. So I looked in Wrap.hsc and found: > #ifdef HAVE_REGEX_H > #define HAVE_REGCOMP 1 > #else > #ifndef __NHC__ > #include "HsRegexPosixConfig.h" > #else > #define HAVE_REGEX_H 1 > #define HAVE_REGCOMP 1 > #endif > #endif Note that I did not write that section -- that was added by someone else. So HsRegexPosixConfig.h should only matter if HAVE_REGEX_H is undefined. The regex-base.cabal file says: "CC-Options: -DHAVE_REGEX_H" So unless Cabal is having a very very bad day, I assume that HsRegexPosixConfig.h is never needed. That it matters to your build to have that file seems _wrong_ to me. The only header file it should need is "regex.h" > Setup.hs build -v3 had a lot of warnings but didn't seem to fail. > However, Setup.hs install -v3 didn't work. You might try to change the cabal file. Currently I think it is "GHC-Options: -Wall -Werror -O2" and remove -Werror "GHC-Options: -Wall -O2" And you can change the cabal "Include-Dirs" to point to wherever it will find "regex.h" > the problem in build seems to occur around "upsweep partially failed or > main not exported"... That means nothing to me. > > [6 of 6] Compiling Text.Regex.Posix ( Text/Regex/Posix.hs, > dist/build/Text/Regex/Posix.o ) > *** Parser: > *** Renamer/typechecker: > > Text/Regex/Posix.hs:57:2: > Warning: The export item `module Text.Regex.Posix.String' exports > nothing > > Text/Regex/Posix.hs:59:2: > Warning: The export item `module Text.Regex.Posix.Sequence' exports > nothing > > Text/Regex/Posix.hs:61:2: > Warning: The export item `module Text.Regex.Posix.ByteString' > exports nothing > > Text/Regex/Posix.hs:63:2: > Warning: The export item `module Text.Regex.Posix.ByteString.Lazy' > exports nothing Those warning are slightly bogus. Including the module should export the instances. > *** Deleting temp files: > Deleting: /tmp/ghc9618_0/ghc9618_0.s > Warning: deleting non-existent /tmp/ghc9618_0/ghc9618_0.s > Upsweep partially successful. > *** Deleting temp files: > Deleting: > link(batch): upsweep (partially) failed OR > Main.main not exported; not linking. > *** Deleting temp files: > Deleting: > *** Deleting temp dirs: > Deleting: /tmp/ghc9618_0 > > complete output (along with patch) is attached. > > I'd appreciate any advice. > > best, thomas. > > --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

2 1

trying to install gutsy's libghc6-mtl-dev from source on feisty
by Anatoly Yakovenko 31 Aug '07

31 Aug '07

i have ghc6_6.6.1-2ubuntu2_i386.deb and ghc6-prof_6.6.1-2ubuntu2_i386.deb installed, but i cant seem to get mtl to install, can someone tell me what this output means? i just switched to a debian based system from gentoo, so i dont grok dpkg yet: aeyakovenko@snowcrash:~$ sudo dpkg -i libghc6-mtl-dev_1.0.1-2_i386.deb (Reading database ... 129709 files and directories currently installed.) Preparing to replace libghc6-mtl-dev 1.0-3 (using libghc6-mtl-dev_1.0.1-2_i386.deb) ... ghc-pkg: cannot find package mtl-1.0 dpkg: warning - old pre-removal script returned error exit status 1 dpkg - trying script from the new package instead ... ghc-pkg: cannot find package mtl-1.0 dpkg: error processing libghc6-mtl-dev_1.0.1-2_i386.deb (--install): subprocess new pre-removal script returned error exit status 1 Reading package info from stdin ... done. ghc-pkg: dependency base-2.0 doesn't exist (use --force to override) dpkg: error while cleaning up: subprocess post-installation script returned error exit status 1 Errors were encountered while processing: libghc6-mtl-dev_1.0.1-2_i386.deb

2 4

Haskell on the Playstation 3? :-)
by Peter Verswyvelen 30 Aug '07

30 Aug '07

Game developers are really struggling to get performance out of the Playstation 3 console. This console has a single PowerPC CPU with 6 Cell SPU coprocessors, all running at 3.3GHz. These SPUs have 256KB very high speed local RAM, and data from the 512MB main memory can stream in and out via DMA into these SPUs. The problem is that with imperative approaches this is a nightmare to manage.. It would be a very cool project to show that Haskell could run on such a platform, making it easier to take advance of its awesome power J Oh well, I'm just brainstorming here. Cheers, Peter BTW: This Cell platform also seemed to be offered for scientific computing in standard workstation PCs, so it would not just be for the Playstation 3.

10 19

Newbie question: Why gfoldl has this strange type?
by Rodrigo Geraldo 30 Aug '07

30 Aug '07

Hi! I am a novice in Haskell, and particularly I have interested in generic programming. This interest motivated me to read paper Scrap your boilerplate: A practical design pattern for generic programming, but I didn't understand the type of the function gfoldl, that was present in class Term (Data). Somebody could help me to understand the type of this function? Thanks... Rodrigo

2 2

darcs behind firewall
by Sukit Tretriluxana 30 Aug '07

30 Aug '07

Hi all, Does anyone know how to specify proxy server and port for darcs to use when it connects to servers? I am behind firewall most of the time and all requests have to go through a proxy. Thanks, Ed

2 2