December 2008 - Haskell-Cafe

Re: [Haskell] ANN: HLint 1.0
by Hugo Pacheco 20 Dec '08

20 Dec '08

Hi again, I have run HLint against my libraries and found lots of suggestions, mainly excessive brackets. This is what I suggest from my experience: . a suggestion for a rule: dollar eta: f $ x -> f x. some parser errors I encountered: import Data.Generics hiding ((:*:)) type instance Rep Id x = x Cheers, hugo On Sat, Dec 20, 2008 at 10:21 AM, Hugo Pacheco <hpacheco(a)gmail.com> wrote: > I noticed that you convert point-wise into point-free.Perhaps you could > add some point-free transformations to remove redundancy in certain cases. > Is that a goal of the library? > > Cheers, > hugo > > > On Sat, Dec 20, 2008 at 9:55 AM, Neil Mitchell <ndmitchell(a)gmail.com>wrote: > >> Hi, >> >> I am pleased to announce HLint, a tool for making suggestions to >> improve your Haskell code. Previously this tool was called Dr Haskell >> and depended on a working installation of Yhc - both of those have now >> changed. HLint requires GHC 6.10*, and to install simply type: >> >> cabal update && cabal install hlint >> >> If you haven't yet installed the cabal command, instructions are here: >> http://ghcmutterings.wordpress.com/2008/11/10/bootstrapping-cabal-install/ >> >> As an example of what HLint does, running "hlint darcs-2.1.2" over the >> latest stable release of darcs gives 385 suggestions, including: >> >> darcs-2.1.2\src\CommandLine.lhs:46:1: Use a string literal >> Found: >> [' ', '\t', '"', '%'] >> Why not: >> " \t\"%" >> >> darcs-2.1.2\src\CommandLine.lhs:49:1: Eta reduce >> Found: >> quotedArg ftable >> = between (char '"') (char '"') $ quoteContent ftable >> Why not: >> quotedArg = between (char '"') (char '"') . quoteContent >> >> darcs-2.1.2\src\CommandLine.lhs:94:1: Use concatMap >> Found: >> concat $ map escapeC s >> Why not: >> concatMap escapeC s >> >> To see all the hints in a nice interactive document visit >> http://www-users.cs.york.ac.uk/~ndm/hlint/hlint-report.htm >> (recommended if you are thinking of trying out hlint) >> >> All necessary links, including a manual, hackage links, bug tracker >> and source code can be found from the tool website: >> http://www-users.cs.york.ac.uk/~ndm/hlint/ >> >> Acknowledgements: Niklas Broberg and the haskell-src-exts package have >> both been very helpful. The darcs users mailing list gave many good >> suggestions which I've incorportated. >> >> Please direct any follow up conversations to haskell-cafe@ >> >> Thanks >> >> Neil >> >> * Why GHC 6.10? View patterns. >> _______________________________________________ >> Haskell mailing list >> Haskell(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell >> > > > > -- > www.di.uminho.pt/~hpacheco > -- www.di.uminho.pt/~hpacheco

2 1

Re: [reactive] problem with unamb -- doesn't kill enough threads
by Conal Elliott 20 Dec '08

20 Dec '08

