March 2009 - Haskell-Cafe

Haxr doesn't compile from cabal (HTTP > 4000 breaks it)
by Jeff Heard 28 Mar '09

28 Mar '09

The haxr cabal library dependencies seem to be off. I wonder, since haxr would benefit highly from the HTTP 4k series of performance improvements, is it trivial to make it compatible with the latest library? -- Jeff

2 1

Re: [Haskell-cafe] Definition of "tail recursive" wrt Folds
by Brent Yorgey 28 Mar '09

28 Mar '09

On Wed, Mar 25, 2009 at 05:54:17PM +1030, Mark Spezzano wrote: > > What, strictly speaking, is the definition of ”tail recursive” as opposed to > just “recursive”? A recursive function is tail recursive if the final result of the recursive call is the final result of the function itself. If the result of the recursive call must be further processed (say, by adding 1 to it, or consing another element onto the beginning of it), it is not tail recursive. With that said, tail recursion is not that useful of a concept in a lazy language like Haskell. The important concept to know in Haskell is 'guarded recursion', where any recursive calls occur within a data constructor (such as foldr, where the recursive call to foldr occurs as an argument to (:)). This allows the result of the function to be consumed lazily, since it can be evaluated up to the data constructor and the recursive call delayed until needed. -Brent

4 3

Haxr doesn't compile from cabal (HTTP > 4000 breaks it)
by Henning Thielemann 28 Mar '09

28 Mar '09

Most breakage caused by new HTTP package is due to the renaming from Response to Response_String and Request to Request_String. I think it was not a good idea to do that. There could have well be two types named Response from different modules, one with a type parameter and the other one without. Or the parametrized variant could have be named ResponseGeneric or so. That would have allowed packages to work both with version 3001 and 4000.

2 1

Lazy counting and printing
by Anakim Border 28 Mar '09

28 Mar '09

Hi, I have written a code like this: import Control.Monad.State countedRecords :: [Int] -> StateT Int IO [Int] countedRecords [] = return [] countedRecords (r:rs) = do modify (+1) rest <- countedRecords rs return $ r:rs printEven :: [Int] -> StateT Int IO () printEven records = do let even = filter (\n -> n `mod` 2 == 0) records lift $ mapM_ (putStrLn . show) even combine :: [Int] -> StateT Int IO () combine records = countedRecords records >>= printEven main = do let numbers = [1..1000000] count <- execStateT (combine numbers) 0 putStrLn $ "Processed " ++ show count ++ " numbers." My intent is that of processing a large collection of records (in this example, integers) doing two things at once: count their total number and print those that satisfy a certain condition. I would like to keep the definitions of the two functions performing such tasks independent. As a result I've used the State monad to hide intermediate counts. Unfortunately the code above breaks laziness, in that records are first completely counted (and stored in memory) and only then filtered and printed. If I redefine main as: main = do let numbers = [1..] .. i.e. I produce an unbounded number of records, I get a stack overflow. Moreover, I don't like the way countedRecords and printEven are defined, because their type signatures are too "broad". I would prefer them to be: countedRecords :: [Int] -> State Int [Int] printEven :: [Int] -> IO () and let "combine" do some sort of lifting into the StateT monad. Is there any way to perform both operations lazily? Thanks

1 0

ANN: smartword 0.0.0.5 Web based flash card for Word Smart I and II vocabularies
by Ahn, Ki Yung 28 Mar '09

28 Mar '09

