November 2007 - Haskell-Cafe

Stream fusion for Hackage
by Don Stewart 21 Nov '07

21 Nov '07

Just a quick announce: the stream fusion library for lists, that Duncan Coutts, Roman Leshchinskiy and I worked on earlier this year is now available on Hackage as a standalone package: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion-0.… As described in the recent paper: "Stream Fusion: From Lists to Streams to Nothing at All" Duncan Coutts, Roman Leshchinskiy and Don Stewart. ICFP 2007 This is a drop-in replacement for Data.List. Haddocks here, http://code.haskell.org/~dons/doc/stream-fusion/ (but note the interface is exactly the same as the Data.List library) You might expect some small percent performance improvement for list heavy programs, using ghc 6.8 and this list library with -O2 (use -ddump-simpl-stats and look for: STREAM stream/unstream fusion messages, indicating your intermediate lists are getting removed. To get an idea of what is happening, consider this list program: foo :: Int -> Int foo n = sum (replicate n 1) Compiled with ghc-6.8.1 -O2 -ddump-simpl Normally, as sum is a left fold, an intermediate lazy list is allocated between the call to sum and replicate, as GHC currently does: foo :: Int# -> Int# foo n = Data.List.sum (case <=# n 0 of False -> go n True -> []) where go :: Int# -> [Int] -- intermediate list! go n = case <=# n 1 of False -> 1 : (go (n -# 1)) True -> [1] By using Data.List.Stream instead, you get a strict fused loop instead, with no intermediate structure allocated: loop_sum :: Int# -> Int# -> Int# loop_sum k n = case <=# n 0 of False -> loop_sum (k +# 1) (n -# 1) True -> k foo :: Int# -> Int# foo n = loop_sum 0 n This is a the halfway mark before porting other sequence types -- especially Data.ByteString -- over to the full stream fusion model (in particular, strict bytestrings will benefit a lot, due to the O(n) cost of intermediate bytestrings being removed). The stream fusion types and combinators are also available in stripped down form in the mlton sml compiler's extended prelude. Enjoy. -- Don

9 11

Re: ANNOUNCE: fixpoint 0.1
by Bertram Felgenhauer 21 Nov '07

21 Nov '07

[redirecting from haskell@...] apfelmus wrote: [...] > I wonder whether a multi parameter type class without fundeps/associated > types would be better. > > class Fixpoint f t where > inject :: f t -> t > project :: t -> f t > [...] > Interestingly, this even gives slightly shorter type signatures > > cata :: Fixpoint f t => (f s -> s) -> t -> s > size :: (Fixpoint f t, Foldable f) => t -> Int size can't be used now though, because there is no way to infer f. Bertram

3 5

Knot tying vs monads
by John D. Ramsdell 21 Nov '07

21 Nov '07

