- Haskell-Cafe - Haskell.org

Basic problem in Haskell language design?
by Nicu Ionita 02 Mar '09

02 Mar '09

Hi, Today I found the following problem when writing a simple function: > -- Whole info from a word8 list to moves > movesFromWord8s :: [Word8] -> [Move] > movesFromWord8s (f:t:ws) = (f, t) : movesFromWord8s ws > moverFromWord8s _ = [] Here I made a small typo in the second equation, writing "mover..." instead of "moves..." for the name of the declared function. Of course this is an error, because I have non-exhaustive patterns in the function movesFromWord8s. But the compiler (here GHC 6.8.2 on WinXP) has in principle no chance to detect this mistake, I saw it only in QuickCheck (aka at run-time). I think this is a basic problem with the language design. In small programs it's not so bad, but in large ones this could be. What do you think about it? Are there possible solutions or workarounds? Nicu Ionita

6 6

ANNOUNCE: tar 0.3.0.0
by Duncan Coutts 02 Mar '09

02 Mar '09

All, I'm pleased to announce a major new release of the tar package for handling ".tar" archive files. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/tar This release has a completely new and much improved API. See the hackage page for the API documentation. There are high level "all in one" functions for extracting or creating .tar files. More interestingly, it is easy to make variants by composing a pipeline. For example extracting a ".tar.gz" file is just: > Tar.unpack dir . Tar.read . GZip.decompress =<< BS.readFile tar Or creating a ".tar.bz2" file: > BS.writeFile tar . BZip.compress . Tar.write =<< Tar.pack base dir In addition it provides a full api for inspecting and constructing tar files without having to pack or unpack to local files. The functions are lazy which allows large archives to be processed in constant space. It is based on the tar handling code that has been in use in the cabal-install program for the last year or so. It has been tested on a large number of real world .tar.gz files so compatibility should be pretty good. There is also an 'htar' tool which is essentially a demo program for the tar library. It implements the common subset of the command line interface of the standard tar program, including gzip and bzip compression. Thanks to Christian Maeder for feedback on pre-release versions. Duncan

2 2

shuffle error
by friggin friggin 02 Mar '09

02 Mar '09

http://hpaste.org/fastcgi/hpaste.fcgi/view?id=1989#a1990 Is the algorithm wrong ar am I using it wrong? Also, is the second argument to shuffle supposed to eb random numbers, ie the function should be used in the IO Monad?

4 3

ANNOUNCE: The Industrial Haskell Group
by Duncan Coutts 02 Mar '09

02 Mar '09

We are pleased to announce the creation of the Industrial Haskell Group (IHG). The IHG is an organisation to support the needs of commercial users of the Haskell programming language. For more information, please see http://industry.haskell.org/ Currently, the main activity of the IHG is a collaborative development scheme, in which multiple companies fund work on the Haskell development platform to their mutual benefit. The scheme has started with three partners of the IHG, including Galois and Amgen. More details are available at http://industry.haskell.org/collab If your company is interested in joining then please e-mail info(a)industry.haskell.org -- Duncan Coutts, Haskell Consultant Well-Typed LLP, http://www.well-typed.com/

1 0

How to work with date?
by Magicloud Magiclouds 02 Mar '09

02 Mar '09

Hi, I am working on some calendar GUI thing. And I cannot find a library to operate the "date". Like, when `now <- getZonedTime`, how could I get all the dates of the week. Or when I got `today`, how to get the date of 10 days ago? Thanks. -- 竹密岂妨流水过山高哪阻野云飞

3 3

Assignment of grayCode
by Anonymous Anonymous 02 Mar '09

02 Mar '09

Hello, I'm working on a project for my university. But I do not understand the assignment. It asks me to write a function that does the following: grayCode :: Int -> ([Char] -> Int, Int -> [Char]) well in my opinion this assignment tells me to write some function that gets one input (an integer) and result two functions in one tuple. One function goes from [Char] to Int and the other one goes from Int to [Char]. But in my opinion this function will stay the same forever... am I mistaken? The assignment should be: Write an efficient code grayCode :: Int -> ([Char] -> Int, Int -> [Char]) that, for values between 2 and 36 (included), creates a Gray Code. That is, a tuple of two functions. Thanks!

3 2

major speed improvement: regex-tdfa reaches 1.0.0
by ChrisK 02 Mar '09

02 Mar '09

