- Haskell-Cafe - Haskell.org

Generics (SYB) with parametrized types
by JP Moresmau 16 Aug '11

16 Aug '11

Hello, I'm banging my head against a wall there trying to use the syb generics schemes against the GHC API. I'm looking at implementing a search mechanism in the AST in the more direct way that what Scion does (creating an instance of a TypeClass for each AST node type). Since the GHC AST types derive from Data and Typeable, I thought it would be possible. So the problem is a follows: I have a start type, say TypecheckedSource, that derives from Data. What I'd like to do is to find all instances of the Located type inside that source that span a particular range. The problem is that Located is a parametrized type that wraps anything and just add location information. So the result of the search could be anything. Ideally, I'd like to restrict my search to Located instances that wrap an instance of Outputable, pretty print that and output only the result. So I'm looking to implement something that would have that signature: TypecheckedSource -> (Line,Column) -> [String] I have written code along these lines: everything (++) ([] `mkQ` overlap) ts where overlap :: forall b1 . (Outputable b1, Typeable b1) =>Located b1 -> [String] overlap (a::Located b1)= ... trivial code here finding if the location overlaps, and if it does, pretty print the object, otherwise returns [] And GHC complains: Ambiguous type variable `b10' in the constraints: (Outputable b10) arising from a use of `overlap' at ... (Typeable b10) arising from a use of `overlap' at ... So it doesn't like the fact that I don't know which types my Located instances wrap. But that's the point, I don't care, I just want to restrict my search to the ones I can pretty print. If I just try the code against simple non parametrized types it of course works. If I add some forall b1 . (Outputable ... in my main function signature it complains that I never use b1 anywhere else in the signature, of course. Is there a way to achieve what I want (-XOhPleaseDoWhatIwantEvenIfIamNotSureItMakesSense or something)? Thanks a million! -- JP Moresmau http://jpmoresmau.blogspot.com/

2 1

ANNOUNCE: taffybar: an alternative status bar for xmonad
by Tristan Ravitch 16 Aug '11

16 Aug '11

I've wanted a slightly fancier status bar than xmobar for a while, so I finally made one. It uses gtk2hs and dbus extensively, so if you hate either of those things it probably isn't for you. Being written in gtk, though, it can have more graphical widgets. http://hackage.haskell.org/package/taffybar Current feature highlights: * It has a system tray * Generic graph widget for things like CPU/memory * XMonad log over DBus so it can be restarted independently of xmonad * Graphical battery widget There is still a lot that I want to add but I figured getting some feedback early would be handy. Documentation is currently at http://pages.cs.wisc.edu/~travitch/taffybar until I figure out how to appease Hackage (see the System.Taffybar module).

4 9

ANNOUNCE: graphviz-2999.12.0.0
by Ivan Lazar Miljenovic 16 Aug '11

16 Aug '11

It's been a while in coming (I started work on this at the end of last year!) but I am pleased to announce the latest version of my graphviz library [1], which acts as a wrapper around the Graphviz [2] suite of graph visualisation utilities. [1] : http://projects.haskell.org/graphviz/ http://hackage.haskell.org/package/graphviz [2]: http://graphviz.org Major changes in this release (see the changelog [3] for a complete listing): * A large focus on increasing usability: - Examples for all Dot representations against an existing Dot graph - Cut-down, easier to use Attribute wrapper (all Attributes still available from Data.GraphViz.Attributes.Complete if you need any of the others). - graphElemsToDot helps visualise non-FGL graphs (if you can list all nodes and edges, you can visualise it!) * Two new Dot representations: - One that allows graph-based operations (based upon FGL) - Another based upon Andy Gill's dotgen [4] (with permission!) for easier embedding of relatively static graphs. * Pure Haskell implementations of `dot -Tcanon` and `tred`. * Now based upon Text rather than String, which improves performance for both printing and parsing and also enforces UTF-8 encoding. * Now easier to do custom I/O with Dot graphs. [3]: http://projects.haskell.org/graphviz/changelog.html [4]: http://hackage.haskell.org/package/dotgen Unfortunately, this release is largely backwards incompatible in some ways, but not too much. Specifically, it didn't take me long to migrate over Graphalyze [5] and SourceGraph [6], and most of that time was spent changing over to the new, nicer functions for creating Attributes. [5]: http://hackage.haskell.org/package/Graphalyze [6]: http://hackage.haskell.org/package/SourceGraph Please let me know if there are any other API improvements that you'd like to see to improve usage. I am planning a tutorial (half of the reason why this release took so long is that I kept thinking "this functionality would be useful for the tutorial!"; this includes the graph-based representation, the re-implementation of tred and canonicalisation, etc.), which should be out in the next month or so (I'm considering adding nicer syntax for record labels first). -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

1 0

