- Haskell-Cafe - Haskell.org

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

20 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 20 Dec '08

20 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 20 Dec '08

20 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

Conditional properties in QuickCheck alter test data generation?
by Kevin Van Horn 19 Dec '08

19 Dec '08

I'm learning QuickCheck, and I'm puzzled by the behavior I'm seeing with conditional properties. After writing and loading a simple qsort function from a separate file, I typed these into ghci: let prop_minimum xs = (length xs > 0) ==> head (qsort xs) == minimum xs where types = xs :: [Integer] let prop_minimum1 xs = (length xs > 3) ==> head (qsort xs) == minimum xs where types = xs :: [Integer] These differ only in that prop_minimum1 uses a more restrictive condition. Then quickCheck prop_minimum outputs "OK, passed 100 tests" but quickCheck prop_minimum1 outputs "Arguments exhausted after 0 tests" Investigating with verboseCheck yields puzzling results. For example, verboseCheck prop_minimum says "OK, passed 100 tests", but some of the test instances it shows have length 0, contrary to the condition... and a significant fraction of the test instances have length > 3, or even length > 10! So why the problem when running quickCheck on prop_minimum1? Running verboseCheck prop_minimum1 just deepens the mystery. Now we see most of the test instances generated having 0 length, and none of them having length > 3. What's going on here? Why is the distribution of generated test instances so drastically altered? BTW, I'm using ghc version 6.10.1, running on Intel Mac OS 10.5.5.

5 6

RWH book club
by Don Stewart 19 Dec '08

19 Dec '08

Matt Podwysocki set up a Real World Haskell book club, http://groups.google.com/group/real-world-haskell-book-club (a mailing list on google groups), with already some 200 members discussing typical new user Haskell questions. Feel free to join if you like talking about Haskell, or teaching new users. -- Don

1 0

ANN: Thingie-0.80
by Jeff Heard 19 Dec '08

19 Dec '08

I need a better name for this, but I have software, so I shall release it with a dumb name. Thingie has just been uploaded to hackage. It is a library for creating 2D visualizations in a purely functional manner. It supports static visualizations and animation, and like most vis libraries, can probably do games as well as simple viz graphics. The backend uses Cairo for rendering, but I'm looking to port it to OpenGL/GLUT for systems where Gtk/Cairo is hard to get working (i.e. OS/X). The idea is that you create a graph of objects or function that return objects and the library renders them for you in 2D. Right now, there's one thing I would like to add to the system above all other things: The interactive system has the concept of a tracked program state that is threaded through the graph. This state is defined by a UIState class, and any state (which is a record object) must be an instance of UIState and provide the system with a certain number of getters and setters for basic bits of state. I would like to use Template Haskell to help create/derive these structures. Does anyone on the list want to help with that? Here are two examples. Each draws a smiley face, and the interactive one tracks your mouse with a little red ball. First the non-interactive: module Main where import Graphics.Rendering.Thingie.Primitives import Graphics.Rendering.Thingie.Cairo import qualified Graphics.Rendering.Cairo as Cairo smiley = Context [FillRGBA 0 0 0 0, Operator Cairo.OperatorClear] $ Group [Draw rectangleFilled{ topleft=Point2D 0 0, width=200, height=200 } ,Context [FillRGBA 1 1 0 1, OutlineRGBA 0 0 0 1, Translate 100 100, Operator Cairo.OperatorOver] $ Group [Draw arc{ radius=100, filled=True } ,Context [FillRGBA 0 0 0 1] $ Group [Draw arc{ center=Point2D (-33) (-33), radius=10, filled=True } ,Draw arc{ center=Point2D 33 (-33), radius=10, filled=True } ,Draw arc{ angle1=degrees 30, angle2=degrees 150, radius=70 }]]] main = renderObjectToPNG "smiley.png" 200 200 smiley ----- Now the interactive: import Graphics.Rendering.Thingie.Interactive import Graphics.Rendering.Thingie.BasicUIState import Graphics.Rendering.Thingie.Cairo import Graphics.Rendering.Thingie.Primitives import qualified Graphics.Rendering.Cairo as Cairo smiley = Context [FillRGBA 0 0 0 0, Operator Cairo.OperatorClear] $ Group [Draw rectangleFilled{ topleft=Point2D 0 0, width=200, height=200 } ,Context [FillRGBA 1 1 0 1, OutlineRGBA 0 0 0 1, Translate 100 100, Operator Cairo.OperatorOver] $ Group [Draw arc{ radius=100, filled=True } ,Context [FillRGBA 0 0 0 1] $ Group [Draw arc{ center=Point2D (-33) (-33), radius=10, filled=True } ,Draw arc{ center=Point2D 33 (-33), radius=10, filled=True } ,Draw arc{ angle1=degrees 30, angle2=degrees 150, radius=70 }]]] undercursor uistate = Context [FillRGBA 1 0 0 1] $ Draw arcFilled{ center=mousePosition uistate, radius=5 } scene = [StaticElement smiley (Rect2D 0 0 0 0) ,UnboundedElement undercursor] main = simpleMotionSensitiveGui defaultBasicUIState scene "smiley face"

1 1

Coroutines
by Ryan Ingram 19 Dec '08

19 Dec '08

Andrew was recently asking about co-routines. A couple of years ago, I was in much the same position as him; although I am pretty sure I had heard the term before, it seemed like a mysterious idea with no practical use. Then I learned Ruby. Ruby makes extensive use of coroutines; it's not uncommon to have three or more coroutines executing cooperatively, made simple by how easy it is to pass blocks of code around in that language. The entire collection iteration system in Ruby is based on coroutines; if an object implements "each", it can be iterated over: [1, 2, 3].each { |x| print x } Implementing "each" for a container is generally simple; you just write a loop and call "yield" def each [1 .. length].each { |index| yield self[index] } end It surprised me how simple and powerful this concept was; code that previously was incredibly ugly to write became simple. I think this abstraction is one of the big reasons for Ruby's current success. At the Haskell Symposium this year, Jesse Tov gave a talk about Session Types in Haskell, and it struck me that they are ideal for implementing coroutines in a type-safe manner. Here you can write pure functions that represent a communicating routines, and guarantee that the communication completes successfully (assuming the routines terminate, of course). Consider these two values: f1 :: Int -> (Char, ()) f2 :: (Int, Char -> String) You can see a natural way to connect them, using the duality of (a, _) and (a -> _): connect_f1f2 :: ((), String) connect_f1f2 = let (arg1, k2) = f2 (arg2, result1) = f1 arg1 result2 = k2 arg2 in (result1, result2) I implemented this idea, along with a nice syntax for these coroutines, in http://hackage.haskell.org/cgi-bin/hackage-scripts/package/Coroutine-0.1.0.0: f1 :: InSession (Int :?: Char :!: Eps) () f1 = runSession $ do x <- get put (head $ show x) return () f2 :: InSession (Int :!: Char :?: Eps) String f2 = runSession $ do put 6 result <- get return ("the answer is " ++ [result]) (Caveat: while this uses the do-notation, it's not *exactly* a monad; it's something more general than that. See Control.Monad.Indexed for the details. Thanks to the GHC team for NoImplicitPrelude!) You can then add choice, looping constructs, etc., to allow increasingly complicated protocols: peer1 :: InSession ((Int :?: Int :!: Eps) :?* Eps) Int -- read an Int, then write an Int, any number of times we are told to do so -- then return an Int peer2 :: InSession ((Int :!: Int :?: Eps) :!* Eps) [Int] -- write an Int, then read an Int, any number of times we want -- then return a list of Ints. The neat thing about this library is that the communication is completely pure! No side effects required! ghci> :t connect peer1 peer2 connect peer1 peer2 :: (Int, [Int]) -- ryan On Wed, Dec 17, 2008 at 6:54 PM, Richard O'Keefe <ok(a)cs.otago.ac.nz> wrote: > On 18 Dec 2008, at 11:26 am, Andrew Coppin wrote: >>> >>> (Also, "coroutines"? Seriously? That's hardly an obscure term in >>> programming circles.) >>> >> >> Well now, I'm curios. I've been writing computer programs since I was 9 >> years old. I hold a diploma *and* an honours degree in computer science. And >> I have never even *heard* of a coroutine. To this day I still don't know >> what it means. I rather suspect I'm not the only "programmer" on earth who >> finds themselves in this position. ;-) > > Shame on you for not reading Knuth's > "The Art of Computer Programming", Volume 1, "Fundamental Algorithms". > The then available three volumes of TAOCP > "were named among the best twelve physical-science monographs > of the century by American Scientist" "at the end of 1999". > (Fasicles 0, 2, 3, and 4 of volume 4 are now available, and > parts of fasicle 1 are on-line. Hooray hooray!) > > Quoting the first two paragraphs of the Wikipedia entry: > "In computer science, coroutines are program components that generalize > subroutines to allow multiple entry points for suspending and resuming of > execution at certain locations. Coroutines are well-suited for implementing > more familiar program components such as cooperative tasks, iterators, > infinite lists and pipes. > The term "coroutine" was originated by Melvin Conway in his seminal 1963 > paper.[1]" > > So "coroutine" has been standard hacker-type programming terminology > since 1963. I was able to use coroutines in Burroughs Extended Algol > (designed in the mid to late 60s), Simula 67, and Interlisp-D (80s). > Current languages supporting them include (thanks, Wikipedia) Lua, > Limbo, JavaScript, Python, and Ruby. Since anything with continuations > can do coroutines, we add Scheme and SML/NJ. Sather's iterators may be > a more familiar form of coroutine. You will commonly find something > like a "yield e" statement that reports the value of e to the caller > without actually returning, and "resume c" that resumes a coroutine > to get the next value. > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

