September 2007 - Haskell-Cafe

Bi-directional Maps
by Andrew Wagner 03 Sep '07

03 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

GHC-API: a few questions
by Andrea Rossato 02 Sep '07

02 Sep '07

Hi, I'm trying to acquire some confidence with the GHC-API and I'm having some problems, related to error handling, I seem not be able to solve. Basically there are 3 functions to (interactively) compile/run Haskell expressions: compileExpr, dyCompileExpr and runStmt. The first 2 will return the value of the compiled expression, as a Maybe HValue the first, and a Maybe Dynamic the second, while the third can bind names and report them, or report exceptions. But my problem is related to the first two. I run expressions (string_expression) wrapped around some let x = string_expression in take 2048 (show x) to avoid infinite list or loops. According to the documentation one should be able to control how error messages are dealt with, by manipulation the GHC session's state. One component of the session state, indeed, is the log_action which, by default, prints errors and warnings to the standard error (compiler/main/DynFlags.hs). Now, no matter what I do, I seem not to be able to change the log_action to collect error messages and warnings. In any case everything seem to be printed to standard error. This way I can only collect exceptions raised by the compiler. For instance: "Prelude.last: empty list" for string_expression = "last []" But if my expression raises a type error, this is printed to stderr. Like in the case of string_expression = "last" which would produce a "No instance for (Show ([a] -> a))" What am I doing wrong? Thanks for your kind attentions. Andrea ps: there are quite a lot of other questions I'd like to ask about some programming techniques I've seen applied in GHC. For instance, sometime a list of actions is given as a string, to be compiled to a HValue which is written to a IORef. Running those actions is just a matter of reading the IORef (you can see this in compiler/ghci/InteractiveUIhs, when it comes to buffer management. For instance: flushInterpBuffers). I ask to myself: Why? Just to amaze the reader? ;-)

1 1

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

Array.Diff, strange oversight or myopia ?
by Chaddaï Fouché 02 Sep '07

02 Sep '07

Data.Array.Diff don't have an instance for DiffUArray Bool, which is strange by itself since IOUArray Bool exists and it's the only IOUArray that is not mirrored in Diff. But ok, why not, I guess it might be a small oversight, so I go on to create the missing instance IArray (IOToDiffArray IOUArray) Bool on the model of the instances in the source of Array.Diff. Ok, Diff exports readDiffArray, newDiffArray and replaceDiffArray for this exact purpose, seems it will be straightforward... except that boundsDiffArray is not exported and you can't rewrite it since it needs to take apart the DiffArrayData type which is not exported either ! So how can I do this (short of copying and renaming an alternative Array.Diff or changing the library in my installation of GHC) ? And is there something obvious I missed due to a sudden case of myopia ? -- Jedaï

1 0

Re: [Haskell-cafe] Learn Prolog...
by Peter Verswyvelen 02 Sep '07

02 Sep '07

3 2

HApps API Documentation?
by James Britt 02 Sep '07

02 Sep '07

Are there alternative sites for HAppS API docs? There are two links on http://happs.org/#documentation but both give "File not found!" messages. Thanks, James

3 4

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

Data.Unique not "safe" in concurrent environments (or brain burned)?
by Neil Davies 01 Sep '07

01 Sep '07

Hi, I was looking over the libraries for bits of GHC (no doubt a standard form of relaxation for readers of this list), and noticed the following statement (in Data.Unique): -- | Creates a new object of type 'Unique'. The value returned will -- not compare equal to any other value of type 'Unique' returned by -- previous calls to 'newUnique'. This set me thinking - so I looked at the code newUnique :: IO Unique newUnique = do val <- takeMVar uniqSource let next = val+1 putMVar uniqSource next return (Unique next) In the concurrent execution world in which we live - I don't think that the implementation supports the "uniqueness" statement above - or am I not understanding something? Cheers Neil

1 1

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