September 2009 - Haskell-Cafe

QuickCheck Questions
by Yusaku Hashimoto 28 Sep '09

28 Sep '09

Hello, I recently worked with QuickCheck for a while, But I still can't handle it well, And a few questions come to my mind. 1. How to find properties In QuickCheck examples on the codes or the papers, they find good properties easily. How did they find these properties? What property can make us believed its implementation is collect? 2. Property driven developments But finally, I could find some patterns of the properties. For example, occasionally, their shape is like unF . f == id or unF . f == Just I thought it could be applied to writing parser, and lead me to "Property Driven Developments." I tried writing S-expression parser in this way. First, I defined my property as parseSexpr . prettySexpr == Just where parseSexpr :: String -> Maybe Sexpr, prettySexpr :: Sexpr -> String. As you see, I should write printer before parser. Fortunately writing such printer for S-expr is easy, but I don't know if what I did is right. Do you think I wasted times? Have you ever tried PDD? And has it worked? If you have experience with TDD, how do you think about PDD? If you have any answers in any questions above, please tell me them. Thanks in advance. Cheers -nwn

8 11

GADT pattern match in non-rigid context
by João Paulo 28 Sep '09

28 Sep '09

Dear all, The following is a (I'm afraid too large!) fragment of a program implementing a GADT-based generic zipper: ********************************************** data Zipper path where Zipper :: hole -> Context (Up (left, hole, right) up) -> Zipper (Up (left, hole, right) up) data Context path where ContTop :: Context (Up (Top, a, Top) Top) Cont :: Left l (h -> r) -> Right r h_parent -> Context (Up (l_parent, h_parent, r_parent) path) -> Context (Up (l, h, r) (Up (l_parent, h_parent, r_parent) path)) data Up a b data Top data Left contains expects where LeftUnit :: a -> Left Top a LeftCons :: Left c (b -> a) -> b -> Left (c -> b) a data Right provides final where RightNull :: Right final final RightCons :: b -> Right a final -> Right (b -> a) final data Erase c a = forall b. (Typeable b) => Erase (c b a) ff :: (Typeable l, Data h, Typeable r, Typeable up) => Zipper (Up (l, h, r) up) -> Erase Left h ff (Zipper h c) = (gfoldl erased_left_cons erased_left_unit h) gg :: (Typeable l_down, Typeable h_down, Data h) => Erase Left h -> Maybe (Left (l_down -> h_down) h) gg (Erase l) = cast l move_down :: (Typeable l_down, Typeable h_down, Typeable l, Data h, Typeable r, Typeable up) => Zipper (Up (l, h, r) up) -> Maybe (Zipper (Up (l_down, h_down, h) (Up (l, h, r) up))) move_down z@(Zipper h c) = case gg (ff z) of # Just (LeftCons l' h_down) -> Just (Zipper h_down (Cont l' RightNull c)) Nothing -> Nothing instance Typeable Top where typeOf _ = mkTyConApp (mkTyCon "Top") [] instance Typeable2 Left where typeOf2 _ = mkTyConApp (mkTyCon "Left") [] instance Typeable2 Up where typeOf2 _ = mkTyConApp (mkTyCon "Up") [] erased_left_cons :: (Typeable b) => Erase Left (b -> a) -> b -> Erase Left a erased_left_cons (Erase c) b = Erase (LeftCons c b) erased_left_unit :: a -> Erase Left a erased_left_unit a = Erase (LeftUnit a) ********************************************** Compiling it with GHC 6.10.4 yelds the error: *** GADT pattern match in non-rigid context for `LeftCons' Solution: add a type signature In the pattern: LeftCons l' h_down [marked with # in the code] *** The suggestion is quite clear :D (in fact, I think this compiler suggestion is the result of previous interactions in this mailing list) The thing is that, in order to add a type signature to the suggested pattern, I believe I have to use the type variables in the signature of function 'move_down' (which I don't think is possible); Can anyone help me with this? I believe this code has compiled before, on previous GHC versions... Thank you very much, João -- João Paulo Fernandes Universidade do Minho www.di.uminho.pt/~jpaulo

2 1

16 bit floating point data in Haskell?
by Olex P 28 Sep '09

28 Sep '09

Hi guys, Do we have anything like half precision floats in Haskell? Maybe in some non standard libraries? Or I have to use FFI + OpenEXR library to achieve this? Cheers, Oleksandr.

8 10

unicode text libraries
by Titto Assini 28 Sep '09

28 Sep '09

Hi, I am looking for an unicode strings library, I found on hackage: http://hackage.haskell.org/package/compact-string http://hackage.haskell.org/package/text They both look solid and functionally complete so ... I don't know which one to use :-) As I am sure I am not the first one facing this choice, may I ask which one you preferred and why? Thanks titto -- Pasqualino "Titto" Assini, Ph.D. http://quicquid.org/

3 2

ANN: ListTree 0.1
by yairchu＠gmail.com 28 Sep '09

28 Sep '09

Hi, I am pleased to announce the release of ListTree. ListTree is a package for combinatorial search and pruning of trees, and should be useful for problems such as those in Google Code Jam (where I, and possibly others* could make use of it), but possibly could even be useful for real applications! It offers BFS, DFS, Best-First-Search, Branch-And-Bound pruning, and more. The trees it works on are not those from Data.Tree, but rather monadic lists of a list monad (ListT []), which is an alternative that has the advantages of working with standard MonadPlus or List operations like takeWhile etc, and where consumption is a monadic action, which allows keeping state required for branch-and-bound (the bound) etc. This would be best explained with an example. Google Code Jam 2009 Round 2 Problem C: Given the prices at 25 time points for 16 stocks (in the small input), split the stocks into several groups, where in each group, the line- plots of its stocks' prices do not intersect or touch. Your mission is to find the minimum number of groups necessary. I will present an inefficient (best one I could come up with during the compo) solution that can solve their small input (it cannot solve the large input of a 100 stocks): * Search the space of all possible splits into groups of the stocks * Prune this search by cutting branches where the plots of two stocks in the same group intersect * Use "Branch and Bound". For each node, calculate a lower and upper bound. Lower bound is number of groups so far, and large bound is number of groups plus number of remaining items to place in group (each one may require a new group). Keep the lowest upper bound encountered, and prune all subtrees with a lower bound larger or equal to it. Code for this solution below. Using ListTree, the code is as modular as the algorithm description above, and there's a function to perform branch-and-bound. One problem with my package (which I'll attempt fixing), however, is speed. I haven't used it during the competition, and the quick and dirty, less modular code, that I coded in the competition, which performs exactly the same algorithm, runs a 100 times faster! Both are fast enough, but this is still troubling. I guess I should look into "Stream Fusion" to try and make my package faster. And the example's code below: import Control.Monad.Identity import Control.Monad.ListT -- from "List", not mtl import Control.Monad.State import Control.Monad.Trans import Data.Array import Data.List.Class (cons, execute) import Data.List.Tree import Data.Maybe -- search tree for all possible splits to separate groups -- each node has the same groups of its parent with a new element added to a group -- or as the sole element of a new group -- the new element is the first element of the first group searchTree :: [a] -> [[a]] -> ListT [] [[a]] searchTree [] groups = return groups searchTree (x : xs) groups = do i <- lift [0 .. length groups] let (pre, group : post) = splitAt i ([] : groups) cur = (x : group) : dropWhile null (pre ++ post) cons groups $ searchTree xs cur getWords :: Read a => IO [a] getWords = fmap (map read . words) getLine main :: IO () main = do numCases <- readLn :: IO Int forM_ [1..numCases] $ \i -> do [n, _] <- getWords stocks <- replicateM n getWords :: IO [[Int]] let friends = listArray rng . map isFriends . range $ rng rng = ((0, 0), (n-1, n-1)) isFriends (a, b) = f (>) a b || f (<) a b f op a b = and $ zipWith op (stocks !! a) (stocks !! b) res = fromJust . snd . runIdentity . (`runStateT` Nothing) . execute . execute . branchAndBound bnds . prune p $ searchTree [0 .. n-1] [] p ((x : xs) : _) = all ((friends !) . ((,) x)) xs p _ = True bnds [] = (Just 0, Just n) bnds groups = ( Just (length groups) , Just (length groups + n - 1 - head (head groups)) ) putStrLn $ "Case #" ++ show i ++ ": " ++ show res * possibly others - currently only 2 out of the 500 "surviving" contestants of codejam use Haskell (http://www.go-hero.net/jam/09/lang/ Haskell). so by others I mean Reid from the US. Good luck Reid!

2 2

Re: [Haskell-cafe] 80 bit floating point data in Haskell?
by Andrew Coppin 28 Sep '09

28 Sep '09

wren ng thornton wrote: > Andrew Coppin wrote: >> While we're on the subject... I understand that certain FPUs support >> 80-bit precision. Is there any way to get at that? Or is this going >> to require FFI too? > > Perhaps you want Foreign.C.Types.CLDouble ? > > http://hackage.haskell.org/packages/archive/base/latest/doc/html/Foreign-C-… > > http://en.wikipedia.org/wiki/Long_double > > (Or do you really want to ensure that it's 80-bits regardless of > platform and the whims of the C compiler?) > Yep, that'll do. :-)

2 1

A proposals
by Louis Wasserman 28 Sep '09

28 Sep '09

I'd like to see something resembling as-patterns in type signatures. Specifically, there are cases where I'm inclined to use (m ~ pat) in a type context when m isn't otherwise constrained, just so I can use m as an abbreviation for pat. To reduce these cases, I'd like to see the syntax m@pat allowed for use in type signatures, with m becoming simply an alias for pat. Thoughts? I've added a ticket here <http://hackage.haskell.org/trac/ghc/ticket/3545>. Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

6 6

ANN: JSONb-0.0.2
by Jason Dusek 28 Sep '09

28 Sep '09

JSONb is a ByteString parser for JSON, yielding a simple JSON type composed of Rationals, ByteString tries and strict ByteStrings. http://hackage.haskell.org/package/json-b-0.0.2 An example application program, `json-schema`, is provided. It derives schema for JSON input. When first looking at a web API, for example, you can feed it a few thousand lines of input and see what you got. A sample schema, derived from a stream of the Twitter API, is here: http://wiki.github.com/jsnx/JSONb/schema-example It's worth noting that the schema has a lone object at the bottom that has exactly the format of the "user" property of the schema ahead of it -- why is that? Well, `json-schema` uses a fault tolerant parsing approach; the very last Tweet was cut off and the "user" property's value was among the things that could be salvaged. -- Jason Dusek

1 0

Re: [Hs-Generics] how to automatically create and install documentations of a package?
by Sean Leather 27 Sep '09

27 Sep '09

Hi Daneel, On Sat, Sep 19, 2009 at 13:58, Daneel Yaitskov wrote: > > Recently I've found wonderful thing cabal can install packages itself! It > can even install those packages which need for final one. But I'm disturbed > cabal doesn't create the documentation of a package by default. It manually > makes "runhaskell Setup haddock". > > Who knows? > I believe you can do 'cabal haddock', but I don't know why it doesn't do it by default. BTW, the Haskell Café is typically more suitable for questions such as these. The Generics list is more specifically for generic programming discussions while the Haskell Café serves a broader audience. I've CC'd haskell-cafe@ to see if anybody there knows the answer to your question. Regards, Sean

5 5

frag game-compiling error
by selahaddin gerdan 27 Sep '09

27 Sep '09

Hi there, when I try to install frag,I get this error: .cabal/bin/cabal install frag Resolving dependencies... Downloading frag-1.1.2... Configuring frag-1.1.2... Preprocessing executables for frag-1.1.2... Building frag-1.1.2... [ 1 of 39] Compiling IdentityList ( src/IdentityList.hs, dist/build/frag/frag-tmp/IdentityList.o ) [ 2 of 39] Compiling Quaternion ( src/Quaternion.hs, dist/build/frag/frag-tmp/Quaternion.o ) src/Quaternion.hs:22:27: Couldn't match expected type `GLfloat' against inferred type `Float' In the expression: (r00 :: GLfloat) In the second argument of `newMatrix', namely `[(r00 :: GLfloat), r01, r02, r03, ....]' In the expression: newMatrix ColumnMajor [(r00 :: GLfloat), r01, r02, r03, ....] cabal: Error: some packages failed to install: frag-1.1.2 failed during the building phase. The exception was: exit: ExitFailure 1 Why?

2 1