3 2

gtk2hs question - derive SettingsWindow from Window
by Cetin Sert 19 Dec '08

19 Dec '08

Hi all, For a network manager of sorts I'm working on, I want to derive a SettingsWindowClass from the WindowClass present in Gtk2Hs: I want (the) instance(s) of the SettingsWindowClass to have a field to store connection settings: 1) Is it safe to do it like this? class WindowClass self ⇒ SettingsWindowClass self where settingsWindowGetSettings :: self → IO [ConnectionSetting] settingsWindowSetSettings :: self → [ConnectionSetting] → IO () newtype SettingsWindow = SettingsWindow (Window,[ConnectionSetting]) mkSettingsWindow = SettingsWindow unSettingsWindow (SettingsWindow o) = o settingsWindowNew :: IO SettingsWindow settingsWindowNew = do win ← windowNew return $ mkSettingsWindow (win,[]) 2) Is this a common practice in gtk2hs usage? 3) And will GC properly free the memory allocated for the Window object? How is this ensured, do ForeignPtr's always call delete on the underlying C ptr when they get garbage collected? Best Regards, CS

2 1

Re: [Haskell] possible bug in pretty-1.0.1.0
by Duncan Coutts 18 Dec '08

18 Dec '08

On Mon, 2008-12-15 at 08:17 -0800, John MacFarlane wrote: > I noticed a difference in how "hang" works between pretty-1.0.0.0 and > pretty-1.0.1.0. I think it's a bug. If this isn't the right place to > report it, please let me know where I should. (Maintainer is listed > as libraries(a)haskell.org, but that is a closed mailing list. Perhaps > Cabal should include a report-bugs-at field?) I'd just like to advertise the fact that as of Cabal-1.6 you can put a bug-reports field in your .cabal file and it will be displayed by hackage. We would like to encourage all package authors to use this. It can be a mailto: url to a maintainer or mailing list or it can be a http: url to a bug tracker website. (Cabal-1.6 also supports specifying darcs/git/whatever repos) Duncan

2 2

Re: [Haskell-cafe] Functional MetaPost in 5 Steps
by Stefan Endrullis 18 Dec '08

18 Dec '08