Announcing the version 1.0.0 release of regex-tdfa. I am proud of this release. This is not just a bug fix release. It is a serious improvement in the asymptotic running time. The previous versions allowed bad combinations of pattern and searched text length to scale badly in the length of the text. Previously the worst case for text of length N was O(N^3). The new worst case asymptotic runtime scaled as O(N). There is never any backtracking. And the worst case storage space is independent of N. The package is on hackage at http://hackage.haskell.org/cgi-bin/hackage-scripts/package/regex-tdfa The darcs repository is at http://darcs.haskell.org/packages/regex-unstable/regex-tdfa/ All non-overlapping matches are found and returned, along with all captured (parenthesized) subexpressions. The result is precisely what Posix extended regular expressions are supposed to return. To be concrete, consider example text with length of N of (2^n)+2: > longInput = replicate (2^n) 'a' ++ "bc" And define 4 worst-case-scenario patterns. I wrote the code and I know how to kill it: > wcs0 = "a*b" > wcs1 = "a*c" > wcs2 = "(a|aa)*b" > wcs3 = "(a|aa)*c" wcs0 is easy. wcs1 causes the old code to backtrack. wcs2 causes the old code's storage to scale as O(N). wcs3 causes both backtracking and O(N) storage with the old code. The old code's time scales as O(N) for wcs0, O(N^2) for wcs1 and wcs2, and O(N^3) for wcs3. The new code is always O(N). The actual timings for the old code on my G4 laptop for wcs on 2^8 and 2^9 and 2^10 are: Reason:compare-tdfa chrisk$ time ./Test-TDFA-np wcs3 8 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA-np wcs3 8 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(257,1)),(1,(-1,0))]] 263,776,756 bytes allocated in the heap user 0m1.017s sys 0m0.058s Reason:compare-tdfa chrisk$ time ./Test-TDFA-np wcs3 9 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA-np wcs3 9 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(513,1)),(1,(-1,0))]] 1,998,647,452 bytes allocated in the heap user 0m7.083s sys 0m0.289s Reason:compare-tdfa chrisk$ time ./Test-TDFA-np wcs3 10 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA-np wcs3 10 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(1025,1)),(1,(-1,0))]] 15,653,277,200 bytes allocated in the heap user 0m53.350s sys 0m2.056s The doubling of length is causing a nearly eight-fold time increase. The heap allocation is also increasing nearly eight-fold. The new code with the same input pattern and texts gives: Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 8 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 8 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(257,1)),(1,(-1,0))]] 2,135,324 bytes allocated in the heap user 0m0.017s sys 0m0.017s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 9 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 9 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(513,1)),(1,(-1,0))]] 3,588,656 bytes allocated in the heap user 0m0.024s sys 0m0.017s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 10 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 10 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(1025,1)),(1,(-1,0))]] 6,345,436 bytes allocated in the heap user 0m0.038s sys 0m0.018s Note that the heap allocation for the 1026 character example above is 2466 times less than the old code. That was too fast to prove the scaling, so take more input: Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 20 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 20 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(1048577,1)),(1,(-1,0))]] 5,708,574,848 bytes allocated in the heap user 0m26.023s sys 0m0.985s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 wcs3 21 +RTS -sstderr 2>&1 | head -4 ./Test-TDFA2-0.99.19-np2 wcs3 21 +RTS -sstderr Test for [Char] Right [array (0,1) [(0,(2097153,1)),(1,(-1,0))]] 11,416,354,056 bytes allocated in the heap user 0m52.656s sys 0m1.985s The length and time both doubled, as did the heap allocation. And the new code has searched two million characters in the time the old code searched one thousand. How about away from the worst case scenario? On the testing suite the new code is running slightly slower: Reason:compare-tdfa chrisk$ time ./Test-TDFA-np -r 1 100 > /dev/null user 0m4.841s sys 0m3.019s Reason:compare-tdfa chrisk$ time ./Test-TDFA2-0.99.19-np2 -r 1 100 > /dev/null user 0m5.970s sys 0m3.012s So that is an increase of execution time of 14%. This small dip in performance might be reclaimable with more optimization. I think the gain in worst case performance already offsets the slight cost. The code for String is complete. The strict and lazy bytestrings and the (Seq Char) are currently using the String code for matching. This will be improved in a future release. Cheers, Chris The small print: regex-tdfa will still behave badly in space and time if given a pathological pattern, e.g. "(((a|aa){0,100}){0,100}){0,100}". But, I am hopeful than I can improve regex-tdfa to behave well with the patterns like this one. That is my vague goal for a future version 2.0.0 release. The very small print: I have been using ghc-6.10.1, and I think I have carried over cabal switches to make ghc-6.8.3 also work. The library probably can work with ghc-6.6, but the cabal file will need editing first as well as fixes to "Text.Regex.TDFA.NewDFA.copySTU".

3 2

A foray into type-level programming, and getting stuck
by George Pollard 02 Mar '09

02 Mar '09