Name: smartword Synopsis: Web based flash card for Word Smart I and II vocabularies Version: 0.0.0.5 Homepage: http://kyagrd.dyndns.org/~kyagrd/project/smartword/ Category: Web,Education License: BSD3 License-file: LICENSE Author: Ahn, Ki Yung Maintainer: Ahn, Ki Yung <kya(a)pdx.edu> =================================================================== Web based online study tool for all vocabularies in Word Smart I and II, a poular book series for studying GRE vocabularies. I typed the vocabulary data and wrote the program in 2004, because I got too boring just going over the strange English words. If you don't read Korean, you can just ignore the Korean translation. Source code is outdated, so never even think of using it as a web programming reference. However, it will still be helpful as a neat web application when one tries to squeeze GRE vocabularies into the volatile memory of human brain. Installation: You can either compile CGI binaries with GHC or use Hugs to run lhs as a CGI script. Copy all .cgi files and data directories (book1, book1.ans, book2, book2.ans) into your webserver CGI directory (usually cgi-bin). Usage: If you get it wright the flash card goes away, but if you didn't get it the flash card goes to the bottom of the deck again. So, it won't end until you get all of them right.

1 0

Use unsafePerformIO to catch Exception?
by Xiao-Yong Jin 28 Mar '09

28 Mar '09

Hi, I just feel it is not comfortable to deal with exceptions only within IO monad, so I defined > tryArith :: a -> Either ArithException a > tryArith = unsafePerformIO . try . evaluate and it works quite good as > map (tryArith . (div 5)) [2,1,0,5] evaluates to > [Right 2,Right 5,Left divide by zero,Right 1] However, I guess unsafePerformIO definitely has a reason for its name. As I read through the document in System.IO.Unsafe, I can't convince myself whether the use of 'tryArith' is indeed safe or unsafe. I know there have been a lot of discussion around unsafePerformIO, but I still can't figure it out by myself. Can someone share some thoughts on this particular use of unsafePerformIO? Is it safe or not? And why? Thanks, Xiao-Yong -- c/* __o/* <\ * (__ */\ <

17 49

is there any reason why Language.C.Syntax.AST.CTranslUnit doesn't derive show?
by Anatoly Yakovenko 28 Mar '09

28 Mar '09

is there any reason why Language.C.Syntax.AST.CTranslUnit doesn't derive show? I would like to look at the data structure it generates. It's a lot easier to experiment it when i can write a template C file, print out the AST and then modify that data structure directly, instead of trying to grok the library. Thanks for your great work btw, the parser is pretty sweet. Anatoly

2 2

Parallel term reduction---solution
by John D. Ramsdell 27 Mar '09

27 Mar '09