I have the same problem with FuncMP. I've also replaced the "generate" function by a custom "toMPFile" as you suggested, but mpost still generates only an empty white sheet. I've used the simple example posted in the first message of this thread. The generated .mp file is also relatively simple (see attachment http://www.nabble.com/file/p21070707/Test.mp Test.mp ) The only problem is the line "input FuncMP", which produces additional code in the ps file and causes the white page. If you remove this line everything is fine again and you can see the text "blah". Here's the additional code FuncMP produces in the .ps file: ----------------------------------------------------------------- /xdvi$run where {pop errordict begin /undefined {} bind def end} if /fmp1 /fmp1 def /fmp8 /fmp8 def /fmp24 /fmp24 def /bitline1 {gsave pop dup scale dup length 8 mul 1 true currentpoint translate [66.66666 0 0 66.66666 0 0] 4 index imagemask pop grestore} bind def /bitline8 {gsave pop dup scale dup length 1 8 currentpoint translate [2.8 0 0 2.8 0 0] 4 index image pop grestore} bind def /bitline24 {gsave pop dup scale dup length 3 idiv 1 8 currentpoint translate [2.777777 0 0 2.777777 0 0] 4 index false 3 colorimage pop grestore} bind def /XDVIfshow {findfont exch scalefont setfont show} bind def /DVIPSfshow {exch gsave 72 TeXDict /Resolution get div -72 TeXDict /VResolution get div scale 1 DVImag div dup scale get cvx exec show grestore} bind def /fshowText {/xdvi$run where {pop XDVIfshow} {DVIPSfshow} ifelse} def /fshow { exch dup /fmp1 eq {bitline1} {dup /fmp8 eq {bitline8} {dup /fmp24 eq {bitline24} {fshowText} ifelse} ifelse} ifelse} def ----------------------------------------------------------------- You can also fix the .ps file by removing the "/fshow ..." part from the file and the text "blah" will appear in your ghostscript viewer. Well, this is my first test with FuncMP and that's why I'm asking this silly question now: Is the "fshow" function really necessary or can I remove it from every generated .ps file without problems? :) Or you know another solution? Does your generated .ps files also contain this code? If no, what version of FuncMP do you use? -- View this message in context: http://www.nabble.com/Functional-MetaPost-in-5-Steps-tp20144360p21070707.ht… Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

1 0

excessive usage of CPU by threadDelay in GHCi
by Jeremy Shaw 18 Dec '08

18 Dec '08

Hello, I have the following simple program: import Control.Concurrent main = threadDelay (10^6) >> main If I run it in GHCi it requires 2-5% of my CPU. If i compile it, it takes 0% of my CPU. It does not matter if I compile -O0, -O2, -threaded, it always uses 0% (which is good). Is it expected that threadDelay should be really expensive in GHCi? Am I doing something wrong? Or should I file a bug? Thanks. - jeremy

2 1

How to choose an arbitrary Arbitrary?
by Bas van Dijk 18 Dec '08

18 Dec '08

Hello, I was playing with the following tree type (attached below) which can be seen as the reification of an applicative. I wondered if I could define a QuickCheck Arbitrary instance for it. The only way I got it to type check however, was to give 'arg' a monomorphic type (for example: 'Gen (Tree ())'). If I left it polymorphic I got a "Ambiguous type variable in constraints" error. This is understandable because if the subtrees have polymorphic types they can be of any type: Tree Int, Tree Float, Tree String, etc. The system then doesn't know which Arbitrary to choose. My question is, is it possible to keep 'arg' polymorphic (i.e. 'Gen (Tree b)') and let the system somehow choose an arbitrary Arbitrary? I guess not, however I like to be proven wrong. regards, Bas ---------------------------------------------------- {-# LANGUAGE ExistentialQuantification #-} module Tree where import Control.Monad import Test.QuickCheck -- I'm using QuickCheck-2.1.0.1 data Tree a = Val a | forall b. Tree (b -> a) :*: Tree b instance Arbitrary a => Arbitrary (Tree a) where arbitrary = sized sizedTree sizedTree :: (Arbitrary a) => Int -> Gen (Tree a) sizedTree n | n <= 0 = liftM Val arbitrary | otherwise = liftM2 (:*:) func arg where m = n `div` 2 func = sizedTree m arg :: Gen (Tree ()) -- how to make this: -- Gen (Tree b) ??? arg = sizedTree m ----------------------------------------------------

2 2

Implementing PacMan
by Andrew Coppin 18 Dec '08

18 Dec '08

What do we think of this, folks? http://prog21.dadgum.com/23.html (And the rest in the series, obviously.) To me, it seems that this plan would *work*... but it wouldn't be very eligant. You'd have the code to respond to user input and move PacMan in one place, the code for collision detection in other place, the code that decides what to *do* about a collision somewhere else, the code for drawing the animations in yet another place... If you wanted to change one game element, you'd have to make changes scattered all over the place. The whole thing seems messy, non-modular and non-composible to my ears. Thoughts, people?

4 6

Re: [Haskell-cafe] Re: Time for a new logo?
by Jeff Wheeler 18 Dec '08

18 Dec '08

On Dec 16, 2008, at 10:08 PM, Ryan Grant wrote: > nice. > the first is better. > in the second, i don't even see the lambda. Thanks the feedback. I just uploaded a new version [1] that is icon- sized, although the font used is Helvetica Neue, which is non-free. I have no free fonts on my Mac, unfortunately, so it'll stay for the moment. Jeff Wheeler [1] http://media.nokrev.com/junk/haskell-logos/logo4.png

2 1

Please tell me this function exists
by Brian Hurt 18 Dec '08

18 Dec '08

I know it's not hard to write, but still: concat :: String -> [String] -> String concat _ [] = "" concat _ [x] = x concat sep x:xs = x ++ sep ++ (concat sep xs) I've got to be stupid and missing it in the standard libraries. Please tell me where. Thanks. Brian

5 6

monadic versus aplicative style. These two snips seem to do the same thing yet one has a bug.
by Thomas Hartman 18 Dec '08

18 Dec '08

Hi, I rewrote a piece of code that used applicative to use instead monadic style, basically because I wanted to adapt it for my own purposes but hadn't wrapped my head around applicative yet. Unfortunately my rewrite had a bug, which I'm still not completely clear on. (I am guessing it's a laziness mixed with IO issue.) I discarded my own version and am using the original now of course, but I'm curious if anyone has anything to say on the difference between these two bits of code and, in general if there is any way to "think" about the difference between monadic and applicative. For what it's worth, the code comes from HSTringTemplate (on hackage). The bug is described in http://groups.google.com/group/HAppS/browse_thread/thread/70d4b1fbe8a4c7ac Basically, in happs, this bit of code caused an unrelated handler to not fully pages correctly, where there was more than one image to load. It took forever to diagnose and track this down. Ugh. Thanks, thomas. -- incorrect behavior directoryGroup' :: (FilePath -> FilePath -> IO (StringTemplate a)) -> FilePath -> IO (STGroup a) directoryGroup' templatereader path = do fs <- return . ( filter ((".st" ==) . takeExtension) ) =<< getDirectoryContents path templates <- mapM (templatereader path) fs stmapping <- return $ zip fs templates return $ groupStringTemplates stmapping -- correct behavior --directoryGroup2' :: (Stringable a) => FilePath -> IO (STGroup a) directoryGroup'2 templatereader path = groupStringTemplates <$> (fmap <$> zip . (map dropExtension) <*> mapM ( templatereader path ) =<< filter ((".st" ==) . takeExtension) <$> getDirectoryContents path)

1 2

Threads not running under GHC 6.10?
by Gwern Branwen 17 Dec '08

17 Dec '08

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 So, the Hint library was recently updated and I was editing Mueval to run with (i386) 6.10, when I discovered that for some reason, DoS'ing expressions were succeeding in rendering my machine unusable. Eventually, I discovered that my watchdog thread didn't seem to be running. But with +RTS -N2 -RTS all my tests did pass! Here's a simple example of what I mean; the following is basically a very lightly adapted version of the actual Mueval code: - ---------------- import Control.Concurrent (forkIO, killThread, myThreadId, threadDelay, throwTo, yield, ThreadId) import System.Posix.Signals (sigXCPU, installHandler, Handler(CatchOnce)) import Control.OldException (Exception(ErrorCall)) main :: IO () main = do tid ThreadId -> IO () watchDog tout tid = do installHandler sigXCPU (CatchOnce $ throwTo tid $ ErrorCall "Time limit exceeded.") Nothing forkIO $ do threadDelay (tout * 100000) -- Time's up. It's a good day to die. throwTo tid (ErrorCall "Time limit exceeded") yield -- give the other thread a chance killThread tid -- Die now, srsly. error "Time expired" return () -- Never reached. Either we error out in -- watchDog, or the evaluation thread finishes. - -------------- Now, from the looks of it, this should always error out with "Time limit exceeded." And the threading is done via forkIO, so it shouldn't matter how it's compiled (be it threaded or no) or run; nor do we need to worry about optimizations, since x has no sensible value for any input - it's always bottom. But the results are very different: gwern@craft:31542~>=ghc -fforce-recomp -O0 example.hs && ./a.out ^C^C gwern@craft:31532~>=ghc -fforce-recomp -O0 -threaded example.hs && ./a.out ^C^C gwern@craft:31536~>=ghc -threaded -fforce-recomp -O0 -threaded example.hs && ./a.out +RTS -N1 -RTS [a minute later] ^C^C^C^C^C^C gwern@craft:31540~>=ghc -threaded -fforce-recomp -O0 -threaded example.hs && ./a.out +RTS -N2 -RTS a.out: Time limit exceeded gwern@craft:31543~>=ghc -fforce-recomp -O2 example.hs && ./a.out a.out: Time limit exceeded gwern@craft:31544~>=ghc -threaded -fforce-recomp -O2 example.hs && ./a.out a.out: Time limit exceeded gwern@craft:31545~>=ghc -threaded -fforce-recomp -O2 example.hs && ./a.out +RTS -N1 -RTS a.out: Time limit exceeded gwern@craft:31546~>=ghc -threaded -fforce-recomp -O2 example.hs && ./a.out +RTS -N2 -RTS a.out: Time limit exceeded So it seems that without optimizations, or without explicit/multiple OS threads, the watchdog thread never gets called! I'm not any sort of expert on parallelism or GHC, but this seems like a bad thing to me. One final note: I suspect there are further ways this can manifest. When compiled with -O2, example.hs terminates (as it should). But Mueval does in fact set -O2 as a ghc-option:, and yet I still found it looping. So, does anyone know whether this is an already known bug or whether it's something else? - -- gwern -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEAREKAAYFAkk63+EACgkQvpDo5Pfl1oITZgCdG2p4VcB6m5IhfqzOT0fi5qrI VagAnRILZSxBzadSj2wlzoOWfBuwdbJo =X61b -----END PGP SIGNATURE-----

3 4

Type wildcards
by Eyal Lotem 17 Dec '08

17 Dec '08

Martin Foster (aka. EvilTerran) suggested an interesting idea, and I decided it was too nice to ignore/be forgotten inside Martin's head... So I'd like to try and suggest it. Type wildcards that allow partially specifying types, e.g: f :: _ -> String f x = show x This will instruct the type-inferrer to "fill out" the wild-card part only (e.g: Show a => a). This feature can be used for a couple of benefits: A. It allows hard-coding part of a type, rather than the all-or-nothing situation we have now (I want to force a single parameter to be more specific, but I'd still prefer to infer the whole type). B. Without scoped type variables, there are currently situations you cannot provide a type signature at all. This may mean that you cannot resolve type ambiguities in some cases, or make types more specific for some purpose. A type wild-card, in addition to scoped type variables, will allow to only specify the part we want. C. Its a nice way to kill the -Wall warnings about missing type declarations, if you want to: f :: _ f = "I am explicitly asking to infer this type, rather than specifying it" Eyal

4 3

Fwd: cabal-install sends invalid proxy password
by Valery V. Vorotyntsev 17 Dec '08

17 Dec '08

Hello, > I was surprised to discover that `cabal-install' -- a popular utility > for installing Hackage packages -- cannot work with HTTP proxies. > Despite all the necessary code linked in. > > `cabal update' command returns HTTP 407 (Proxy Authentication Required) > error. The problem is explained below and patches follow. See http://article.gmane.org/gmane.comp.lang.haskell.libraries/10420 No response so far. (I start to suspect that there is just one "proxied haskeller" subscribed to `libraries' and `cabal-dev' lists:) -- vvv

1 0

How to think about this? (profiling)
by Patrick Perry 17 Dec '08

17 Dec '08

I agree with everyone else who has said that the better solution is Lemmih's. It is simple, fast, and does not use much memory. On the other hand, here is a more faithful implementation of what you were trying to write. To use mutable arrays, you need to work in either the IO or the ST monad. The advantage of ST is the function "runST", which is roughly equivalent to "unsafePerformIO", but is much safer. I hope this helps, Patrick \begin{code} import Control.Monad import Control.Monad.ST import Data.Array.ST import System.Environment -- | Create an array for storing the results of foo 0 through foo n. -- Initialize foo 0, foo 1, and foo 2, but set all other values to -- 'missing'. newMemo :: Int -> ST s (STUArray s Int Int) newMemo n = do arr <- newArray (0,n) missing :: ST s (STUArray s Int Int) writeArray arr 0 0 writeArray arr 1 1 writeArray arr 2 2 return arr -- | Code to indicate a missing value in the memo array. missing :: Int missing = -1 -- | Compute the value of the function at @i@, using the memo-ed results -- in the array. fooWithMemo :: STUArray s Int Int -> Int -> ST s Int fooWithMemo arr i = do x <- readArray arr i if x /= missing then return x else do r <- liftM3 (\ a b c -> a + b + c) (fooWithMemo arr $ i - 1) (fooWithMemo arr $ i - 2) (fooWithMemo arr $ i - 3) writeArray arr i r return r foo :: Int -> Int foo n = runST $ do arr <- newMemo n fooWithMemo arr n main = do (n:_) <- liftM (map read) getArgs print $ foo n \end{code}

1 0

Reader monad, implicit parameters, or something else altogether?
by Bjorn Buckwalter 17 Dec '08

17 Dec '08

All, I have a growing amount of astrodynamics code that relies on various physical "constants". The problem with these so called "constants" are that they either aren't really constants or aren't well known. An example is the leap second table (see Data.Time.Clock.TAI). I'd like to be able to fetch current values of these constants at runtime and make them accessible to my astrodynamics functions by some means. To clarify, once initialized the constants will be considered constant for the remainder of the program. I'd store the constants in a data structure along the lines of: > data AstroData a = AstroData > { mu_Earth :: GravitationalParameter a > , leapSeconds :: LeapSecondTable > } I would like to know if there is any consensus on what is the best way to make such a data structure accessible in pure functions. Passing it explicitly would be a mess. It seems that two options are to use either a Reader monad or implicit parameters. Using a Reader monad is straight forward enough though it requires writing/converting code in/to monadic style and adds some clutter to the formulae. It seems implicit parameters could be cleaner but I've seen them referred to as everything from evil to "just what you need" and rendering the Reader monad obsolete... What do you people recommend? Thanks, Bjorn Buckwalter

5 7

Random language humour
by Andrew Coppin 17 Dec '08

17 Dec '08

http://www.aegisub.net/2008/12/if-programming-languages-were-religions.html Seems pretty accurate, actually...

1 0

How to think about this? (profiling)
by Magnus Therning 17 Dec '08

17 Dec '08

This behaviour by Haskell seems to go against my intuition, I'm sure I just need an update of my intuition ;-) I wanted to improve on the following little example code: foo :: Int -> Int foo 0 = 0 foo 1 = 1 foo 2 = 2 foo n = foo (n - 1) + foo (n - 2) + foo (n - 3) This is obviously going to run into problems for large values of `n` so I introduced a state to keep intermediate results in: foo :: Int -> State (UArray Int Int) Int foo 0 = return 0 foo 1 = return 1 foo 2 = return 2 foo n = do c <- get if (c ! n) /= -1 then return $ c ! n else do r <- liftM3 (\ a b c -> a + b + c) (foo $ n - 1) (foo $ n - 2) (foo $ n - 3) modify (\ s -> s // [(n, r)]) return r Then I added a convenience function and called it like this: createArray :: Int -> UArray Int Int createArray n = array (0, n) (zip [0..n] (repeat (-1))) main = do (n:_) <- liftM (map read) getArgs print $ evalState (foo n) (createArray n) Then I thought that this still looks pretty deeply recursive, but if I call the function for increasing values of `n` then I'll simply build up the state, sort of like doing a for-loop in an imperative language. I could then end it with a call to `foo n` and be done. I replaced `main` by: main = do (n:_) <- liftM (map read) getArgs print $ evalState (mapM_ foo [0..n] >> foo n) (createArray n) Then I started profiling and found out that the latter version both uses more memory and makes far more calls to `foo`. That's not what I expected! (I suspect there's something about laziness I'm missing.) Anyway, I ran it with `n=35` and got foo n : 202,048 bytes , foo entries 100 mapM_ foo [0..n] >> foo n : 236,312 , foo entries 135 + 1 How should I think about this in order to predict this behaviour in the future? /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus＠therning．org Jabber: magnus＠therning．org http://therning.org/magnus Haskell is an even 'redder' pill than Lisp or Scheme. -- PaulPotts

8 10

haskell compiler never comes back
by Greg Meredith 17 Dec '08

17 Dec '08

Haskellians, The simple-minded and smallish code sample at this link<http://paste.pocoo.org/show/95503/>causes the compiler to go off into never-never land. Any clues would be greatly appreciated. Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com

3 7

Re: [Haskell] Missing Documentation
by Neil Mitchell 16 Dec '08

16 Dec '08

Hi Ron > This may very well be a FAQ, but I tried to search the archives and could not find a post... > Anyway, some documentation seems to be missing, which was there before I thought. For example: > http://www.haskell.org/ghc/docs/latest/html/libraries/haskell98/Random.html That's a bug, I've reported it here: http://hackage.haskell.org/trac/ghc/ticket/2886 > Thanks, and sorry if this lowers the S/N We usually use haskell@ for annoucements, and haskell-cafe@ for general discussion/questions etc, so in future these kinds of posts should go on that mailing list. It's a confusing system! Any follow ups to this post should also only go to haskell-cafe@ Thanks Neil

2 2

MVar and Par ..
by Mozhgan Kabiri 16 Dec '08

16 Dec '08

Hi .. Hope you are doing well . I've just joined this group. Recently, I am struggling to do some simple experiment with haskell language about parallelism and wrong answers that we can get while using a shared variable . I tried to write a simple program, for example calculationg 'n=n+1' few times.And then I tried to do it in parallel by using 'par' and 'pseq' . The aim was to get the wrong answer because we have to share a variable here,and without using 'MVar' function we will get the wrong answer for the calculation .I don't know how to write it in parallel in order to get a wrong answer when we don't use MVar,because we have a shared variable here. I read about MVars as well,but also I don't know how to combine MVar and Par together to get the program to work.I wrote this :module Main where f :: Int -> Int -> Int f i n = g 1 i n where g x i n | x <= i = g (x+1) i (n+1) | otherwise = n main :: IO () main = do putStrLn "starting..." let r = f 10 5 putStrLn (show r) putStrLn "finished" I want to make to work in parallel by using 'Par'.And also use MVar for this simple example to work.All of the example about MVar are a little bit complicated and I couldn't figure it that how can I write one,the same !Can any one help me with this ? I want a simple example that I can feel the need of MVar when I run my program in parallel and while I am using a shared variable.Regards; Mozhgan _________________________________________________________________ News, entertainment and everything you care about at Live.com. Get it now! http://www.live.com/getstarted.aspx

3 7

MVar and Par ..
by Mozhgan Kabiri 16 Dec '08

16 Dec '08

Hi .. Hope you are doing well . I've just joined this group. Recently, I am struggling to do some simple experiment with haskell language about parallelism and wrong answers that we can get while using a shared variable . I tried to write a simple program, for example calculationg 'n=n+1' few times.And then I tried to do it in parallel by using 'par' and 'pseq' . The aim was to get the wrong answer because we have to share a variable here,and without using 'MVar' function we will get the wrong answer for the calculation .I don't know how to write it in parallel in order to get a wrong answer when we don't use MVar,because we have a shared variable here. I read about MVars as well,but also I don't know how to combine MVar and Par together to get the program to work.I wrote this :module Main where f :: Int -> Int -> Int f i n = g 1 i n where g x i n | x <= i = g (x+1) i (n+1) | otherwise = n main :: IO () main = do putStrLn "starting..." let r = f 10 5 putStrLn (show r) putStrLn "finished" I want to make to work in parallel by using 'Par'.And also use MVar for this simple example to work.All of the example about MVar are a little bit complicated and I couldn't figure it that how can I write one,the same !Can any one help me with this ? I want a simple example that I can feel the need of MVar when I run my program in parallel and while I am using a shared variable.Regards; Mozhgan Get news, entertainment and everything you care about at Live.com. Check it out! _________________________________________________________________ Explore the seven wonders of the world http://search.msn.com/results.aspx?q=7+wonders+world&mkt=en-US&form=QBRE

1 0

Re: [Haskell-cafe] Multi-parameter type class woes
by Mario Blažević 16 Dec '08

16 Dec '08

> I think that http://www.haskell.org/pipermail/haskell-cafe/2008-April/041461.html > may be relevant. It's a design decision. Thanks for the link. I've read through the thread, but rather than try to figure out if it's the same issue and whether it's a design decision or a historical accident, I've decided to create a ticket (#2885) and let GHC developers decide if it's valid or not.

1 0

Minimal complete definitions
by George Pollard 16 Dec '08

16 Dec '08

Good afternoon Café, I've written a little bit of code to calculate minimal complete definitions for a class given which of its functions use which other functions. As an example: doDependencies ord = ([],[["<="],["compare"]]) doDependencies num = (["plus","times","abs","signum","fromInteger"],[["minus"],["negate"]]) The first part of the pair is those functions which must *always* be implemented, the second part is a list of possible minimal complete definitions available for the provided list. This can help catch mistakes; a comment in the GHC source for GHC.Classes notes that compare must be implemented using (<=) and not (<) in order to give the minimal complete definition (<= OR compare). If we use the incorrect (<) then my code calculates the MCD as: doDependencies wrongOrd = ([],[["<"],["<","<=","compare"],["compare"]]) That is, the MCD is (< OR (< AND <= AND compare) OR compare). Now I have two questions: 1) Is my code correct? ;) 2) Could this be incorporated into GHC in order to detect when someone hasn't provided a sufficient definition for a class? As an example, it could detect this: > ~$ cat test2.hs > data Die d = Die d > instance Eq (Die d) where > main = do > let i = Die "stack overflow" > print (i == i) > ~$ ghc -Wall test2.hs --make > ~$ ./test2 > Stack space overflow: current size 8388608 bytes. > Use `+RTS -Ksize' to increase it. Given the following: doDependencies [("==", Just ["/="]),("/=", Just ["=="])] = ([],[["/="],["=="]]) GHC could warn that either (==) or (/=) must be implemented. Thanks, - George

1 2

Re: Re: [Haskell-cafe] Multi-parameter type class woes
by Mario Blažević 16 Dec '08

16 Dec '08

> I'll take a swing at this one: > > instance Container (Maybe x) [x] where > wrapper = isNothing > . . . > > That isn't a sensible definition of 'wrapper', but I believe without > trying to compile it is completely legal. Which wrapper do you use? > > You /don't/ have a different matching Container instance, but without the > functional dependency you /might/, and ghc barfs. But liftWrap doesn't require any particular instance, it's a generic function accepting any pair of types for which there is an instance of Container. Instance selection (as I understand it) shouldn't come into play until one applies liftWrap to a particular type, and indeed it does cause problems there: note the type annotations on the last line. That part I understand and accept, or at least have learned to live with. > On Sun, 14 Dec 2008, Mario Bla?evi? wrote: > >> I have, for a change, a relatively simple problem with >> type classes. Can somebody explain to me, or point me to an explanation of >> the behaviour I see? >> >> Here is a short and useless example: >> >> {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} >> >> import Data.Maybe >> >> class Container x y where >> wrapper :: x -> Bool >> unwrap :: x -> y >> rewrap :: y -> x >> >> liftWrap :: Container x y => (y -> y) -> (x -> x) >> liftWrap f x = (if wrapper x then rewrap . f . unwrap else id) x >> >> instance Container (Maybe x) x where >> wrapper = isJust >> unwrap = fromJust >> rewrap = Just >> >> main = print (liftWrap (succ :: Int -> Int) (Just 1 :: Maybe Int)) >> >> GHC 6.10.1 refuses to typecheck the 'wrapper' function >> in definition of 'liftWrap', with the following error message: >> >> Could not deduce (Container x y) from the context (Container x y1) >> arising from a use of `wrapper' at Test.hs:11:22-30 >> Possible fix: >> add (Container x y) to the context of >> the type signature for `liftWrap' >> In the expression: wrapper x >> In the expression: >> (if wrapper x then rewrap . f . unwrap else id) x >> In the definition of `liftWrap': >> liftWrap f x = (if wrapper x then rewrap . f . unwrap else id) x >> >> Let me clarify that I'm aware that in this particular >> example a functional dependecy should be used. Also, I can think of a few >> workarounds for my actual problem, so I'm not asking for any solutions. I'm >> looking for an explanation. It bugs me that my intuition of how this type >> class should have worked is completely wrong. The error message does not >> help, to put it mildly. Where should I go, what should I read? >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >>

5 6

Re: [Haskell-cafe] Re: haskell compiler never comes back
by Greg Meredith 16 Dec '08

16 Dec '08

George, Thanks for the response. If i take out the AllowUndecidableInstances i get no complaints and the compiler hangs. See this<http://paste.pocoo.org/show/95523/>. Thus, i can find no observable difference for this flag in this particular code sample. Best wishes, --greg On Mon, Dec 15, 2008 at 2:34 PM, George Pollard <porges(a)porg.es> wrote: > This is precisely what AllowUndecidableInstances allows; the type > checking becomes possibly non-terminating. It should *eventually* > terminate because the stack depth is restricted. > > - George > -- L.G. Meredith Managing Partner Biosimilarity LLC 806 55th St NE Seattle, WA 98105 +1 206.650.3740 http://biosimilarity.blogspot.com

2 1

Data.List.Split
by Brent Yorgey 16 Dec '08

16 Dec '08

Today yet another newbie in #haskell asked about a 'split' function for lists, and I got fed up with saying 'no one can agree on the right interface so it doesn't exist, just write it yourself', because it's a really dumb answer, even if it's true. Instead of trying to get a 'split' function added to Data.List (which will never ever happen), I thought, why not create a module Data.List.Split which contains implementations of every conceivable way to split a list? Of course, people will probably still argue over what should go in such a module, what to name the various functions, etc., but hopefully we can converge on something useful. I've created a Data.List.Split page on the wiki: http://haskell.org/haskellwiki/Data.List.Split Please add code to it! Once something useful is hashed out we can upload it to hackage. Perhaps eventually some of it can be folded into the standard libraries, but this seems like a much more lightweight way to get started. -Brent

6 9

Re: [Haskell-cafe] Time for a new logo?
by Brettschneider, Matthias 16 Dec '08

16 Dec '08

If there is someone interested in playing around with the logo Don posted, I made a gimp-version out of it. http://frosch03.de/haskell/Haskell.xcf http://frosch03.de/haskell/Haskell.png -- Matthias

1 0

ICFP09 Call for Papers
by Matthew Fluet (ICFP Publicity Chair) 16 Dec '08

16 Dec '08

Call for Papers ICFP 2009: International Conference on Functional Programming Edinburgh, Scotland, 31 August - 2 September 2009 http://www.cs.nott.ac.uk/~gmh/icfp09.html ** Submission deadline: 2 March 2009 ** (submission deadline is earlier than usual) ICFP 2009 seeks original papers on the art and science of functional programming. Submissions are invited on all topics from principles to practice, from foundations to features, from abstraction to application. The scope includes all languages that encourage functional programming, including both purely applicative and imperative languages, as well as languages with objects or concurrency. Particular topics of interest include * Language Design: type systems; concurrency and distribution; modules; components and composition; metaprogramming; relations to object-oriented or logic programming; interoperability * Implementation: abstract machines; compilation; compile-time and run-time optimization; memory management; multi-threading; exploiting parallel hardware; interfaces to foreign functions, services, components or low-level machine resources * Software-Development Techniques: algorithms and data structures; design patterns; specification; verification; validation; proof assistants; debugging; testing; tracing; profiling * Foundations: formal semantics; lambda calculus; rewriting; type theory; monads; continuations; control; state; effects * Transformation and Analysis: abstract interpretation; partial evaluation; program transformation; program calculation; program proof * Applications and Domain-Specific Languages: symbolic computing; formal-methods tools; artificial intelligence; systems programming; distributed-systems and web programming; hardware design; databases; XML processing; scientific and numerical computing; graphical user interfaces; multimedia programming; scripting; system administration; security; education * Functional Pearls: elegant, instructive, and fun essays on functional programming The conference also solicits Experience Reports, which are short papers that provide evidence that functional programming really works or describe obstacles that have kept it from working in a particular application. What's different this year? ~~~~~~~~~~~~~~~~~~~~~~~~~~~ * The conference dates and the submission deadline are about one month earlier than usual. * Special 'Call for Experience Reports' page, suitable as a target for posts on blogs and social networks to reach practitioners who wouldn't normally think about submitting to a conference. If you have a blog, etc., please help by pointing your readers to: http://web.cecs.pdx.edu/~apt/icfp09_cfer.html Instructions for authors ~~~~~~~~~~~~~~~~~~~~~~~~ By Monday, 2 March 2009, 20:00 UTC, submit an abstract of at most 300 words and a full paper of at most 12 pages (4 pages for an Experience Report), including bibliography and figures. The deadline will be strictly enforced and papers exceeding the page limits will be summarily rejected. Authors have the option to attach supplementary material to a submission, on the understanding that reviewers may choose not to look at it. A submission will be evaluated according to its relevance, correctness, significance, originality, and clarity. It should explain its contributions in both general and technical terms, clearly identifying what has been accomplished, explaining why it is significant, and comparing it with previous work. The technical content should be accessible to a broad audience. Functional Pearls and Experience Reports are separate categories of papers that need not report original research results and must be marked as such at the time of submission. Detailed guidelines on both categories are below. Each submission must adhere to SIGPLAN's republication policy, as explained on the web. Violation risks summary rejection of the offending submission. Proceedings will be published by ACM Press. Authors of accepted submissions are expected to transfer the copyright to ACM. Presentations will be videotaped and released online if the presenter consents by signing an additional permission form at the time of the presentation. Released videos will be included along with the conference proceedings in the ACM Digital Library and may also be placed on a host such as YouTube or Google Video. Formatting: ~~~~~~~~~~~ Submissions must be in PDF format printable in black and white on US Letter sized paper and interpretable by Ghostscript. If this requirement is a hardship, make contact with the program chair at least one week before the deadline. ICFP proceedings are printed in black and white. It is permissible to include color in a submission, but you risk annoying reviewers who will have to decide if your final paper will be understandable without it. Papers must adhere to the standard ACM conference format: two columns, nine-point font on a ten-point baseline, with columns 20pc (3.33in) wide and 54pc (9in) tall, with a column gutter of 2pc (0.33in). A suitable document template for LaTeX is available from SIGPLAN. Submission: ~~~~~~~~~~~ Submissions will be accepted electronically at a URL to be named later. The deadline is set in Coordinated Universal Time. The world clock (http://www.timeanddate.com/worldclock/fixedtime.html?month=3&day=2&year=200…) can give you the equivalent in your local time, e.g., Noon Monday in Seattle, 3:00 PM Monday in New York, 8:00 PM Monday in London, 5:00 AM Tuesday in Tokyo. Citation: ~~~~~~~~~ We recommend (but do not require) that you put your citations into author-date form. This procedure makes your paper easier to review. For example, if you cite a result on testing as ``(Claessen and Hughes 2000)'', many reviewers will recognize the result instantly. On the other hand, if you cite it as ``[4]'', even the best-informed reviewer has to page through your paper to find the reference. By using author-date form, you enable a knowledgeable reviewer to focus on content, not arbitrary numbering of references. LaTeX users can simply use the natbib package along with the plainnat bibliography style. In practice, this means putting \usepackage{natbib} \bibpunct();A{}, \let\cite=\citep in your LaTeX preamble, and \bibliographystyle{plainnat} in your document. For most citations you will use the \cite command; if you want a citation like ``Claessen and Hughes (2000) showed that...'' you should use something like ``\citet{claessen:quickcheck} showed...'' Alternatively, the McBride bibliography style, which adheres to the Chicago manual of style ``Documentation Two'' specifications and which fixes some perceived deficiencies of natbib, may be used. The style file along with instructions for using it is available on the McBride web site. Author response: ~~~~~~~~~~~~~~~~ Authors will have a 48-hour period, starting at 20:00 UTC on 21 April 2009, to read and respond to reviews. Special categories of papers ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In addition to research papers, ICFP solicits two kinds of papers that do not require original research contributions: Functional Pearls, which are full papers, and Experience Reports, which are limited to four pages. Authors submitting such papers may wish to consider the following advice. Functional Pearls ~~~~~~~~~~~~~~~~~ A Functional Pearl is an elegant essay about something related to functional programming. It might offer: * a new and thought-provoking way of looking at an old idea * an instructive example of program calculation or proof * a nifty presentation of an old or new data structure * an interesting application of functional programming techniques * a novel use or exposition of functional programming in the classroom Functional Pearls are not restricted to the above varieties, however. While pearls often demonstrate an idea through the development of a short program, there is no requirement or expectation that they do so. Thus, they encompass the notions of theoretical and educational pearls. Functional Pearls are valued as highly and judged as rigorously as ordinary papers, but using somewhat different criteria. In particular, a pearl is not required to report original research. However, it should be concise, instructive, and entertaining. Your pearl is likely to be rejected if your readers get bored, if the material gets too complicated, if too much specialized knowledge is needed, or if the writing is inelegant. The key to writing a good pearl is polishing. A submission you wish to have treated as a pearl must be marked as such on the submission web page, and should contain the words ``Functional Pearl'' somewhere in its title or subtitle. These steps will alert reviewers to use the appropriate evaluation criteria. However, pearls will be combined with ordinary papers for the purpose of computing the conference's acceptance rate. Experience Reports ~~~~~~~~~~~~~~~~~~ The purpose of an Experience Report is to help create a body of published, refereed, citable evidence that functional programming really works---or to describe what obstacles prevent it from working. Possible topics for an Experience Report include, but are not limited to: * insights gained from real-world projects using functional programming * comparison of functional programming with conventional programming in the context of an industrial project or a university curriculum * project-management, business, or legal issues encountered when using functional programming in a real-world project * curricular issues encountered when using functional programming in education * real-world constraints that created special challenges for an implementation of a functional language or for functional programming in general An Experience Report is distinguished from a normal ICFP paper by its title, by its length, and by the criteria used to evaluate it. * Both in the proceedings and in any citations, the title of each accepted Experience Report must begin with the words ``Experience Report'' followed by a colon. The acceptance rate for Experience Reports will be computed and reported separately from the rate for ordinary papers. * An Experience Report is at most 4 pages long. Each accepted Experience Report will be presented at the conference, but depending on the number of Experience Reports and regular papers accepted, authors of Experience reports may be asked to give shorter talks. * Because the purpose of Experience Reports is to enable our community to accumulate a body of evidence about the efficacy of functional programming, an acceptable Experience Report need not add to the body of knowledge of the functional-programming community by presenting novel results or conclusions. It is sufficient if the Report states a clear thesis and provides supporting evidence. The thesis must be relevant to ICFP, but it need not be novel. The program committee will accept or reject Experience Reports based on whether they judge the evidence to be convincing. Anecdotal evidence will be acceptable provided it is well argued and the author explains what efforts were made to gather as much evidence as possible. Typically, more convincing evidence is obtained from papers which show how functional programming was used than from papers which only say that functional programming was used. The most convincing evidence often includes comparisons of situations before and after the introduction or discontinuation of functional programming. Evidence drawn from a single person's experience may be sufficient, but more weight will be given to evidence drawn from the experience of groups of people. An Experience Report should be short and to the point: make a claim about how well functional programming worked on your project and why, and produce evidence to substantiate your claim. If functional programming worked for you in the same ways it has worked for others, you need only to summarize the results---the main part of your paper should discuss how well it worked and in what context. Most readers will not want to know all the details of your project and its implementation, but please characterize your project and its context well enough so that readers can judge to what degree your experience is relevant to their own projects. Be especially careful to highlight any unusual aspects of your project. Also keep in mind that specifics about your project are more valuable than generalities about functional programming; for example, it is more valuable to say that your team delivered its software a month ahead of schedule than it is to say that functional programming made your team more productive. If your paper not only describes experience but also presents new technical results, or if your experience refutes cherished beliefs of the functional-programming community, you may be better off submitting it as a full paper, which will be judged by the usual criteria of novelty, originality, and relevance. If you are unsure in which category to submit, the program chair will be happy to help you decide. Other information ~~~~~~~~~~~~~~~~~ Conference Chair ~~~~~~~~~~~~~~~~ Graham Hutton (University of Nottingham) Program Chair ~~~~~~~~~~~~~ Andrew Tolmach Department of Computer Science Portland State University P.O. Box 751, Portland, OR 97207 USA Email: apt(a)cs.pdx.edu Phone: +1 503 725 5492 Fax: +1 503 725 3211 Mail sent to the address above is filtered for spam. If you send mail and do not receive a prompt response, particularly if the deadline is looming, feel free to telephone. Program Committee ~~~~~~~~~~~~~~~~~ Amal Ahmed (Toyota Technological Institute, Chicago) Maria Alpuente (Technical University of Valencia (UPV)) Lennart Augustsson (Standard Chartered Bank) Lars Birkedal (IT University of Copenhagen) Manuel Chakravarty (University of New South Wales) Koen Claessen (Chalmers University of Technology) Marc Feeley (Universite de Montreal) Andrzej Filinski (University of Copenhagen) Daan Leijen (Microsoft Research) Xavier Leroy (INRIA Paris-Rocquencourt) Conor McBride (University of Strathclyde) Matthew Might (University of Utah) Shin-Cheng Mu (Academia Sinica) Atsushi Ohori (Tohoku University) Kristoffer Rose (IBM Thomas J. Watson Research Center) Important Dates (at 20:00 UTC) ~~~~~~~~~~~~~~~ Submission: 2 March 2009 Author response: 21-23 April 2009 Notification: 5 May 2009 Final papers due: 8 June 2009 ICFP 2009 Web Site ~~~~~~~~~~~~~~~~~~ http://www.cs.nott.ac.uk/~gmh/icfp09.html Special Journal Issue ~~~~~~~~~~~~~~~~~~~~~ There will be a special issue of the Journal of Functional Programming with papers from ICFP 2009. The program committee will invite the authors of select accepted papers to submit a journal version to this issue.

1 0

Missing comment highlighting in vim syntax script
by Ori Avtalion 15 Dec '08

15 Dec '08

Hi all, The Haskell syntax script for vim mentions this mailing list as the maintainer. Perhaps one of you could fix this bug. Comments on the same line as import declarations don't get highlighted: import A -- This comment isn't highlighted import B {- Neither is this -} import C {- and this -} I'm using this version of the syntax file: (the only version) http://vim.svn.sourceforge.net/viewvc/vim/vim7/runtime/syntax/haskell.vim?r… Thanks, Ori

4 3

Re: [Haskell] Re: Help : A problem with IO
by wman 15 Dec '08

15 Dec '08

you probably got it pointed out in haskell-beginners, but in case not: On Thu, Nov 27, 2008 at 7:10 PM, abdullah abdul Khadir < abdullah.ak2002(a)gmail.com> wrote: > a) I need to put a do after else for more than one instruction (?) No, the do thingy is a syntactic sugar for chaining "warm, fuzzy" (the "preffered" wannabe-joke-term for the presumably scary term monads/monadic) operations. it allows you to write in "classical" imperative/sequential style instead of chaining operations manually (using the >> and >>= operators, which the do notation translates into anyway). lookup some monad tutorials/docs. you are right in that if there is only one operation, no transformation is needed, so the do is unnecessary.

1 0

Problem with haddock 2.3.0 (again)
by Leonidas Fegaras 15 Dec '08

15 Dec '08

Sorry for the previous message. I am sending it again. Dear fellow haskell programmers, I tried to install a package in hackageDB and got a strange error from haddock: haddock: internal Haddock or GHC error: Maybe.fromJust: Nothing Here is the complete log: http://hackage.haskell.org/packages/archive/HXQ/0.10.0/logs/failure/ghc-6.8 When I build it using Cabal 1.6.0.1 and haddock 2.2.2 using 'runhaskell Setup.lhs haddock', it works fine (I get warnings but no errors). Also haddock 2.3.0 is not available in hackageDB so I can't test it myself. Where I can find haddock 2.3.0? Thank you for your help, Leonidas Fegaras _________________________________________________________________ Stay organized with simple drag and drop from Windows Live Hotmail. http://windowslive.com/Explore/hotmail?ocid=TXT_TAGLM_WL_hotmail_102008

7 29

Parsec and type level numerals
by Nathan Bloomfield 15 Dec '08

15 Dec '08

Hello all. I've got a puzzling Parsec problem. Perhaps the collective wisdom of haskell-cafe can point me in the right direction. I want to be able to parse a string of digits to a type level numeral as described in the Number parameterized types<http://okmij.org/ftp/papers/number-parameterized-types.pdf>paper. After fiddling with the problem for a while, I'm not convinced it's possible- it seems as though one would need to know the type of the result before parsing, but then we wouldn't need to parse in the first place. :) My first (simplified) approximation is as follows: > data Zero = Zero > data Succ a = Succ a > class Card t > instance Card Zero > instance (Card a) => Card (Succ a) > parseP :: (Card a) => Parser a > parseP = do { char '1' > ; rest <- parseP > ; return $ Succ rest > } > <|> return Zero I'd like for this to parse, for example, "111" into Succ Succ Succ Zero. Of course this doesn't work because parseP is ill-typed, but I'm not sure how to fix it. It seems that what I'm asking for is a function whose type is forall a. (Card a) => String -> a, which is problematic. Has anyone tried this before? I'm new to using Parsec and to parsing in general, so I apologize if this is a silly question. (Parsec is very impressive, by the way.) Thanks- Nathan Bloomfield University of Arkansas, Fayetteville

5 4

Multi-parameter type class woes
by Mario Blažević 15 Dec '08

15 Dec '08

I have, for a change, a relatively simple problem with type classes. Can somebody explain to me, or point me to an explanation of the behaviour I see? Here is a short and useless example: {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} import Data.Maybe class Container x y where wrapper :: x -> Bool unwrap :: x -> y rewrap :: y -> x liftWrap :: Container x y => (y -> y) -> (x -> x) liftWrap f x = (if wrapper x then rewrap . f . unwrap else id) x instance Container (Maybe x) x where wrapper = isJust unwrap = fromJust rewrap = Just main = print (liftWrap (succ :: Int -> Int) (Just 1 :: Maybe Int)) GHC 6.10.1 refuses to typecheck the 'wrapper' function in definition of 'liftWrap', with the following error message: Could not deduce (Container x y) from the context (Container x y1) arising from a use of `wrapper' at Test.hs:11:22-30 Possible fix: add (Container x y) to the context of the type signature for `liftWrap' In the expression: wrapper x In the expression: (if wrapper x then rewrap . f . unwrap else id) x In the definition of `liftWrap': liftWrap f x = (if wrapper x then rewrap . f . unwrap else id) x Let me clarify that I'm aware that in this particular example a functional dependecy should be used. Also, I can think of a few workarounds for my actual problem, so I'm not asking for any solutions. I'm looking for an explanation. It bugs me that my intuition of how this type class should have worked is completely wrong. The error message does not help, to put it mildly. Where should I go, what should I read?

2 1

ghc on CentOS 5 ?
by Steve Lihn 15 Dec '08

15 Dec '08

I recently got a CentOS server, but noticed that ghc rpm is not available from CentOS yum. After investigation, I found ghc is in Fedora repository, but does not make its way to EPEL, which yum on CentOS can use. ( http://download.fedora.redhat.com/pub/epel/5/x86_64/) Is there any plan to get it to EPEL? Or is there any missing piece preventing it? Thanks, Steve

3 2

Origins of '$'
by George Pollard 15 Dec '08

15 Dec '08

Hello Haskell-Café: This is a little bit random, but I was just wondering if anyone knew where the $ low-precedence parenthesis-eliminating application operator originated. The Haskell Report doesn't mention anything, and I can't search for "$" on Google. So... who thought it up? Does it originate in an earlier language, or is it uniquely Haskellish? :) - George

12 15

ANN: typehash version 1.3
by Lennart Augustsson 15 Dec '08

15 Dec '08

The typehash library allows you to produce a unique identifier (a cryptographic hash) for a type. This is useful if you save values of some type to a file (text, binary, whatever format you wish) and then when you read it back in again you want to verify that the type you want to read is the one you actually wrote. The type hash takes into account both the actual name of the type and the structure of the type. The type hash is a compact value that only allows comparing for equality. The library also supports type codes. A type code encodes the complete structure of a type and can be used for finer comparison than just equality, e.g., will the read function be able to read what show produced (in this case renaming types and adding constructors is allowed). The library is on hackage, of course. -- Lennart

1 0

ANNOUNCE: uvector-algorithms 0.1
by Dan Doel 15 Dec '08

15 Dec '08

Hello, I've been sitting on this for a while, waiting for some changes to uvector to go in, but finally decided I should just release it, and fix it up if and when said changes go in. So, I'm announcing the first release of uvector- algorithms. What it is is a library of algorithms (mostly sorting) for the mutable arrays defined in uvector. It has several varieties of sorting, including introsort (quicksort which falls back on heapsort in bad cases), heapsort, a simple top- down merge sort and a radix sort (as well as insertion sort, and optimal sorting for length<=4 arrays, which probably won't get much use outside of the implementation of the other sorts). All modules attempt to export as uniform an interface as possible, so that one can substitute between them freely, say when trying to determine which algorithm is best suited for your particular datasets. Also exposed are the operations that allow you to use the arrays as heaps (which is the basis for implementing heapsort), and partial sorts and selects in heap and intro variety. Lastly, there is a combinator for safely using these mutable array algorithms to sort immutable arrays. All of these algorithms have been painstakingly profiled, and their generated core examined to do as little heap allocation and as much unboxing as possible, and to inline and specialize for maximum performance (unless, of course, I've managed to miss anything). I've been running a relatively simple benchmarking suite that tests various kinds of inputs, and in my experience, the sorts herein tend to beat glibc's sort, and do relatively well compared to GNU's STL sorts over vector<>s (taking 50% or so more time at present, although this library may well be better at heapsorting random arrays, if you want something to brag about :)). For future work, I've been working on an implementation of Python's timsort (which is a very fancy bottom-up merge sort), but it's not ready yet. I'd also like to introduce some combinators for easy Schwartzian transforms, but that again requires modifications to uvector. I may also look at moving some of my benchmark program into the package. Suggestions for other algorithms people would like to see are of course welcome (especially if accompanied by papers/references on how to implement them if they're not well known). The hackage page is here: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/uvector-algorith… Enjoy, and please let me know of any issues. -- Dan