(I'm broadening the discussion to include haskell-cafe.) Andy -- What do you mean by "handling all thread forking locally"? - Conal On Thu, Dec 18, 2008 at 1:57 PM, Andy Gill <andygill(a)ku.edu> wrote: > Conal, et. al, > I was looking for exactly this about 6~9 months ago. I got the suggestion > to pose it as a challenge > to the community by Duncan Coutts. What you need is thread groups, where > for a ThreadId, you can send a signal > to all its children, even missing generations if needed. > > I know of no way to fix this at the Haskell level without handling > all thread forking locally. > > Perhaps a ICFP paper about the pending implementation :-) but I'm not sure > about the research content here. > > Again, there is something deep about values with lifetimes. > > Andy Gill > > > On Dec 18, 2008, at 3:43 PM, Conal Elliott wrote: > > I realized in the shower this morning that there's a serious flaw in my > unamb implementation as described in > http://conal.net/blog/posts/functional-concurrency-with-unambiguous-choice. > I'm looking for ideas for fixing the flaw. Here's the code for racing > computations: > > race :: IO a -> IO a -> IO a > a `race` b = do v <- newEmptyMVar > ta <- forkPut a v > tb <- forkPut b v > x <- takeMVar v > killThread ta > killThread tb > return x > > forkPut :: IO a -> MVar a -> IO ThreadId > forkPut act v = forkIO ((act >>= putMVar v) `catch` uhandler `catch` > bhandler) > where > uhandler (ErrorCall "Prelude.undefined") = return () > uhandler err = throw err > bhandler BlockedOnDeadMVar = return () > > The problem is that each of the threads ta and tb may have spawned other > threads, directly or indirectly. When I kill them, they don't get a chance > to kill their sub-threads. > > Perhaps I want some form of garbage collection of threads, perhaps akin to > Henry Baker's paper "The Incremental Garbage Collection of Processes". As > with memory GC, dropping one consumer would sometimes result is cascading > de-allocations. That cascade is missing from my implementation. > > Or maybe there's a simple and dependable manual solution, enhancing the > method above. > > Any ideas? > > - Conal > > > _______________________________________________ > Reactive mailing list > Reactive(a)haskell.org > http://www.haskell.org/mailman/listinfo/reactive > > >

4 6

OT: representations for graphs
by Bayley, Alistair 19 Dec '08

19 Dec '08

(OT, but I'm hoping some of you might have some ideas on this anyway...) I was wondering what alternative representations there are for graphs, or maybe if there might be a way to derive one/some from some insightful observations. For the purposes of storing and exmaining (querying) graphs in an SQL database. For example, a tree (so, a specialised sub-class of graph) can be represented by a three models, that I know of: - adjacency-list (the most common) - materialised-path (a denormalisation of adjacency-list) - nested-sets Nested-sets (and materialised-path) works for trees because the graph is - directed (so we know which nodes are parents or children) - acyclic (there's a definite root, and leaves) - every child has a single parent (so no diamond shapes - does this property have a name?) Nested-sets works well with SQL databases for querying, at the expense of updates. Adjacency-list is easier to update, but some queries suck, or are downright impossible in normal SQL. We can use the adjacency-list model for graphs too, but it has the same query deficiencies as for trees. I'd like some sort of alternative to adjacency-list, like nested-sets, that would work better for querying at the expense of updates. Alistair ***************************************************************** Confidentiality Note: The information contained in this message, and any attachments, may contain confidential and/or privileged material. It is intended solely for the person(s) or entity to which it is addressed. Any review, retransmission, dissemination, or taking of any action in reliance upon this information by persons or entities other than the intended recipient(s) is prohibited. If you received this in error, please contact the sender and delete the material from any computer. *****************************************************************

2 2

Re: [Haskell-cafe] OT: representations for graphs
by Nathan Bloomfield 19 Dec '08

19 Dec '08

(Forgot to send to haskell-cafe- sorry Alistair!) Martin Erwig wrote a paper [1] that defines an inductive graph type and implements some common algorithms with it. Also, it isn't very Haskellish but if you can label your nodes with an instance of Ix you might be able to use an Array to get constant time access. I've never used Data.HashTable before, but that might also be useful. [1] - http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf<http://web.engr.oregonstate.edu/%7Eerwig/papers/InductiveGraphs_JFP01.pdf>

1 0

sort and lazyness (?)
by Daniel Kraft 19 Dec '08

19 Dec '08

Hi, I'm just a beginner trying to learn a little about Haskell, and as such write some toy programs (e.g. for projecteuler.net) in Haskell. Currently, I'm experiencing what I would call "strange behaviour": I've got a data-type data Fraction = Fraction Int Int to hold rational numbers (maybe there's already some built-in type for this in Haskell, much like for instance Scheme has a rational type?), and then I compute a list of pairs of those numbers, that is [(Fraction, Fraction)]. Fraction is declared an instance of Ord. This list has up to 3 million elements. If I do main = print $ length $ points then the program prints out the length fine and takes around 6s to finish (compiled with GHC -O3). Ok, but I acknowledge that length isn't quite an expensive function, as I can imagine that Haskell does not compute and hold the entire list for this but instead each element at once and discards it afterwards. Doing main = print $ length $ map (\(x, _) -> x == Fraction 1 2) points instead, gives a slightly longer runtime (6.6s), but in this case I'm sure that at least each element is computed; right? main = print $ length $ reverse points gives 11.9s, and here I guess (?) that for this to work, the entire list is computed and hold in memory. However, trying to do import List main = print $ length $ sort points makes memory usage go up and the program does not finish in 15m, also spending most time waiting for swapped out memory. What am I doing wrong, why is sort this expensive in this case? I would assume that computing and holding the whole list does not take too much memory, given its size and data type; doing the very same calculation in C should be straight forward. And sort should be O(n * log n) for time and also not much more expensive in memory, right? Am I running into a problem with lazyness? What can I do to avoid it? As far as I see it though, the reverse or map call above should do nearly the same as sort, except maybe that the list needs to be stored in memory as a whole and sort has an additional *log n factor, but neither of those should matter. What's the problem here? Is this something known with sort or similar functions? I couldn't find anything useful on Google, though. My code is below, and while I would of course welcome critics, I do not want to persuade anyone to read through it. Thanks a lot, Daniel ---------------------------------------------------------- -- Problem 165: Intersections of lines. import List -- The random number generator. seeds :: [Integer] seeds = 290797 : [ mod (x * x) 50515093 | x <- seeds ] numbers :: [Int] numbers = map fromInteger (map (\x -> mod x 500) (tail seeds)) -- Line segments, vectors and fractions. data Segment = Segment Int Int Int Int data Vector = Vector Int Int data Fraction = Fraction Int Int instance Eq Fraction where (Fraction a b) == (Fraction c d) = (a == c && b == d) instance Ord Fraction where compare (Fraction a b) (Fraction c d) | (a == c && b == d) = EQ | b > 0 = if a * d < b * c then LT else GT | otherwise = if a * d > b * c then LT else GT -- Build a normalized fraction and get its value. normalize (Fraction a b) = let g = gcd a b; aa = div a g; bb = div b g in if bb < 0 then Fraction (-aa) (-bb) else Fraction aa bb -- Find the inner product of two vectors. innerProduct (Vector a b) (Vector c d) = a * c + b * d -- Find the normal vector and direction of a line segment, as well as -- the constant in straight-normal form for a given normal vector. normalVector (Segment x1 y1 x2 y2) = Vector (y1 - y2) (x2 - x1) direction (Segment x1 y1 x2 y2) = Vector (x2 - x1) (y2 - y1) nfConstant (Segment x1 y1 x2 y2) n = innerProduct n (Vector x1 y1) -- Check if a point is between the ends of the segment times D. betweenEndsTimes d (Segment x1 y1 x2 y2) xD yD = let x1D = x1 * d; x2D = x2 * d; y1D = y1 * d; y2D = y2 * d; xDMin = min x1D x2D; xDMax = max x1D x2D; yDMin = min y1D y2D; yDMax = max y1D y2D in (xDMin <= xD && xDMax >= xD && yDMin <= yD && yDMax >= yD && (x1D /= xD || y1D /= yD) && (x2D /= xD || y2D /= yD)) -- If they are not parallel, we can find their intersection point (at least, -- the one it would be if both were straights). Then it is easy to check if -- it is between the endpoints for both. -- -- n1 * x + m1 * y = c1 -- n2 * x + m2 * y = c2 -- -- => x = (c1 * m2 - x2 * m1) / (n1 * m2 - n2 * m1) -- => y = (n1 * c2 - n2 * c1) / (n1 * m2 - n2 * m1) -- -- (Iff they are parallel, the determinant will be 0.) trueIntersect s1 s2 = let (Vector n1 m1) = normalVector s1; (Vector n2 m2) = normalVector s2; c1 = nfConstant s1 (Vector n1 m1); c2 = nfConstant s2 (Vector n2 m2); d = n1 * m2 - n2 * m1; xD = c1 * m2 - c2 * m1; yD = n1 * c2 - n2 * c1 in if d == 0 then Nothing else if (betweenEndsTimes d s1 xD yD) && (betweenEndsTimes d s2 xD yD) then Just ((normalize $ Fraction xD d), (normalize $ Fraction yD d)) else Nothing -- Build list of segments. takeEveryForth :: [Int] -> [Int] takeEveryForth (a:_:_:_:t) = a : (takeEveryForth t) n1 = numbers n2 = tail n1 n3 = tail n2 n4 = tail n3 segments = [ Segment a b c d | ((a, b), (c, d)) <- zip (zip (takeEveryForth n1) (takeEveryForth n2)) (zip (takeEveryForth n3) (takeEveryForth n4)) ] -- For the first 5000 segments, calculate intersections. firstSegments = take 5000 segments intersects :: [Maybe (Fraction, Fraction)] intersects = findInters firstSegments [] where findInters [] l = l findInters (h:t) l = findInters t (addInters h t l) where addInters _ [] l = l addInters e (h:t) l = addInters e t ((trueIntersect e h) : l) getPoints :: [Maybe (Fraction, Fraction)] -> [(Fraction, Fraction)] getPoints [] = [] getPoints (Nothing : t) = getPoints t getPoints ((Just v) : t) = v : (getPoints t) points = getPoints intersects -- Main program. main :: IO () main = print $ length $ reverse points --main = print $ length $ map (\(x, _) -> x == Fraction 1 2) points --main = print $ length $ sort points