On February 1, I sent a message to this list asking for advice on how to write a parallel term reduction system. I now have a semi-explicit parallelised version of a term reduction system that makes effective use of multiple CPUs. The enclosed code describes the solution, even though its performance on the example reduction rule does not show a speed up. In the actual reduction system. profiling shows that 99% of the runtime and 98% of the allocations occur in the equivalent of the branch function below, for a representative test case. It's no surprise that just one parallel function, parMap, is all that's needed. John > module Main (main) where > import System.Time (ClockTime(..), getClockTime) > import Data.Tree (Tree(..), flatten) > import Data.Maybe (isNothing) > import Control.Parallel The reduction system takes a rule, a step count, and an initial value, and computes a tree of reductions. > reduce :: (Eq a, Monad m) => (a -> [a]) -> Int -> a -> m (Tree a) > reduce rule limit root = > step rule limit [top] [top] > where > top = Item { item = root, parent = Nothing } The Item data structure stores the information about a reduction step in a form that can be used to construct the final answer as a tree. > data Eq a => Item a > = Item { item :: a, > parent :: Maybe (Item a) } > instance Eq a => Eq (Item a) where > x == y = item x == item y The step function is where nearly all of the time is used. It is called as: step rule limit seen todo where seen is the items already seen, and todo is the items on the queue. The order of the items in the seen list is irrelevant, because the tree is assembled as a post processing step. > step :: (Eq a, Monad m) => (a -> [a]) -> Int -> > [Item a] -> [Item a] -> m (Tree a) > step _ _ seen [] = tree seen > step rule limit seen todo = > combine rule seen limit [] [] (parMap (branch rule seen) todo) Each branch of the rule derivation tree can be evaluated in parallel. Furthermore, most of the checking to see if an item has been seen before can be done in parallel. > branch :: Eq a => (a -> [a]) -> [Item a] -> Item a -> Reduct a > branch rule seen parent = > Reduct parent (seqList kids) > where > kids = [ kid | kid <- rule (item parent), not (dejaVu kid seen) ] This data structure ensures as much computation as possible is done in parallel. > data Eq a => Reduct a = Reduct !(Item a) ![a] Has x been seen before? > dejaVu :: Eq a => a -> [Item a] -> Bool > dejaVu x seen = any (\i-> x == item i) seen Combine the results of one level of the rule derivation tree. The combination function is not associative, so there are no opportunities for parallelisation. > combine :: (Eq a, Monad m) => (a -> [a]) -> [Item a] -> Int -> > [Item a] -> [Item a] -> [Reduct a] -> m (Tree a) > combine rule seen' limit seen todo [] = > step rule limit (seen ++ seen') (reverse todo) > combine _ _ limit _ _ _ > | limit <= 0 = fail "Step limit exceeded" > combine rule oseen limit seen todo (Reduct p kids : reducts) = > combine rule oseen (limit - 1) seen' todo' reducts > where > (seen', todo') = foldr f (seen, todo) kids > f kid (seen, todo) = > if dejaVu kid seen then > (seen, todo) > else > (x:seen, x:todo) > where > x = Item { item = kid, parent = Just p } > seqList :: [a] -> [a] > seqList xs = > loop xs > where > loop [] = xs > loop (y : ys) = seq y (loop ys) > parMap :: (a -> b) -> [a] -> [b] > parMap _ [] = [] > parMap f (x:xs) = > par y (pseq ys (y:ys)) > where > y = f x > ys = parMap f xs The next two functions assemble the answer into a tree. Sequential search is just fine for tree building. > tree :: (Eq a, Monad m) => [Item a] -> m (Tree a) > tree items = > case filter (isNothing . parent) items of > [root] -> return (build items (item root)) > _ -> fail "bad tree" > build :: Eq a => [Item a] -> a -> Tree a > build items root = > Node { rootLabel = root, > subForest = map (build items . item) children } > where > children = filter child items > child i = maybe False ((== root) . item) (parent i) A silly rule > rule :: Int -> [Int] > rule n = filter (>= 0) [n - 1, n `quot` 2, n `quot` 3] > secDiff :: ClockTime -> ClockTime -> Float > secDiff (TOD secs1 psecs1) (TOD secs2 psecs2) > = fromInteger (psecs2 - psecs1) / 1e12 + fromInteger (secs2 - secs1) > main :: IO () > main = > do > t0 <- getClockTime > t <- reduce rule 20000 5000 > let ns = length (flatten t) > t1 <- getClockTime > putStrLn $ "length: " ++ show ns > putStrLn $ "time: " ++ show (secDiff t0 t1) ++ " seconds" The makefile ------------ PROG = parreduce GHCFLAGS = -Wall -package containers -package parallel -threaded \ -fno-warn-name-shadowing -O %: %.lhs ghc $(GHCFLAGS) -o $@ $< all: $(PROG) clean: -rm *.o *.hi $(PROG)

1 0

Haddock GSoC project
by Isaac Dupree 27 Mar '09

27 Mar '09