This is another Haskell style question. I had some trouble with the pretty printer that comes with GHC, so I translated one written in Standard ML. I have already translated the program into C, so rewriting it in Haskell was quick and easy for me. The Standard ML version uses a reference cell to keep track of the space available on a line. I threaded the value of the reference cell through the computation using a where clause to define two mutually recursive equations. The fixed point implicit in the where clause ties the knot in the circular definitions in a way that allows the output string to be efficiently computed front to back. I showed the code to a colleague, who found the circular definitions opaque. He suggested a better style is to use monads, and describe the computation in a mode that is closer to its origin form in Standard ML. What style do to you prefer, a knot-tying or a monad-based style? I have enclosed the pretty printer. The printing function is the subject of the controversy. John A simple pretty printer The alogithm is by Lawrence C. Paulson, who simplified an algorithm by Derek C. Oppen. Derek C. Oppen, Prettyprinting, ACM Transactions on Programming Languages and Systems, Vol 2, No. 4, October 1980, Pages 465-483. A pretty printer based on ML programs with the following copyright (**** ML Programs from Chapter 8 of ML for the Working Programmer, 2nd edition by Lawrence C. Paulson, Computer Laboratory, University of Cambridge. (Cambridge University Press, 1996) Copyright (C) 1996 by Cambridge University Press. Permission to copy without fee is granted provided that this copyright notice and the DISCLAIMER OF WARRANTY are included in any copy. DISCLAIMER OF WARRANTY. These programs are provided `as is' without warranty of any kind. We make no warranties, express or implied, that the programs are free of error, or are consistent with any particular standard of merchantability, or that they will meet your requirements for any particular application. They should not be relied upon for solving a problem whose incorrect solution could result in injury to a person or loss of property. If you do use the programs or functions in such a manner, it is at your own risk. The author and publisher disclaim all liability for direct, incidental or consequential damages resulting from your use of these programs or functions. ****) > module Pretty(Pretty, pr, blo, str, brk) where > data Pretty > = Str !String > | Brk !Int -- Int is the number of breakable spaces > | Blo ![Pretty] !Int !Int -- First int is the indent, second int > -- is the number of chars and spaces for strings and breaks in block Constructors Strings > str :: String -> Pretty > str = Str Break points > brk :: Int -> Pretty > brk = Brk Indentation blocks > blo :: Int -> [Pretty] -> Pretty > blo indent es = > Blo es indent (sum es 0) > where > sum [] k = k > sum (e:es) k = sum es (size e + k) > size (Str s) = length s > size (Brk n) = n > size (Blo _ _ n) = n Pretty prints the constructed object > pr :: Int -> Pretty -> ShowS > pr margin e s = > s1 > where > (_, s1) = printing margin [e] margin 0 (margin, s) The state of the computation is maintained as a pair consisting of an integer and a string. The integer is the number of unused character positions in the current line of output. The printer adds content to the front of the given string. > printing :: Int -> [Pretty] -> Int -> Int -> (Int, String) -> (Int, String) > printing _ [] _ _ p = p > printing margin (e:es) blockspace after (space, s) = > (space1, s1) > where > (space2, s1) = -- Result of first item > case e of > Str str -> -- Place a string > (space - length str, showString str s2) > Brk n -> -- Place breakable space > if n + breakdist es after <= space then > blanks n (space, s2) -- Don't break > else > (space3, showChar '\n' s3) -- Break > where > (space3, s3) = > blanks (margin - blockspace) (margin, s2) > Blo bes indent _ -> -- Place a block > printing margin bes (space - indent) > (breakdist es after) (space, s2) > (space1, s2) = -- Result of the remaining items > printing margin es blockspace after (space2, s) Find the distance to the nearest breakable space. > breakdist :: [Pretty] -> Int -> Int > breakdist (Str s : es) after = length s + breakdist es after > breakdist (Brk _ : _) _ = 0 > breakdist (Blo _ _ n : es) after = n + breakdist es after > breakdist [] after = after Place spaces > blanks :: Int -> (Int, String) -> (Int, String) > blanks n (space, s) > | n <= 0 = (space, s) > | otherwise = blanks (n - 1) (space - 1, showChar ' ' s)

5 14

Re: [Haskell] recursive deriving
by Duncan Coutts 21 Nov '07

21 Nov '07

On Tue, 2007-11-20 at 19:18 -0500, Alex Jacobson wrote: > When you want automated deriving of show/read etc., you need all the > components of your type also to be instances of show/read but you won't > want to *require* them to be automatically generated verions. > > Standalone deriving does the wrong thing here. Standalone deriving > should not cause an overlapping instance error if someone derives an > instance manually. Instead, the manually derived instance should be > treated as more specific and win out. > > The other part of this problem is that you can't do automatic recursive > deriving and this results in a ridiculous amount of boilerplate. I know > some people have a theory that they want to avoid accidentally creating > instances for things that shouldn't have them, but the solution to that > is probably to add some declaration for types that prohibits automatic > deriving for those types. The 99% case is that automatic deriving is ok. > > Proposed syntax: > > derive instance Show T recursively > data T = T no-deriving (Ord,Eq) I would expect that if the data constructor for T is not exported then standalone deriving should not work. However this appears not to be the case which breaks module abstraction. Foo.hs: module Foo ( T, t ) where data T = T t = T Bar.hs: import Foo deriving instance Eq T $ ghci Bar.hs -XStandaloneDeriving [1 of 2] Compiling Bar ( Bar.hs, interpreted ) [2 of 2] Compiling Main ( Baz.hs, interpreted ) Ok, modules loaded: Bar, Main. *Main> t == t True You could write that Eq instance by hand since they do not have access to the T constructor, then StandaloneDeriving should not be able to so either. I think it's a design flaw in standalone deriving. Does anyone else agree? Should we file a bug report? Duncan

3 2

SingHaskell 2007, November 28 2007
by Tom Schrijvers 21 Nov '07

21 Nov '07

We're pleased to invite you to SingHaskell: What is SingHaskell? Sing(apore)Haskell is a Haskell (and related languages) meeting in Singapore. The meeting is organized by Tom Schrijvers and Martin Sulzmann and will be hosted by the National University of Singapore. Date and location Sing(apore)Haskell takes place on Wed 28 Nov 2007 (right before APLAS'07 http://flint.cs.yale.edu/aplas2007/) The meeting will be held somewhere on the National University of Singapore campus (details will follow shortly). Let Tom or Martin know if you are interested in coming. Either to attend the meeting or even give a talk. For more information and tentaive talks: http://taichi.ddns.comp.nus.edu.sg/taichiwiki/SingHaskell2007 Best regards, Martin Sulzmann and Tom Schrijvers -- Tom Schrijvers Department of Computer Science K.U. Leuven Celestijnenlaan 200A B-3001 Heverlee Belgium tel: +32 16 327544 e-mail: tom.schrijvers(a)cs.kuleuven.be url: http://www.cs.kuleuven.be/~toms/

2 1

Best way to format a number
by Maurício 20 Nov '07

20 Nov '07

Hi, I would like to get a string for a number using always 2 digits (i.e., 75 would be "75", 3 would became "03"). What is the best way to do that? I tried printf "%02d\n" 3 which gives me the correct string, but ghci always ends that call with a *** Exception: Prelude.undefined message. What else should I try? Can Text.PrettyPrint do that? Thanks, Maurício

3 2

Re: Tetris
by nick ralabate 20 Nov '07

20 Nov '07

Speaking of Tetris and Space Invaders, you might be interested in this project: http://www.geocities.jp/takascience/haskell/monadius_en.html It's a clone of Gradius written in Haskell. -Nick

3 4

timeout and waitForProcess
by Tim Bauer 20 Nov '07

20 Nov '07

Does anyone know if the new System.Timeout.timeout combinator can wakeup from System.Process.waitForProcess? I have not been able to make this work, and it appears as though the timeout exception is thrown only after waitForProcess returns normally (if it ever does). I am using Windows and GHC 6.8.1. import Control.Concurrent import System.IO import System.IO.Error(isEOFError) import System.Process(runInteractiveProcess, waitForProcess, ProcessHandle) import System.Timeout(timeout) halfSecond = 500000 example = timeout halfSecond sleepy sleepy = do (inp,out,err,pid) <- runInteractiveProcess "sleep.exe" ["10"] Nothing Nothing forkOS (ioGobbler out) forkOS (ioGobbler err) waitForProcess pid -- CAN timeout INTERRUPT THIS? return "PROCESS FINISHED" ioGobbler :: Handle -> IO () ioGobbler h = catch (ioDiscarder h) eofHandler ioDiscarder :: Handle -> IO () ioDiscarder h = do hGetChar h >> ioDiscarder h eofHandler :: IOError -> IO () eofHandler e | isEOFError e = return () | otherwise = ioError e Executing `example' from ghci will spawn (sleep.exe 10) which sleeps for 10 seconds. The timeout should happen in half a second (giving the thread time to get blocked into waitForProcess). However, instead, things block for ten seconds (until sleep.exe exits and waitForProcess returns normally). While a workaround is to spin and sleep with the getProcessExitCode and threadDelay, it seems like an inappropriate hack. The documentation for timeout lists some functions that are interruptible, but is not mean to be a complete list. Thanks all, - Tim -- View this message in context: http://www.nabble.com/timeout-and-waitForProcess-tf4847280.html#a13868823 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 1

Re: Exposed module still hidden, why?
by Olivier Boudry 20 Nov '07

20 Nov '07

On 11/20/07, Greg Fitzgerald <garious(a)gmail.com> wrote: > > Using GHC 6.8.1 on Windows XP, after having used ghc-pkg to expose ' > directory-1.0.0.0', I am getting an error when I build haddock that says > the package is hidden. When I type "ghc-pkg list", the package is not in > parenthesis. Typing "ghc -v" says that it is using the file from > "C:\ghc\ghc- 6.8.1\package.conf". That package.conf file has the > 'exposed' set to True for that file. Why does GHC still think the package > is hidden? Hi Greg, You need to add "directory" to the Build-Depends instruction in the cabal file. The base package has been split into separate modules in 6.8.1. Build-Depends: base, directory Look at this: http://groups.google.com/group/fa.haskell/msg/17a78c120ae26514 Cheers, Olivier.

2 1

-O2 bug in GHC 6.8.1?
by Brad Clow 20 Nov '07

20 Nov '07

I upgraded from GHC 6.6.1 to 6.8.1 and around that time I noticed that the output from an app I am working on changed. I have distilled the code down to the following example that produces different output depending on whether it is compiled with -O2 or not: main = do let (T x) = read "T 3" print $ f x print $ g x data T = T Int deriving (Read, Show) f x = truncate $ 2000 / fromIntegral ((x * 25) + 10) g :: Int -> Int g x = f x Here is the transcript from a shell (example code is saved in test.hs): $ ghc --make test.hs [1 of 1] Compiling Main ( test.hs, test.o ) Linking test ... $ ./test 23 23 $ rm test.hi test.o test $ ghc -O2 --make test.hs [1 of 1] Compiling Main ( test.hs, test.o ) Linking test ... $ ./test 23 24 It is a little disconcerting that -O2 changes the output. :-) Regards brad -- www.scoodi.com Contribute things you don't need and find things you do, all within your local community.

7 8