6 13

Fwd: [Haskell-cafe] Haskell as a religion
by Alberto G. Corona 19 Dec '08

19 Dec '08

But many features need other features. For example, the option to use referential transparency will be common in future languages for multicore programming purposes. This creates the problem of separating side-effect-free code from side-effect code. For this purpose, a strong type system at compile time is needed, which indeed need automatic type inference or, else, the user will be too busy with the details. The type inference open the door for experimenting with complex data types. class types is a logical step after that. Monads are the best option for many problems once the programmer have all te above. higuer order functions are being taken seriously in other languages. this goes to the need of currying and lists. optional lazyness and tail recursion is the most elegant option for expressing lists managing code. Will all the above, explicit loops will be avoided by the programmer, this will end up in mode declarative programming style. I think that once the average programmer start to use one or two of these features, he will feel a bit frustrated if its language don´t have all the others, specially if he know haskell. Probably, he will use haskell for fun. This is the best way for the takeover of the industry, because this has been so historically. 2008/12/18 John Goerzen <jgoerzen(a)complete.org> Andrew Coppin wrote: > > Don Stewart wrote: > >> I think of Haskell more as a revolutionary movement > > > > LOL! Longest revolution EVER, eh? I mean, how long ago was its dogma > > first codified? ;-) > > Lisp has been around for how long now? Measured in decades. We don't > even have our version of a Symbolics machine yet! > > > Basically, Haskell will never be popular, but its coolest ideas will be > > stolen by everybody else and passed off as their own. :-( > > Well, in a sense, if that happens, we would have won, right? We'd have > created a situation where "paradigm shift" would mean more than just a > buzzword on some CEO's presentation slide ;-) > > In another sense, isn't this what Haskell was explicitly created to do? > (Combine ideas from a bunch of similar languages into one standard one) > > Some ideas in Haskell are easy to integrate into other languages: see > list comprehensions in Python. I don't see Perl picking up pervasive > laziness anytime soon, nor Python compile-time type inference. > > -- John > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