I'm interested in being a GSoC student, and the Haddock-related tickets looked like a good place to start http://hackage.haskell.org/trac/summer-of-code/ticket/1567 http://hackage.haskell.org/trac/summer-of-code/ticket/1568 http://hackage.haskell.org/trac/summer-of-code/ticket/1569 ... haddock could use some love! And I love documentation. I think I'd start by hacking on some relatively easy Haddock tickets to find my way around the code and the hacking process. Then it might be time to move into one of the bigger projects (I'm tempted to say #1567, "Haddock: allow documentation to propagate between packages"), depending on priorities; probably still working on some smaller but important Haddock tickets. Then it depends how much time we have left in the summer, there's a lot that can be done! - I've hacked on the GHC lexing/parsing code a bit, and I know darcs, haskell, etc., and I've been around watching on mailing-lists since before Haddock 2.x, so I feel like I have a fair amount of context with which to approach this project. What do you think, is this a good project to look towards? What's the next step... should I elaborate my proposal by looking at Haddock tickets and their priorities? But I should have your feedback first; what do the mentors, or the Haskell community, want most to be improved about Haddock? -Isaac

3 4

Re: Exception handling in numeric computations
by John Lato 27 Mar '09

27 Mar '09

> > Message: 8 > Date: Fri, 27 Mar 2009 10:41:05 -0700 > From: Jonathan Cast <jonathanccast(a)fastmail.fm> > Subject: Re: [Haskell-cafe] Re: Exception handling in numeric > computations > To: Gregory Petrosyan <gregory.petrosyan+haskell(a)gmail.com> > Cc: haskell-cafe(a)haskell.org > Message-ID: <1238175665.20367.12.camel@jcchost> > Content-Type: text/plain; charset=utf-8 > > On Fri, 2009-03-27 at 20:38 +0300, Gregory Petrosyan wrote: >> On Fri, Mar 27, 2009 at 7:31 PM, Donn Cave <donn(a)avvanta.com> wrote: >> > Quoth John Lato <jwlato(a)gmail.com>, >> > >> >> An exception is caused by some sort of interaction with the run-time >> >> system (frequently a hardware issue). The programmer typically can't >> >> check for these in advance, but can only attempt to recover after >> >> they've happened. >> >> >> >> An error is some sort of bug that should be fixed by the programmer. >> > >> > I have never felt that I really understood that one. >> >> Me too :-) >> >> BTW, John, how often do you encounter _hardware_ issues compared to "errors"? > > Can't speak for anyone else, but I usually encounter hardware issues > just before I replace the hardware... This is getting confusing with two "John"'s replying. For myself, I do not encounter hardware issues often at all (unless you count buggy drivers). They are the exceptional condition. > >> Is an "out of memory" thing an error or exception? >> You will say "exception, for sure", wouldn't you? :-) > > No. GHC possesses an out-of-memory exception that (IIRC) it never > throws, because it's simply not worth trying to recover from heap > exhaustion. Maybe 20 years ago it was, but these days a program that > manages to exhaust space is almost certainly either buggy or poorly > optimized. I would have said exception, although I agree with the assessment that it's not worth trying to recover from. > > An `error' is any condition where the correct response is for the > programmer to change the source code :) > >> And if it is a >> result of applying >> known-to-be-very-memory-hungry algorithms to non-trivial input? Looks like >> programmer's error, doesn't it? > > See above. Due to their brevity, I sometimes find it difficult to understand Jonathan's replies. So at the risk of putting words in his mouth, I will take an attempt to explain this further. Keep in mind these are my words, not his, and it's possible I have completely misunderstood his point since I've only been using Haskell intensively for about a year (and I have no formal CS training, and other biographical points apply as well). Running out of memory is an exceptional condition. Doing something that is likely to cause memory exhaustion is a programming error, because it was the wrong solution to the problem. Memory exhaustion, the exceptional condition, is an end result of making the programming error. In this case (but not all), it is possible to treat the symptoms by handling the exception, but the general solution is to avoid the problem in the first place. > >> And I think I can provide lots of similar examples. >> >> If there exists separation between errors and exceptions, it should be >> very strong >> and evident — otherwise "casual programmers" like myself will need to >> stare at the >> ceiling every time they write something to decide what suits best. > I am not sure when I would every throw an exception in Haskell code, short of re-raising from a handler. Things that I would have used exceptions for in C-sharp can be handled explicitly with Maybe or Either, a style that I greatly prefer. John > Protip: try pacing instead of staring at the ceiling. > > jcc >

1 0