AVL Tree in a pattern matching way
by larry.liuxinyu 16 Aug '11

16 Aug '11

Hi, I browsed the current AVL tree implementation in Hackage http://hackage.haskell.org/packages/archive/AvlTree/4.2/doc/html/src/Data-T… AVL tree denote the different of height from right sub-tree to left sub-tree as delta, to keep the balance, abs(delta)<=1 is kept as invariant. So the typical implementation define N (Negative), P (Positive), and Z (zero) as the tree valid nodes (and the Empty as the trivial case). When a new element is inserted, the program typically first check if the result will break the balance, and process rotation to keep the balance of the tree. Some other pure functional implementation takes the same approach, for example: Guy Cousineau and Michel Mauny. ``The Functional Approach to Programming''. pp 173 ~ 186 Consider the elegant implementation of Red-black tree in pattern matching way by Chris Okasaki, I tried to use the same method in AVL tree, and here is the result. module AVLTree where -- for easy verification, I used Quick Check package. import Test.QuickCheck import qualified Data.List as L -- for verification purpose only -- Definition of AVL tree, it is almost as same as BST, besides a new field to store delta. data AVLTree a = Empty | Br (AVLTree a) a (AVLTree a) Int insert::(Ord a)=>AVLTree a -> a -> AVLTree a insert t x = fst $ ins t where -- result of ins is a pair (t, d), t: tree, d: increment of height ins Empty = (Br Empty x Empty 0, 1) ins (Br l k r d) | x < k = node (ins l) k (r, 0) d | x == k = (Br l k r d, 0) -- For duplicate element, we just ignore it. | otherwise = node (l, 0) k (ins r) d -- params: (left, increment on left) key (right, increment on right) node::(AVLTree a, Int) -> a -> (AVLTree a, Int) -> Int -> (AVLTree a, Int) node (l, dl) k (r, dr) d = balance (Br l k r d', delta) where d' = d + dr - dl delta = deltaH d d' dl dr -- delta(Height) = max(|R'|, |L'|) - max (|R|, |L|) -- where we denote height(R) as |R| deltaH :: Int -> Int -> Int -> Int -> Int deltaH d d' dl dr | d >=0 && d' >=0 = dr | d <=0 && d' >=0 = d+dr | d >=0 && d' <=0 = dl - d | otherwise = dl -- Here is the core pattern matching part, there are 4 cases need rebalance balance :: (AVLTree a, Int) -> (AVLTree a, Int) balance (Br (Br (Br a x b dx) y c (-1)) z d (-2), _) = (Br (Br a x b dx) y (Br c z d 0) 0, 0) balance (Br a x (Br b y (Br c z d dz) 1) 2, _) = (Br (Br a x b 0) y (Br c z d dz) 0, 0) balance (Br (Br a x (Br b y c dy) 1) z d (-2), _) = (Br (Br a x b dx') y (Br c z d dz') 0, 0) where dx' = if dy == 1 then -1 else 0 dz' = if dy == -1 then 1 else 0 balance (Br a x (Br (Br b y c dy) z d (-1)) 2, _) = (Br (Br a x b dx') y (Br c z d dz') 0, 0) where dx' = if dy == 1 then -1 else 0 dz' = if dy == -1 then 1 else 0 balance (t, d) = (t, d) -- Here are some auxiliary functions for verification -- check if a AVLTree is valid isAVL :: (AVLTree a) -> Bool isAVL Empty = True isAVL (Br l _ r d) = and [isAVL l, isAVL r, d == (height r - height l), abs d <= 1] height :: (AVLTree a) -> Int height Empty = 0 height (Br l _ r _) = 1 + max (height l) (height r) checkDelta :: (AVLTree a) -> Bool checkDelta Empty = True checkDelta (Br l _ r d) = and [checkDelta l, checkDelta r, d == (height r - height l)] -- Auxiliary functions to build tree from a list, as same as BST fromList::(Ord a)=>[a] -> AVLTree a fromList = foldl insert Empty toList :: (AVLTree a) -> [a] toList Empty = [] toList (Br l k r _) = toList l ++ [k] ++ toList r -- test prop_bst :: (Ord a, Num a) => [a] -> Bool prop_bst xs = (L.sort $ L.nub xs) == (toList $ fromList xs) prop_avl :: (Ord a, Num a) => [a] -> Bool prop_avl = isAVL . fromList . L.nub And here are my result in ghci: *AVLTree> test prop_avl OK, passed 100 tests. The program is available in github: http://www.google.com/url?sa=D&q=https://github.com/liuxinyu95/AlgoXY/blob/… I haven't provided delete function yet. Cheers. -- Larry, LIU https://github.com/liuxinyu95/AlgoXY

2 1

Haskell Actors, Linda, publish / subscribe models?
by dokondr 15 Aug '11