6 5

Automatic instance constraints derivation: how?
by Dimitry Golubovsky 19 Dec '08

19 Dec '08

Hi, I am trying to understand, why do I need to place constraints with class instance declaration while all the information seems to be already available to the compiler. I have placed the code in question here: http://codepad.org/Akew0p2t so anybody can play with it. The code tries to model evaluation of GRIN-style thunks using Haskell type classes instead of tag-based pattern matching, as in the GRIN papers. That is, a thunk is represented as a datatype like data Ffun a b c = Ffun a b c, and there is some "eval" function which being applied to such data results in the call fun a b c. Such "eval" function is a method of class Eval: class Eval a b | a -> b where eval :: (Monad m) => a -> m b which means that thunks of some type (a) evaluate to values of some dependent type (b). The code is monadic because GRIN is a monad, so the code looks similar to GRIN. The ultimate goal is to make GRIN code understandable by Haskell compiler. Everything is fine with "simple" types like Int, that is "instance Eval Int Int" means that Int (and Char, and Bool) do not need in fact evaluation at all. instance Eval Int Int where eval = return Everything is fine with thunks encoding calls to primitives. See instances for FADD and FSUB. All type information for primitives (primPlusInt, primMinusInt) is specified in the code. Then, a function "fun" is defined that calls the primitives. The "main" function illustrates its use, and everything works as expected, as output shows. But when I tried to define a thunk for "fun" (instance for Ffun) I was only able to do that with all constraints on its parameters explicitly set. OTOH, even if I comment out the instance Eval for Ffun, and load the code in Hugs (or GHCi, doesn't matter) then type signature of "fun" is correctly derived by the compiler. If I try to define instance for Ffun like this: instance (Eval x x) => Eval (Ffun a b c) x where eval (Ffun a b c) = fun a b c meaning only the fact that result of the function "fun" will be like Int or Bool - evaluates to itself, and we don't care about the types of arguments, I cannot use forall x. with instance declaration, so I have to say something about x. I get the error (Hugs): Error occurred ERROR line 51 - Instance is more general than a dependency allows *** Instance : Eval (Ffun a b c) d *** For class : Eval a b *** Under dependency : a -> b So, is there a way to define such an instance for a thunk without any constraints? Wouldn't it be reasonable to expect that eval (Ffun a b c) = fun a b c would allow the compiler to retrieve constraints on a, b, c from those already known for the called function? Thanks. -- Dimitry Golubovsky Anywhere on the Web