1 0

A curios monad
by Andrew Coppin 14 Dec '08

14 Dec '08

Yesterday I wrote something slightly unusual: module Storage where data Storage x instance Monad Storage run :: Storage x -> x data Key v instance Eq (Key v) instance Ord (Key v) new_key :: v -> Storage (Key v) set_key :: Key v -> v -> Storage () get_key :: Key v -> Storage (Maybe v) delete_key :: Key v -> Storage () In other words, you can store a value (of arbitrary type) under a unique key. The monad chooses what key for you, and tells you the key so you can look up or alter the value again later. Under the covers, it uses Data.Map to store stuff. I used some trickery with existential quantification and unsafeCoerce (!!) to make it work. Notice the sneaky phantom type in the key, telling the type system what type to coerce the value back to when you read it. Neat, eh? ...until I realised that somebody that somebody could generate a key in one run and then try to use it in another run. o_O Oops! But hey, until then it was working quite well. And completely pure; no IO anywhere. Ah well, just thought I'd share... (You could of course do away with the monad, but then you'd be able to manipulate the dictionary directly, and key uniqueness would be even more fragile!)

8 15

Small haskell practical course
by Marco Túlio Gontijo e Silva 14 Dec '08

14 Dec '08

Hello, I've presented a small practical course[0] in EMSL[1]. Any comments are welcome. 0: http://marcot.iaaeee.org/mini-curso.pdf (Portuguese only) 1: http://emsl.softwarelivre.org/ Greetings. -- marcot http://marcot.iaaeee.org/