15 Aug '11

Hi, I am trying to figure out what Haskell libraries can be used to build publish / subscribe communication between threads running both in the same and different address spaces on the net. For my needs any of these models will work: - Actors [ http://en.wikipedia.org/wiki/Actor_model ] - Linda tuple space [ http://en.wikipedia.org/wiki/Linda_%28coordination_language%29 ] - Publish / subscribe [ http://en.wikipedia.org/wiki/Java_Message_Service#Publish.2Fsubscribe_model] I need to build a framework to coordinate task producers / consumers distributed in the same and different address spaces. I need to scale a data processing application somewhat Hadoop-like way yet in more flexible manner, without Hadoop-specific distributed FS constraints. Looking through Applications and libraries/Concurrency and parallelism: http://www.haskell.org/haskellwiki/Applications_and_libraries/Concurrency_a… I found Haskell actor package [ http://hackage.haskell.org/cgi-bin/hackage-scripts/package/actor ] that fails to build with ghc 7.0. Please advise on latest working libraries. Thanks! -- All the best, Dmitri O. Kondratiev "This is what keeps me going: discovery" dokondr(a)gmail.com http://sites.google.com/site/dokondr/welcome

3 5

GHC API gives a weird error about .hi-boot files
by Chris Smith 15 Aug '11

15 Aug '11

Can anyone tell me what I'm doing wrong with the GHC API? I'm getting the following error message from the GHC API: Can't find interface-file declaration for variable Main.picture Probable cause: bug in .hi-boot file, or inconsistent .hi file Use -ddump-if-trace to get an idea of which file caused the error The source code I'm loading doesn't seem to matter at all, except that it defines a top-level variable called 'picture'. Of course, if I change the module name then I get a different module name in the error, but that's about it. The code I'm using to load the file is as follows: getPicture src = do fn <- chooseFileName ".hs" B.writeFile fn src codeErrors <- newIORef [] GHC.defaultErrorHandler (addErrorTo codeErrors) $ GHC.runGhc (Just GHC.libdir) $ GHC.handleSourceError (handle codeErrors) $ do dflags <- GHC.getSessionDynFlags GHC.setSessionDynFlags $ dflags { GHC.ghcMode = GHC.OneShot, GHC.ghcLink = GHC.LinkInMemory, GHC.hscTarget = GHC.HscInterpreted, GHC.log_action = addErrorTo codeErrors } target <- GHC.guessTarget fn Nothing GHC.setTargets [target] r <- fmap GHC.succeeded (GHC.load GHC.LoadAllTargets) case r of True -> do mods <- GHC.getModuleGraph GHC.setContext [ GHC.ms_mod (head mods) ] [ GHC.simpleImportDecl (GHC.mkModuleName "Graphics.Gloss") ] v <- GHC.compileExpr "picture :: Picture" return (Right (unsafeCoerce# v :: Picture)) False -> return (Left codeErrors) I can't see anything I'm doing obviously wrong here, but I'm not at all familiar with GHC's build process, so I'm hoping someone can pipe up and point out the obvious stuff I've missed. Any ideas? -- Chris Smith

1 1

Haskell syntax highlighting in a public blog
by Oscar Picasso 15 Aug '11

15 Aug '11

Hi, Is there a public blog that that allow syntax highlighting of Haskell code? Oscar Picasso

7 7

library on common sub-expression elimination?
by Anton Kholomiov 15 Aug '11

15 Aug '11

Is there a library on common sub-expression elimination?

6 9

FLOPS 2012: 1st Call for Papers
by Tom Schrijvers 15 Aug '11

15 Aug '11

First Call For Papers ===================== *Eleventh International Symposium on Functional and Logic Programming (FLOPS 2012)* May 23-25, 2012 Kobe, Japan [http://www.org.kobe-u.ac.jp/flops2012/] _Submission deadline : December 9, 2011_ FLOPS is a forum for research on all issues concerning declarative programming, including functional programming and logic programming, and aims to promote cross-fertilization and integration between the two paradigms. Previous FLOPS meetings were held in Fuji Susono (1995), Shonan Village (1996), Kyoto (1998), Tsukuba (1999), Tokyo (2001), Aizu (2002), Nara (2004), Fuji Susono (2006), Ise (2008), and Sendai (2010). Topics ====== FLOPS solicits original papers in all areas of functional and logic programming, including (but not limited to): - Declarative Pearls: new and excellent declarative programs with illustrative applications. - Language issues: language design and constructs, programming methodology, integration of paradigms, interfacing with other languages, type systems, constraints, concurrency and distributed computing. - Foundations: logic and semantics, rewrite systems and narrowing, type theory, proof systems. - Implementation issues: compilation techniques, memory management, program analysis and transformation, partial evaluation, parallelism. - Applications: case studies, real-world applications, graphical user interfaces, Internet applications, XML, databases, formal methods and model checking. The proceedings will be published as an LNCS volume. The proceedings of the previous meeting (FLOPS 2010) were published as LNCS 6009. PC co-Chairs ============ - Tom Schrijvers (Ghent University, Belgium) - Peter Thiemann (University of Freiburg, Germany) PC Members ========== - Salvador Abreu (University of Evora, Portugal) - Thorsten Altenkirch (University of Nottingham, UK) - Sebastian Brand (NICTA, Australia) - Giuseppe Castagna (CNRS Univ Paris 7, France) - Sebastian Fischer (Germany) - Marco Gavanelli (University of Ferrara, Italy) - Joxan Jaffar (National University of Singapore, Singapore) - Barry Jay (University of Sydney, Australia) - Andy King (University of Kent, UK) - Claude Kirchner (INRIA, France) - Neelakantan R. Krishnaswami (Microsoft Cambridge, UK) - Yulya Lierler (University of Kentucky, USA) - Keiko Nakata (Tallinn University of Technology, Estonia) - Peter Schneider-Kamp (University of Southern Denmark, Denmark) - Olin Shivers (Northeastern University, USA) - Paul Tarau (University of Northern Texas, USA) - Kazunori Ueda (Waseda University, Japan) - Meng Wang (Chalmers Technical University, Sweden) General Chair and Local co-Chairs ================================= - Naoyuki Tamura (Kobe University, Japan) - Mutsunori Banbara (Kobe University, Japan) - Katsutoshi Hirayama (Kobe University, Japan) Submission ========== Submissions must be unpublished and not submitted for publication elsewhere. Work that already appeared in unpublished or informally published workshops proceedings may be submitted. Submissions should fall into one of the following categories: - Regular research papers: they should describe new results and will be judged on originality, correctness, and significance. - System descriptions: they should contain a link to a working system and will be judged on originality, usefulness, and design. Submissions must be written in English and can be up to 15 pages long, though pearls are typically considerably shorter. Authors are required to use LaTeX2e and the Springer llncs class file, available at [http://www.springer.de/comp/lncs/authors.html] Regular research papers should be supported by proofs and/or experimental results. In case of lack of space, this supporting information should be made accessible otherwise (e.g., a link to a web page, or an appendix). Papers should be submitted electronically at [https://www.easychair.org/conferences/?conf=flops2012] Important Dates =============== - Submission deadline : December 9, 2011 - Author notification : February 3, 2012 - Camera-ready copy : March 2, 2012 Place and Related Events ======================== Takikawa Memorial Hall, Kobe University, 1-1 Rokkodai, Nada, Kobe 657-8501 Japan. The 23rd International Conference on Rewriting Techniques and Applications (RTA 2012) and satellite workshops including WFLP 2012 will be held in the week after FLOPS at Nagoya, Japan. Some Previous FLOPS =================== - FLOPS 2010, Sendai: [http://www.kb.ecei.tohoku.ac.jp/flops2010/] - FLOPS 2008, Ise: [http://www.math.nagoya-u.ac.jp/~garrigue/FLOPS2008/] - FLOPS 2006, Fuji Susono: [http://hagi.is.s.u-tokyo.ac.jp/FLOPS2006/] Sponsors ======== - Japan Society for Software Science and Technology (JSSST) SIGPPL In Cooperation with =================== - ACM SIGPLAN (pending approval) - Asian Association for Foundation of Software (AAFS) - Association for Logic Programming (ALP)

1 0

strictness properties of monoidal folds
by Sebastian Fischer 15 Aug '11

15 Aug '11

Hello Cafe, left- and rightwards folds come in strict and lazy variants foldl/fold' and foldr/foldr' which makes sense because strict versions sometimes use less stack space while lazy versions support infinite data. For example, head (foldr (:) [] [1..]) returns in an instant while head (foldr' (:) [] [1..]) diverges. On the other hand foldl' (flip (:)) 0 [1..10^9] runs in constant space while foldl (flip (:)) 0 [1..10^9] consumes all memory available on my machine (at least without optimizations. With optimizations GHC's strictness analyzer seems to be smart enough to make the accumulator strict.) Data.Foldable also provides the monoidal fold function foldMap. It is left unspecified whether the elements are accumulated leftwards, rightwards or in some other way, which is possible because the combining function is required to be associative. Does this additional freedom for implementors go so far as to allow for strict accumulation? Is it safe to implement foldMap (without prime) with a strict accumulator or are there examples where lazy accumulation is useful like in the above foldr example and distinguishable from strict accumulation without breaking the monoid laws? Sebastian P.S. I thought the `Last` monoid would be an example that requires a lazy accumulator but it is not because the `Just` constructor guards list elements.

2 2