1 0

Fwd: Fwd: [Haskell-cafe] Haskell as a religion
by Alberto G. Corona 19 Dec '08

19 Dec '08

---------- Forwarded message ---------- From: Alberto G. Corona <agocorona(a)gmail.com> Date: 2008/12/19 Subject: Re: Fwd: [Haskell-cafe] Haskell as a religion To: Dan Piponi <dpiponi(a)gmail.com> As far as I know, const only protect from updates that the compiler can detect at compilation time. Moreover, the C/C++ code does not make use of true referential transparency properties, for example const a=1; const b=a perform a copy of content of a to b . In haskell a=1; b=a make b to point to a directly. 2008/12/19 Dan Piponi <dpiponi(a)gmail.com> On Thu, Dec 18, 2008 at 4:15 PM, Henning Thielemann > <schlepptop(a)henning-thielemann.de> wrote: > > > In C/C++ referential transparent functions code can be declared by > > appending a 'const' to the prototype, right? > > For one thing, some fields in a const C++ object can be explicitly set > mutable. mutable is sometimes used in C++ a similar way to > unsafePerformIO in Haskell. You have something that uses mutability in > its internals but that mutability shouldn't be observable to the > caller. In both cases you have no means of actually ensuring that the > mutability is actually unobservable. > -- > Dan >

1 0

Thread scheduling and GHC.Conc
by Jake Foell 19 Dec '08

19 Dec '08