2 2

Haskell Weekly News: Issue 97 - December 13, 2008
by Brent Yorgey 14 Dec '08

14 Dec '08

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20081213 Issue 97 - December 13, 2008 --------------------------------------------------------------------------- Welcome to issue 97 of HWN, a newsletter covering developments in the [1]Haskell community. Lots of neat blog posts and funny quotes this week. Don't forget to keep adding [2]haiku to the wiki, and don't miss Alex McLean (yaxu)'s [3]streaming livecoding performance tonight! Announcements Spam on HaskellWiki. Ashley Yakeley [4]asked what people would like to do about the increasing amounts of spam on the Haskell wiki, and offered some suggestions. The Timber compiler 1.0.2. Johan Nordlander [5]announced the first public release of the [6]Timber compiler. Timber is a modern language for building event-driven systems, based around the notion of reactive objects. It is also a purely functional language derived from Haskell, although with a strict evaluation semantics. To try it out, just grab the [7]timberc package on Hackage. Retrospective on 2008?. Don Stewart [8]proposed the idea of a 2008 retrospective. How would you choose the 10 best new libraries, applications, blog posts, etc. of 2008? a haskell_proposals subreddit. Jason Dusek [9]announced a [10]subreddit for Haskell library proposals. The idea is that Web 2.0 will help us to allocate our collective talents more efficiently when it comes to extensions (and perhaps clue us in when our pet project is something people really want). permutation-0.2. Patrick Perry [11]announced a [12]new version of the permutation library, which includes data types for storing permutations. It implements pure and impure types, the latter which can be modified in-place. The main utility of the library is converting between the linear representation of a permutation to a sequence of swaps. This allows, for instance, applying a permutation or its inverse to an array with O(1) memory use. Data.List.Split. Brent Yorgey [13]announced the creation of a wiki page for [14]Data.List.Split, a hypothetical module containing implementations of every conceivable way of splitting lists known to man, so we no longer have to (1) argue about the 'one true' interface for a 'split' function, or (2) be embarrassed when people ask why there isn't a split function in the standard libraries. Please add code or comments! At some point it will be uploaded as a new module to Hackage. Announcing Haskell protocol-buffers version 1.2.2. Chris Kuklewicz [15]announced new versions of [16]protocol-buffers, [17]protocol-buffers-descriptor, and [18]hprotoc. Discussion A curious monad. Andrew Coppin [19]exhibited an interesting Storage monad, which (it turns out) is similar to ST. An enlightening discussion if you want to understand how ST works and the motivation behind it. Origins of '$'. George Pollard [20]asked about the origins of the $ operator (low-precedence function application) in the standard libraries, leading to some interesting history and general discussion about notation. Blog noise [21]Haskell news from the [22]blogosphere. * Jamie Brandon: [23]Zombified GMap. Jamie is determined to get his SoC generalized map library released! * Philip Wadler: [24]Informatics 1 - Fancy Dress and Competition. * >>> Eduard - Gabriel Munteanu: [25]Learning Haskell, part 2. * Martin Sulzmann: [26]Equality, containment and intersection among regular expressions via symbolic manipulation. * Neil Mitchell: [27]mapM, mapM_ and monadic statements. * Alson Kemp: [28]A HAML parser for Haskell. * Chris Done: [29]More Haskell blogging. * Twan van Laarhoven: [30]Knight in n, part 4: tensors. Part four of Twan's enlightening series on computing knight moves. * Alex McLean: [31]Saturday night stream. All the cool kids will be watching Alex's streaming livecoding performance TONIGHT, using (among other things) a tool implemented in Haskell. * David Sankel: [32]Synchronous Events. * Lennart Augustsson: [33]The OCaml code again. * Lennart Augustsson: [34]Abstracting on, suggested solutions. * Lennart Augustsson: [35]The abstraction continues. * Conal Elliott: [36]Functional interactive behavior. * Conal Elliott: [37]Trimming inputs in functional reactive programming. * Mikael Vejdemo Johansson (Syzygy-): [38]J, or how I learned to stop worrying and love the matrix. * Conal Elliott: [39]Why classic FRP does not fit interactive behavior. * Clifford Beshers: [40]Functional Programming Marketing. * Lennart Augustsson: [41]A somewhat failed adventure in Haskell abstraction. * >>> Joey Hess: [42]haskell and xmonad. * Andy Gill: [43]The Timber compiler 1.0.2. * Manuel M T Chakravarty: [44]Not a particularly good article, but.... * >>> Chris Double: [45]Random and Binary IO using Iteratees. * >>> Chris Double: [46]Not a Tutorial on HAppS. * "FP Lunch": [47]The new GHC API. * Luke Palmer: [48]Compact data types. * Neil Mitchell: [49]F# from a Haskell perspective. * Real-World Haskell: [50]RWH Now In Store. * >>> Sebastian Fischer: [51]Constraint Functional-Logic Programming. * >>> fhtr: [52]Hexagons with Haskell. * >>> Eduard - Gabriel Munteanu: [53]Learning Haskell. * Bryan O'Sullivan: [54]Functional programmers on Twitter. * Martin Sulzmann: [55]Parallel Join Patterns with Guards and Propagation. * Martin Sulzmann: [56]Multi-set rewrite rules with guards and a parallel execution scheme. * Martin Sulzmann: [57]STM with control: Communication for retrying transactions. * Martin Sulzmann: [58]Concurrent Goal-Based Execution of Constraint Handling Rules. * >>> talkingCode: [59]Haskell, GTK and Multi-Threading. * >>> Gianfranco Alongi: [60]QuickCheck(ing) the code I C - source. Quotes of the Week * quicksilver: Baughn: glFlush? the 80s called, they want your programs back? * gwern: the best way to optimize a program is to make it lazier or stricter. * ksf: Perl is obfuscated by design, haskell is designed by obfuscation. * conal: omg -- i can print right from emacs again. praise be to Linux! * mmorrow: [I] didn't realize what it really said until after i @remembered it * blackh: Haskell is great because of all the wonderful things you can't do with it. * JustinBogner: gitit's 46 dependencies convinced me to install cabal-install, and now I couldn't be happier! * Anonymous: I'd love to explain to you how to write hello world in Haskell, but first let me introduce you to basic category theory. * lilac: @type \o-> look at my muscles <lambdabot> forall t nice muscles. t -> nice -> muscles * ook: (:[]) * oink: <^(oo)^> * mmorrow: {-# RULES "HAI; CAN HAS STDIO?" id = unsafePerformIO (system "killall -9 breathingMachine && xeyes &" >> return id) #-} * gwern: We will be welcomed as liberators! I estimate that we will need 50000 haskellers at most and will be able to wind up the occupation quickly About the Haskell Weekly News New editions are posted to [61]the Haskell mailing list as well as to [62]the Haskell Sequence and [63]Planet Haskell. [64]RSS is also available, and headlines appear on [65]haskell.org. To help create new editions of this newsletter, please see the information on [66]how to contribute. Send stories to byorgey at cis dot upenn dot edu. The darcs repository is available at darcs get [67]http://code.haskell.org/~byorgey/code/hwn/ . References 1. http://haskell.org/ 2. http://haskell.org/haskellwiki/Haikus 3. http://yaxu.org/saturday-night-stream/ 4. http://article.gmane.org/gmane.comp.lang.haskell.general/16678 5. http://article.gmane.org/gmane.comp.lang.haskell.general/16672 6. http://timber-lang.org/ 7. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/timberc 8. http://article.gmane.org/gmane.comp.lang.haskell.cafe/48778 9. http://article.gmane.org/gmane.comp.lang.haskell.cafe/48721 10. http://www.reddit.com/r/haskell_proposals/ 11. http://article.gmane.org/gmane.comp.lang.haskell.cafe/48663 12. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/permutation 13. http://article.gmane.org/gmane.comp.lang.haskell.cafe/48868 14. http://haskell.org/haskellwiki/Data.List.Split 15. http://article.gmane.org/gmane.comp.lang.haskell.libraries/10406 16. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/protocol-buffers 17. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/protocol-buffers… 18. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/hprotoc 19. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/48806 20. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/48622 21. http://planet.haskell.org/ 22. http://haskell.org/haskellwiki/Blog_articles 23. http://jamiiecb.blogspot.com/2008/12/zombified-gmap.html 24. http://wadler.blogspot.com/2008/12/informatics-1-functional-programming.html 25. http://eduard-munteanu.blogspot.com/2008/12/learning-haskell-part-2.html 26. http://sulzmann.blogspot.com/2008/12/equality-containment-and-intersection.… 27. http://neilmitchell.blogspot.com/2008/12/mapm-mapm-and-monadic-statements.h… 28. http://www.alsonkemp.com/programming/a-haml-parser-for-haskell/ 29. http://chrisdone.com/blog/2008/12/11/More-Haskell-blogging 30. http://twan.home.fmf.nl/blog/haskell/Knight4.details 31. http://yaxu.org/saturday-night-stream/ 32. http://netsuperbrain.com/blog/posts/synchronous-events/ 33. http://augustss.blogspot.com/2008/12/ocaml-code-again-im-posting-slight.html 34. http://augustss.blogspot.com/2008/12/abstracting-on-suggested-solutions-i.h… 35. http://augustss.blogspot.com/2008/12/abstraction-continues-i-got-several.ht… 36. http://conal.net/blog/posts/functional-interactive-behavior/ 37. http://conal.net/blog/posts/trimming-inputs-in-functional-reactive-programm… 38. http://blog.mikael.johanssons.org/archive/2008/12/j-or-how-i-learned-to-sto… 39. http://conal.net/blog/posts/why-classic-frp-does-not-fit-interactive-behavi… 40. http://cliffordbeshers.blogspot.com/2007/11/functional-programming-marketin… 41. http://augustss.blogspot.com/2008/12/somewhat-failed-adventure-in-haskell.h… 42. http://kitenet.net/~joey/blog/entry/haskell_and_xmonad/ 43. http://blog.unsafeperformio.com/?p=32 44. http://justtesting.org/post/63809222 45. http://www.bluishcoder.co.nz/2008/12/random-and-binary-io-using-iteratees.h… 46. http://www.bluishcoder.co.nz/2008/12/not-tutorial-on-happs.html 47. http://sneezy.cs.nott.ac.uk/fplunch/weblog/?p=168 48. file://localhost/home/brent/hacking/hwn/20081213.html 49. http://neilmitchell.blogspot.com/2008/12/f-from-haskell-perspective.html 50. http://www.realworldhaskell.org/blog/2008/12/06/rwh-now-in-store/ 51. http://www-ps.informatik.uni-kiel.de/~sebf/projects/cflp.html 52. http://fhtr.blogspot.com/2008/12/hexagons-with-haskell.html 53. http://eduard-munteanu.blogspot.com/2008/12/learning-haskell.html 54. http://www.serpentine.com/blog/2008/12/05/functional-programmers-on-twitter/ 55. http://sulzmann.blogspot.com/2008/12/parallel-join-patterns-with-guards-and… 56. http://sulzmann.blogspot.com/2008/10/multi-set-rewrite-rules-with-guards-an… 57. http://sulzmann.blogspot.com/2008/12/stm-with-control-communication-for.html 58. http://sulzmann.blogspot.com/2008/12/concurrent-goal-based-execution-of.html 59. http://talkingcode.co.uk/2008/12/02/haskell-gtk-and-multi-threading/ 60. http://writert.blogspot.com/2008/12/quickchecking-code-i-c-source.html 61. http://www.haskell.org/mailman/listinfo/haskell 62. http://sequence.complete.org/ 63. http://planet.haskell.org/ 64. http://sequence.complete.org/node/feed 65. http://haskell.org/ 66. http://haskell.org/haskellwiki/HWN 67. http://code.haskell.org/~byorgey/code/hwn/

1 0