- Haskell-Cafe - Haskell.org

I hate constructing strings with ++
by Thomas Hartman 20 Dec '08

20 Dec '08

I hate constructing strings with ++. Especially icky when you start dealing with escape characters and stuff. cabal install HStringTemplateHelpers ..... import Text.StringTemplate.Helpers putStrLn $ render1 [("name",name)] "Why, hello, $name$" just thinkin out loud :) (originally at http://www.reddit.com/r/programming/comments/7khkd/the_fun_of_programming_a…)

2 2

"non-functions like unsafePerformIO are not technically part of the haskell language!"
by Jason Dusek 20 Dec '08

20 Dec '08

From an old thread: > non-functions like unsafePerformIO are not technically part > of the haskell language! How is this true, exactly? -- _jsn |...an old thread.| http://www.nabble.com/Re%3A-Re%3A-Parsers-are-monadic--p11390440.html

4 4

Re: [Haskell] ANN: HLint 1.0
by Gwern Branwen 20 Dec '08

20 Dec '08

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 On Sat, Dec 20, 2008 at 4:55 AM, Neil Mitchell 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. Hi, Neil. Thanks for the tool; it found some worthwhile changes in my projects. But a few points: 1) How does one actually use the CLI tool? You didn't say. It *seems* that one just feeds it a list of random filepaths, so on Mueval, say, the command would be 'hlint main.hs Mueval/*.hs' (and not, say, 'hlint mueval.cabal'). But I'm not actually sure. 2) I think I found a parsing bug. One line in Mueval/Interpreter.hs runs: > fmap (take n exceptionMsg ++) $ render' (n-length exceptionMsg) s which gives the error: > Mueval/Interpreter.hs:145:59: Parse failure, Parse error > No relevant suggestions Adding spaces between 'n' and 'length', so it reads: > fmap (take n exceptionMsg ++) $ render' (n - length exceptionMsg) s lets hlint parse and suggest for it. - -- gwern -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEAREKAAYFAklM+kwACgkQvpDo5Pfl1oKDhwCfRgQutbvr9QbKvbLJlbhdla2Z absAniWC+ksXHhfbunsdOsnmG69lppFZ =X9uv -----END PGP SIGNATURE-----

2 1

Re: [Haskell] ANN: HLint 1.0
by Neil Mitchell 20 Dec '08

20 Dec '08

Hi > 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? It does some transformations of th at nature, but the idea isn't to remove redundancy, its to make the code clearer. Do you have any suggestions for things it could easily do to remove redundancy? It already does a few relating to if expressions. > a suggestion for a rule: dollar eta: f $ x -> f x That can easily be added. > Why not: > ("TAG " `isPrefixOf` just_name pinfo) That's an open bug: http://code.google.com/p/ndmitchell/issues/detail?id=109 In general, most of the hints are "replace this with this" - evaluating the new bit (even to remove easy constants) is beyond it for the moment. Some people theorised it might be too hard, non-terminating, or incorrect. As it happens this rule only fires when "TAG " is either a string literal or a list literal, and when the number is a constant, so its always safe and the guard could always be eliminated. > 1) How does one actually use the CLI tool? You didn't say. It *seems* > that one just feeds it a list of random filepaths, so on Mueval, say, > the command would be 'hlint main.hs Mueval/*.hs' (and not, say, 'hlint > mueval.cabal'). But I'm not actually sure. The filenames are either filenames, or directories which are recursively searched, i.e cd mueval && hlint . is probably sufficient. I should document it more clearly in the manual. Thanks Neil

2 1

Re: [Haskell] ANN: HLint 1.0
by Martijn van Steenbergen 20 Dec '08

20 Dec '08

Hi Neil, This is awesome, thank you. :-) It found a 'use liftM', 'use on' and three eta-reduces in Yogurt. It seems like the line numbers could be a bit more accurate: ./Network/Yogurt/IO.hs:54:3: Use liftM Found: rec >>= return . (c :) Why not: liftM (c :) rec Where the code is: 50 -- Waits for input, but once the first character is read, waits 51 -- no longer than the specified number of ms before giving up. 52 hGetImpatientLine :: Handle -> Int -> IO String 53 hGetImpatientLine h patience = rec where 54 rec = do 55 c <- hGetChar h 56 if c == '\n' 57 then return [c] 58 else do 59 b <- hWaitForInput h patience 60 if b 61 then rec >>= return . (c:) 62 else return [c] I imagine it could have told me to look at line 61 right away. Thanks, Martijn.

4 4

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