using ghc v6.8.2 Problem: I am creating a program that forks two other lightweight threads. One of the forked threads seems to be stuck or dead after running successfully for a non-trivial amount of time. I am receiving no error messages. Questions: What is the best way to diagnose this problem? (perhaps a ghc upgrade to a version that includes processStatus?) Does the runtime system ensure that no thread will starve for processor time? My initial diagnosis: by looking at log files that this program produces, it seems that the thread in question is failing while receiving a response from a server. Here is a simplified exerpt: h <- connectTo server port appendFile file "Connection Established\n" hPutStr h httpRequestString hFlush h reply <- hGetContents h appendFile file reply If I look at the tail of file that is created, I see something similar to this: ... Connection Established here is the response... Connection Established Answers to my questions and/or any advice would be appreciated. thanks

3 2

lengthOP rewrite rules
by Cetin Sert 19 Dec '08

19 Dec '08

Hi *^o^*, With the following rewrite rules: lengthOP :: (Num a, Ord a) ⇒ Bool → (a → a → Bool) → [b] → a → Bool lengthOP v (⊜) [] n = 0 ⊜ n lengthOP v (⊜) xxs n = co xxs 0 where co [] c = c ⊜ n co (_:xs) c | n > c = co xs (c+1) | otherwise = v lenEQ = lengthOP False (==) lenLT = lengthOP False (<) lenLE = lengthOP False (<=) lenGT = lengthOP True (>) lenGE = lengthOP True (>=) {-# RULES -- | length "lenEQ_LHS" forall xs n. (length xs) == n = lenEQ xs n "lenLT_LHS" forall xs n. (length xs) < n = lenLT xs n "lenLE_LHS" forall xs n. (length xs) <= n = lenLE xs n "lenGT_LHS" forall xs n. (length xs) > n = lenGT xs n "lenGE_LHS" forall xs n. (length xs) >= n = lenGE xs n "lenEQ_RHS" forall xs n. n == (length xs) = lenEQ xs n "lenLT_RHS" forall xs n. n < (length xs) = lenGE xs n "lenLE_RHS" forall xs n. n <= (length xs) = lenGT xs n "lenGT_RHS" forall xs n. n > (length xs) = lenLE xs n "lenGE_RHS" forall xs n. n >= (length xs) = lenLT xs n -- | genericLength "glenEQ_LHS" forall xs n. (genericLength xs) == n = lenEQ xs n "glenLT_LHS" forall xs n. (genericLength xs) < n = lenLT xs n "glenLE_LHS" forall xs n. (genericLength xs) <= n = lenLE xs n "glenGT_LHS" forall xs n. (genericLength xs) > n = lenGT xs n "glenGE_LHS" forall xs n. (genericLength xs) >= n = lenGE xs n "glenEQ_RHS" forall xs n. n == (genericLength xs) = lenEQ xs n "glenLT_RHS" forall xs n. n < (genericLength xs) = lenGE xs n "glenLE_RHS" forall xs n. n <= (genericLength xs) = lenGT xs n "glenGT_RHS" forall xs n. n > (genericLength xs) = lenLE xs n "glenGE_RHS" forall xs n. n >= (genericLength xs) = lenLT xs n #-} 1) Is there a way to tell where 'length' is mentioned, what is meant is for example 'Prelude.length' or any length that works on lists? 2) How can I avoid the following error messages? module Main where import Data.List main :: IO Int print $ length (repeat 0) > 200 print $ 200 < length (repeat 0) print $ genericLength (repeat 0) > 200 -- error print $ 200 < genericLength (repeat 0) -- error return 0 ########: Could not deduce (Ord i) from the context (Eq i, Num i) arising from a use of `lenEQ' at ######## Possible fix: add (Ord i) to the context of the RULE "glenEQ_LHS" In the expression: lenEQ xs n When checking the transformation rule "glenEQ_LHS" ########: Could not deduce (Ord a) from the context (Eq a, Num a) arising from a use of `lenEQ' at ######## Possible fix: add (Ord a) to the context of the RULE "glenEQ_RHS" In the expression: lenEQ xs n When checking the transformation rule "glenEQ_RHS" 3) What speaks for/against broad usage of such rewrite rules involving list lengths? Best Regards, Cetin Sert

5 7