Okay, so I've written a small library to generalize 'fst' and 'snd' to arbitrary tuples, but I'd like to extend it a bit. I'm using the type-level library to do the thinking :) Imports and defines first: > {-# LANGUAGE UnicodeSyntax, MultiParamTypeClasses, > FunctionalDependencies, FlexibleInstances, FlexibleContexts, > UndecidableInstances, DeriveDataTypeable, OverlappingInstances, > ScopedTypeVariables #-} > import Prelude hiding ((-),Eq) > import qualified Prelude as P > import Data.TypeLevel.Num.Sets > import Data.TypeLevel.Num.Reps > import Data.TypeLevel.Num.Aliases > import Data.TypeLevel.Bool > import Data.TypeLevel.Num.Ops > import Data.Typeable I start by requiring that if you can access element 'n', you should be able to access element 'n-1'. > class (ImplementsPrev t n a) ⇒ Nthable t n a | t n → a where > nth ∷ n → t → a > > class (Pos n) ⇒ ImplementsPrev t n a > instance (Pred n n', Nthable t n' a') ⇒ ImplementsPrev t n a > instance ImplementsPrev t D1 a So, this is a simple induction. Testing it with the nthable instances confirms that it works; removing either of the first two lines stops the code from compiling, hurrah! > instance Nthable (a,b,c) D1 a where nth _ (a,_,_) = a > instance Nthable (a,b,c) D2 b where nth _ (_,b,_) = b > instance Nthable (a,b,c) D3 c where nth _ (_,_,c) = c Now, I have heard talk/suggestions of revamping tuples in Haskell to a more flexible system. Perhaps we would like to do it like this (modulo strictness annotations): > data (Nat n) ⇒ Tuple n a b = Tuple a b > deriving (Show,Read,Typeable,P.Eq,Ord) > infixr 0 `comma` > -- comma :: a -> (b ~> c) -> (a ~> (b ~> c)) -- to investigate > comma ∷ (Succ n n') ⇒ a → Tuple n b c → Tuple n' a (Tuple n b c) > x `comma` y = Tuple x y > empty ∷ Tuple D0 () undefined > empty = Tuple () undefined Thus, we can create, e.g. (1 `comma` 2 `comma` empty). Now, I'd like to be able to write Nthable instances, so I start with the base case: > instance (n :>=: D1) ⇒ Nthable (Tuple n a b) D1 a where > nth _ (Tuple a _) = a This works well. However, I am really stuck on the instance for the inductive case. My first idea was this: > instance (Pred x x', Nthable b x' r) ⇒ Nthable (Tuple n a b) x r where > nth _ (Tuple _ b) = nth (undefined ∷ x') b But this doesn't work, muttering about IncoherentInstances and hidden datatypes from the type-level library. So, I turn to Haskell café for help :)

3 3

Re: [Haskell-cafe] Basic problem in Haskell language design?
by Daniel Schüssler 02 Mar '09

02 Mar '09

Hi, On Sunday 01 March 2009 14:26:42 Nicu Ionita wrote: > [...] > movesFromWord8s (f:t:ws) = (f, t) : movesFromWord8s ws > moverFromWord8s _ = [] > [...] > Are there possible solutions or workarounds? for the particular problem of having to repeat the function name, you could use "case": movesFromWord8s x = case x of f:t:ws -> (f, t) : movesFromWord8s ws _ -> [] (at the cost of one extra variable name :)) Greetings, Daniel

1 0

Take a break: write an essay for Onward! Essays
by Simon Peyton-Jones 02 Mar '09

02 Mar '09

Friends Writing papers is fun, we mostly only get to write one *kind* of paper. Here is an opportunity to write something in a totally different style: Submit an essay to Onward! Essays Deadline: 20 April 2009 http://onward-conference.org/calls/foressays An Onward! essay is a thoughtful reflection upon software-related technology. Its goal is to help the reader to share a new insight, engage with an argument, or wrestle with a dilemma. A successful essay is a clear and compelling piece of writing that explores a topic important to the software community. The subject area should be interpreted broadly, including the relationship of software to human endeavours, or its philosophical, sociological, psychological, historical, or anthropological underpinnings. An essay can be an exploration of its topic, its impact, or the circumstances of its creation; it can present a personal view of what is, explore a terrain, or lead the reader in an act of discovery; it can be a philosophical digression or a deep analysis. It can describe a personal journey, perhaps that by which the author reached an understanding of such a topic. I'm the program chair, and I'd love to get submissions from the POPL/ICFP/types community. Reflections on programming languages, types, testing, verification, software engineering, compilers, society, ... you name it. Anything to do with software. NB: Onward! is co-located with OOPSLA, but they are otherwise unrelated. OO is fine, but not required. Don't forget: 20th April. Simon PS: To get your imagination going, here are a couple of (strongly-contrasting) past essays: * Dan Grossman "The transactional memory / garbage collection analogy" http://www.cs.washington.edu/homes/djg/papers/analogy_oopsla07.pdf * Dick Gabriel "Designed as designer" http://dreamsongs.org/DesignedAsDesigner.html

2 1