Re: [Haskell-cafe] Package documentation complaints -- and a suggestion
The problem isn't social pressure to be stable, it's the ambiguity of what stable means. If Hackage 2 institutes a policy whereby things claiming to be stable are treated better, then stable is likely to become the new experimental. I'd say, rather than rely on social agreement on what terms mean, let's just collect lots of automated metrics, and present them as extra information on the hackage pages. At work, we have all modules scored by hlint metrics, and doclint metrics. (Doclint complains about modules without a module header comment, and type signatures without haddock comments.) We count infractions and have a top ten hall-of-shame, as well as placing the scores in the module documentation itself. We also have a fingerprint for every release (basically the API type signatures), and the size of fingerprint-diffs between releases is a rough measure of API-churn. Some of these measures are designed to place social pressure on authors to improve their code/documentation, but they have a dual role in allowing users to get a feel for the quality of the code they are using, without imposing any external hierarchy on which metrics are more important in any given situation. Regards, Malcolm ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: Monad.Reader Issue 19
On Wed, Oct 26, 2011 at 03:17:47PM -0400, Brent Yorgey wrote: I am pleased to announce that Issue 19 of The Monad.Reader, a special issue on parallelism and concurrency, is now available: http://themonadreader.files.wordpress.com/2011/10/issue19.pdf Thanks a lot for the TMR, it's a pleasure to read, as always. If like me there are people who (would like to) read this on an ebook reader, these are the changes that finally give me good results on a Sony Reader: \usepackage[papersize={90mm,120mm},margin=2mm]{geometry} \usepackage[kerning=true]{microtype} \usepackage[T1]{fontenc} \usepackage[charter]{mathdesign} \usepackage{hyperref} \hypersetup{pdftitle={The Monad Reader 19}} \sloppy Additionally, all the \includegraphics commands need changing from absolute measurements (e.g. width=6cm) to something relative; in my case, I just used \textwidth. And finally, the verbatim sections need a bit smaller font, as they can't be reflowed nicely; or alternatively, inserting manual line wraps (keeping the code consistent). regards, iustin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MonadPlus versus Alternative
On Sun, Oct 30, 2011 at 04:02, Gregory Crosswhite wrote: So is there any difference between the interpretation of MonadPlus and Alternative, or is the only difference between them that the former applies to Monad whereas the latter applies to Applicative? Somewhat OT, but this led me to playing with ConstraintKinds: https://github.com/spl/sandbox/blob/master/ConstraintKindsAlternativeMonadPlus.lhs Regards, Sean ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lazy A-star search
I'm misunderstanding astar. I've thought that 'whole route'-heuristic will prevent algorithm from going in circles. The more you circle around the more the whole route distance is. Thank you for showing this. Here is an updated version. searchBy function contains a state. State value accumulates visited nodes: -- | Heuristic search. Nodes are visited from smaller to greater. searchBy :: Ord b = (a - b) - (a - a - Ordering) - Tree a - [a] searchBy f heur t = evalState (searchBy' f heur t) S.empty searchBy' :: Ord b = (a - b) - (a - a - Ordering) - Tree a - State (S.Set b) [a] searchBy' f heur (Node v ts) = get = phi where phi visited | S.member (f v) visited = return [] | otherwise = put (S.insert (f v) visited) (v :) . foldr (mergeBy heur) [] $ mapM (searchBy' f heur) ts I need to add function Ord b = (a - b). It converts tree nodes into visited nodes. I'm using it for saving distance-values alongside with nodes in astar algorithm. In attachment you can find algorithm with your example. 2011/10/27 Ryan Ingram ryani.s...@gmail.com Also, this wasn't clear in my message, but the edges in the graph only go one way; towards the top/right; otherwise the best path is ABCDEHIJ :) On Thu, Oct 27, 2011 at 10:48 AM, Ryan Ingram ryani.s...@gmail.comwrote: You're missing one of the key insights from A-star (and simple djikstra, for that matter): once you visit a node, you don't have to visit it again. Consider a 5x2 2d graph with these edge costs: B 1 C 1 D 1 E 9 J 1 1 1 1 1 A 2 F 2 G 2 H 2 I with the start node being A, the target node being J, and the heuristic being manhattan distance. Your search will always try to take the top route, on every node along the bottom path, even though you visit every node along the top route in your first try at reaching the goal. You need a way to mark that a node is visited and remove it from future consideration, or else you're wasting work. A-star will visit the nodes in the order ABCDE FGHIJ; your algorithm visits the nodes in the order ABCDE FCDE GDE HE IJ. -- ryan On Sat, Oct 22, 2011 at 5:28 AM, Anton Kholomiov anton.kholom...@gmail.com wrote: Recently I was looking for an A-star search algorithm. I've found a package but I couldn't understand the code. Then I saw some blogposts but they were difficult to understand too. I thought about some easier solution that relies on laziness. And I've come to this: Heuristic search is like depth-first search but solutions in sub-trees are concatenated with mergeBy function, that concatenates two list by specific order: module Search where import Control.Applicative import Data.Function(on) import Control.Arrow(second) import Data.Tree -- | Heuristic search. Nodes are visited from smaller to greater. searchBy :: (a - a - Ordering) - Tree a - [a] searchBy heur (Node v ts) = v : foldr (mergeBy heur) [] (searchBy heur $ ts) -- | Merge two lists. Elements concatenated in specified order. mergeBy :: (a - a - Ordering) - [a] - [a] - [a] mergeBy _ a [] = a mergeBy _ []b = b mergeBy p (a:as)(b:bs) | a `p` b == LT= a : mergeBy p as (b:bs) | otherwise = b : mergeBy p bs (a:as) Now we can define specific heuristic search in terms of searchBy: -- | Heuristic is distance to goal. bestFirst :: Ord h = (a - h) - (a - [a]) - a - [a] bestFirst dist alts = searchBy (compare `on` dist) . unfoldTree (\a - (a, alts a)) -- | A-star search. -- Heuristic is estimated length of whole path. astar :: (Ord h, Num h) = (a - h) - (a - [(a, h)]) - a - [a] astar dist alts s0 = fmap fst $ searchBy (compare `on` astarDist) $ unfoldTree gen (s0, 0) where astarDist (a, d) = dist a + d gen (a, d) = d `seq` ((a, d), second (+d) $ alts a) I'm wondering is it effective enough? Anton ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Search.hs Description: Binary data ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] ANN: Haskell OpenGL package updates
The biggest problem with the RULES based approach is that if you are in a context where the RULES don't or can't fire, then your semantics silently change. This leads to subtle bugs which only show up in ghci, etc. On Friday, October 28, 2011, Jason Dagit dag...@gmail.com wrote: On Fri, Oct 28, 2011 at 2:07 PM, Edward Kmett ekm...@gmail.com wrote: Jason, Thank you for taking ownership of HOpenGL! Thanks! I would like to make a formal request for there to be some way to get access to either Graphics.Rendering.OpenGL.Raw.Core31.TypesInternal or that Graphics.Rendering.OpenGL.Raw.Core31.Types re-export the newtype wrappers it places around CDouble and CFloat. As things stand the only way to work with them is to pointlessly round-trip through rational or pray that GHC is smart enough to automatically convert once it sees through the newtype, which it isn't, potentially costing me orders of magnitude of performance in tight loops in exchange for implementation freedom the current OpenGL bindings do not use on any platform. Yes, it's a real problem. I think there are a couple directions we could move in (and some may not even be mutually exclusive). Andy Gill created this workaround: {-# RULES realToFrac/a-GLfloat realToFrac = \x - GLfloat (realToFrac x) #-} {-# RULES realToFrac/GLfloat-a realToFrac = \(GLfloat x) - realToFrac x #-} That one helps a lot for most people. Someone made a libraries proposal that also helps the conversion situation but I don't have the details handy at the moment. If you read here, I'd like to get some MArray support in and I think it's possible, although I haven't the idea I proposed yet: http://www.haskell.org/pipermail/haskell-cafe/2011-March/090511.html Another thing we could do is find a different balance between newtypes and the C types. I'm totally onboard with exposing all of OpenGLRaw. I think we just need to sufficiently document the internal bits so that only people who absolutely need them will use them. That's how I see ByteString and it seems to be working there. Thanks for your suggestion (and your pull request on github, yay for collaborative tools!). Jason ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] control-c only caught once -- bug?
Quoth Brian Johnson brianjohnsonhaskellc...@gmail.com, ... On further thought, there is something sensible here: the RTS might crash while trying to exit. I propose, for POSIX environments, the following change to SIGINT handling: * SIGINT is transformed into UserInterrupt during normal program execution * Once the RTS is committed to exiting, it resets the signal handler for SIGINT so that any additional control-c causes an immediate exit The picture I get from the commentary (below) is that we're talking about shutting down, one way or another - either gracefully, or if that isn't making satisfactory progress, abruptly on the second ^C. Because the user entered a keyboard interrupt, and the program hasn't installed a signal handler for it. If you have your own shutdown procedure that you want to have happen at that time, then it would make sense to me to catch this exception for that purpose. If you want to handle keyboard interrupts, throughout the lifetime of the program process, then you should handle the signals. If the SIGINT handler described below is too confusing, then I would solve that problem by simply removing it. Programs written in other languages simply abort on unhandled signals, and I'm a little skeptical that there's any reliable way to improve on that. We're just teaching people to press ctrlC twice if it's a Haskell program. Donn From http://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Signals: When the interrupt signal is received, the default behaviour of the runtime is to attempt to shut down the Haskell program gracefully. It does this by calling interruptStgRts() in rts/Schedule.chttp://hackage.haskell.org/trac/ghc/browser/rts/Schedule.c (see Commentary/Rts/Scheduler#ShuttingDownhttp://hackage.haskell.org/trac/ghc/wiki/Commentary/Rts/Scheduler#ShuttingDown). If a second interrupt signal is received, then we terminate the process immediately; this is just in case the normal shutdown procedure failed or hung for some reason, the user is always able to stop the process with two control-C keystrokes ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] MonadPlus versus Alternative
On 10/29/11 11:02 PM, Gregory Crosswhite wrote: Hey everyone, What is the difference between MonadPlus and Alternative? In my mind, it would make sense for the difference to be that the former provides and semantics (i.e., x `mplus` y means do both x and y) whereas the latter provides or semantics (i.e., x| y means do x or y but not both). However, when I look at the instances defined for List I see that it is exactly the same as MonadPlus. As other's've mentioned, they both have or semantics and it's just an artifact of the Monad/Applicative split. However, an additional note. For lists or sets, the mplus/(|) functions could be interpreted as both and and or semantics, depending on what you think lists are. If you think of them as a collection of multiple answers, then concatenating/unioning is colloquially regarded as saying I have xs and ys. However, if you think of them as giving a non-deterministic answer, then the concatenation/union should be regarded as saying you can chose the xs or the ys, which is closer to the logical interpretation of union as disjunction. I guess my point is that the notion of and isn't especially well-defined. At the very least there are three different notions of and. We have the andThen notion which corresponds to monadic bind, probabilistic conjunction, and Sigma types. We have the andAlso notion which corresponds to unions conceived of as nondeterminisms, also covers the linear conjunction which only lets you take one of the projections, and is the one involved with the idea of anding two functions with (+++). And we have the bothAnd notion which corresponds to Cartesian products, logical conjunction, the linear conjunction which lets you take both projections, and the notion of anding two functions with (***). -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] lazy A-star search
On 10/30/11 11:44 AM, Anton Kholomiov wrote: I'm misunderstanding astar. I've thought that 'whole route'-heuristic will prevent algorithm from going in circles. The more you circle around the more the whole route distance is. Thank you for showing this. There are multiple things involved in A*. Part of it is having the admissible heuristic in order to do forward-chaining in a way which accounts for things you haven't seen/handled yet.[1] Using an admissible heuristic isn't sufficient to prevent looping. Just consider a path which has a loop with zero cost or negative cost (if we're adding costs). A different part of it is the fact that we can implement A* as a dynamic programming algorithm in order to reduce the complexity of forward-chaining. This is the insight from Dijkstra's algorithm (and Prim's, and Kruskal's, and Warshall's,...), which also uses dynamic programming to reduce complexity. [1] Or dually, you could use an admissible heuristic to do backwards-chaining in a way that accounts for things you haven't seen/handled yet. But everyone seems to mean the forward-chaining variant when they talk about A* (perhaps because the backward-chaining variant would be better called B*, given the standard variable-naming convention). -- Live well, ~wren ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient mutable arrays in STM
Benjamin Franksen wrote: David Barbour wrote: Create an extra TVar Int for every `chunk` in the array (e.g every 256 elements, tuned to your update patterns). Read-write it (increment it, be sure to force evaluation) just before every time you write an element or slice it or slice the array element. Incrementing and forcing evaluation should not be necessary, a TVar () should be enough. I was wrong, though not completely. I would be very much surprised if the internal STM machinery compares the actual _values_ of what is inside a TVar, I guess it just notes that a read or a write happened. According to the original STM paper the implementation does an equality test, albeit only for pointer equality. So, one should make sure that whatever is written to the TVar is a new object. An incremented integer would probably be ok, (no need to evaluate it, since the closure is newly allocated, thus a new object), a little more on the safe side is a new TVar i.e. use TVar (TVar ()). Cheers Ben ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Efficient mutable arrays in STM
On Sun, Oct 30, 2011 at 6:20 PM, Ben Franksen ben.frank...@online.dewrote: According to the original STM paper the implementation does an equality test, albeit only for pointer equality. It strikes me as bad form to depend on characteristics of `the implementation`. An incremented integer would probably be ok, (no need to evaluate it, since the closure is newly allocated, thus a new object) Evaluation would be necessary to avoid a subtle space-leak with laziness semantics. The size of the closure is potentially linear with the number of allocations. A little more on the safe side is a new TVar That works too. Regards, Dave ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe