- Haskell-Cafe - Haskell.org

Hiding "growing" state using existentials.
by Tom Schouten 16 Aug '11

16 Aug '11

Dear Cafe, I'm building an abstraction for representing sequences as difference equations, storing initial values and update equation. I have something that resembles a Monad, but has an extra state parameter s that "grows" on _join or _bind, so I can't simply create an instance Monad (Sig s). > {-# LANGUAGE ExistentialQuantification #-} > data Sig s a = Sig s (s -> (a, s)) > _join :: (Sig s1 (Sig s2 a)) -> Sig (s1,s2) a > _join (Sig i1 u1) = Sig (i1, i2) u12 where > ((Sig i2 _), _) = u1 i1 > u12 (s1, s2) = (a, (s1', s2')) where > ((Sig _ u2), s1') = u1 s1 > (a, s2') = u2 s2 > _fmap :: (a -> b) -> Sig s a -> Sig s b > _fmap f (Sig s0 u) = Sig s0 u' where > u' s = (f a, s') where > (a, s') = u s > _return x = Sig () $ \() -> (x, ()) > _bind :: (Sig s1 a) -> (a -> Sig s2 b) -> (Sig (s1,s2) b) > m `_bind` g = _join ((_fmap g) m) I try to hide the state parameter using existential quantification. > data Signal a = forall s. Signal (Sig s a) This approach works for defining Functor and Applicative instances, but I can't seem to find a way to obtain an unwrapped version of f that can be passed to _bind to implement the Monad instance's (>>=). The following returns: Couldn't match type `t' with `Sig s1 b' `t' is a rigid type variable bound by the inferred type of f' :: a -> t at /home/tom/meta/ssm/SigHC.lhs:52:7 In the expression: mb In a case alternative: Signal mb -> mb In the expression: case (f a) of { Signal mb -> mb } > instance Monad Signal where > return = Signal . _return > (>>=) (Signal ma) f = Signal $ ma `_bind` f' where > f' a = case (f a) of > Signal mb -> mb Any tips on how to work around this? Cheers, Tom

2 2

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

how to read CPU time vs wall time report from GHC?
by Wishnu Prasetya 15 Aug '11

15 Aug '11

Hi guys, I'm new in parallel programming with Haskell. I made a simple test program using that par combinator etc, and was a bit unhappy that it turns out to be slower than its sequential version. But firstly, I dont fully understand how to read the runtime report produced by GHC with -s option: SPARKS: 5 (5 converted, 0 pruned) INIT time 0.02s ( 0.01s elapsed) MUT time 3.46s ( 0.89s elapsed) GC time 5.49s ( 1.46s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 8.97s ( 2.36s elapsed) As I understand it from the documentation, the left time-column is the CPU time, whereas the right one is elapses wall time. But how come that the wall time is less than the CPU time? Isn't wall time = user's perspective of time; so that is CPU time + IO + etc? Any help? --Wish.

4 10

Evolving faster Haskell programs - where are the files?
by Robert Clausecker 14 Aug '11

14 Aug '11

I just read the enlightening article by Don Stewart[1], and wanted to test this method on one of my own programs, but it seems that there some of the attached files are missing, namely [2], [3] and [4]. Is there anybody who knows, where I can get those files? I don't really want to rewrite those file by hand. Yours, Robert Clausecker [1]: http://donsbot.wordpress.com/2009/03/09/evolving-faster-haskell-programs [2]: http://galois.com/~dons/acovea/gcc43_core2.acovea [3]: http://galois.com/~dons/acovea/ghc-basic.acovea [4]: http://galois.com/~dons/acovea/ghc-6_10.acovea

2 1

Invitation to connect on LinkedIn
by Andrew Smith B.Sc(Hons),MBA 14 Aug '11

14 Aug '11

LinkedIn ------------ I'd like to add you to my professional network on LinkedIn. - Andrew Andrew Smith B.Sc(Hons),MBA Founder and CEO at VTRL - Value Technology Research Ltd Edinburgh, United Kingdom Confirm that you know Andrew Smith B.Sc(Hons),MBA https://www.linkedin.com/e/uc6lxc-grc8ge3y-3d/isd/3853824536/atjCCKYr/ -- (c) 2011, LinkedIn Corporation

6 6

Re: [Haskell-cafe] Proposal #3339: Add (+>) as a synonym for mappend
by Brandon Allbery 14 Aug '11

14 Aug '11

On Sun, Aug 14, 2011 at 13:38, Yitzchak Gale <gale(a)sefer.org> wrote: > Brandon Allbery wrote: > > Umm, I think the semigroups package will break everything that creates > > Monoid instances anyway. > > It has never broken anything for me. What do you mean? > Anything useful has to be modified to depend on SemiGroup as well to get mconcat or its replacement; that's why you jumped the proposal to begin with.... As others have noted, this is a rather intrusive change to the Haskell ecosystem. *If* it has in fact been decided to go ahead with it, *then* this proposal should be merged with yours since the best time to do it is when mconcat is being relocated anyway. I don't think we've made it past the "if", especially given the comments so far. -- brandon s allbery allbery.b(a)gmail.com wandering unix systems administrator (available) (412) 475-9364 vm/sms

4 3

Array and Ix for custom Graph ADT
by Mark Spezzano 14 Aug '11

14 Aug '11

Hi, I'm creating a Graph data structure, and I want to use the array list approach, implemented as an Array. I need my Nodes to be instances of Ix for this to work and my Node type is roughly as follows: data Node = MyNode Int [Int] Type1 Type2 (Type1 and Type2 are nullary algebraic datatypes--enumerations in other words) How can I "index" the Array with an instance of a Node. I think I need to make Node an instance of Ix somehow?? Is this a sensible approach? Sample code of the instance declaration for Ix would be helpful. Thanks Mark Spezzano

3 4

Diffs for hackage
by Luite Stegeman 14 Aug '11

14 Aug '11

hi all, often when a new version of a package is available on hackage, I want to see what has changed since the previous release. Unfortunately many packages don't have a changelog or a public source code repository. That's why I have made a simple website with git repositories that contain all versions of all hackage packages: http://hdiff.luite.com/ The home page contains a bookmarklet that takes you directly from the index page of a package version (for example http://hackage.haskell.org/package/parsec-3.1.0 ) to the commit diff, showing the difference with the previous version ( http://hdiff.luite.com/cgit/parsec/commit?id=3.1.0 ) I hope some people will find this useful, luite

6 10

Subtitles for "Programming in Haskell" videos
by José Romildo Malaquias 13 Aug '11

13 Aug '11

Hello. Are there subtitles (in English or Portuguese) for the video lectures[1] given by Erik Meijer using the book "Programming in Haskell", by Graham Hutton? [1] http://www.cs.nott.ac.uk/~gmh/book.html Romildo

1 0

ML Workshop: register early by August 15
by Chung-chieh Shan 13 Aug '11

13 Aug '11

ACM SIGPLAN Workshop on ML Sunday, 18 September 2011, Tokyo, Japan (co-located with ICFP) http://conway.rutgers.edu/ml2011/ CALL FOR PARTICIPATION * Early Registration deadline is August 15! * The ML family of programming languages includes dialects known as Standard ML, Objective Caml, and F#. These languages have inspired a large amount of computer-science research, both practical and theoretical. This workshop aims to provide a forum for discussion and research on ML and related technology (higher-order, typed, or strict languages). The format of ML 2011 will continue the return in 2010 to a more informal model: a workshop with presentations selected from submitted abstracts. Presenters will be invited to submit working notes, source code, and extended papers for distribution to the attendees, but the workshop will not publish proceedings, so any contributions may be submitted for publication elsewhere. We hope that this format will encourage the presentation of exciting (if unpolished) research and deliver a lively workshop atmosphere. INVITED SPEAKERS Naoki Kobayashi (Tohoku University) Atsushi Ohori (Tohoku University) ACCEPTED TALKS Efficiently scrapping boilerplate code in OCaml Dmitri Boulytchev, Sergey Mechtaev Implementing implicit self-adjusting computation (short talk) Yan Chen, Joshua Dunfield, Matthew A. Hammer, Umut A. Acar Lightweight typed customizable unmarshaling Pascal Cuoq, Damien Doligez, Julien Signoles Adding GADTs to OCaml: the direct approach Jacques Garrigue, Jacques Le Normand A demo of Coco: a compiler of monadic coercions in ML (short talk) Nataliya Guts, Michael Hicks, Nikhil Swamy, Daan Leijen Verifying liveness properties of ML programs M. M. Lester, R. P. Neatherway, C.-H. L. Ong, S. J. Ramsay MixML remixed Andreas Rossberg, Derek Dreyer Report on OCaml type debugger Kanae Tsushima, Kenichi Asai Camomile: a Unicode library for OCaml (short talk) Yoriyuki Yamagata PROGRAM COMMITTEE Amal Ahmed (Indiana University) Andrew Tolmach (Portland State University) Anil Madhavapeddy (University of Cambridge) Chung-chieh Shan (chair) Joshua Dunfield (Max Planck Institute for Software Systems) Julia Lawall (University of Copenhagen) Keisuke Nakano (University of Electro-Communications) Martin Elsman (SimCorp) Walid Taha (Halmstad University) STEERING COMMITTEE Eijiro Sumii (chair) (Tohoku University) Andreas Rossberg (Google) Jacques Garrigue (Nagoya University) Matthew Fluet (Rochester Institute of Technology) Robert Harper (Carnegie Mellon University) Yaron Minsky (Jane Street)

1 0

logic and types
by Patrick Browne 13 Aug '11

13 Aug '11

Hi, Below are some questions about the logical interpretation of types and type classes. Thanks, Pat module J where type Id = String type Position = Integer data Person = Person Id Position deriving Show -- Is this an axiom at type level? class Pos a where getPos :: a -> Position -- The :type command says -- forall a. (Pos a) => a -> Position -- How do I write this in logic? (e.g. implies, and, or, etc) -- What exactly is being asserted about the type variable and/or about the class? -- I am not sure of the respective roles of => and -> in a logical context -- Is the following a fact at type level, class level or both? instance Pos Person where getPos (Person i p) = p -- Is it the evaluation or the type checking that provides a proof of type correctness? -- getPos(Person "1" 2) This message has been scanned for content and viruses by the DIT Information Services E-Mail Scanning Service, and is believed to be clean. http://www.dit.ie

6 8

Re: [Haskell-cafe] library on common sub-expression elimination?
by oleg＠okmij.org 13 Aug '11

13 Aug '11

I guess you mean the function that converts an abstract syntax tree to a directed acyclic graph (DAG). Just for completeness I should mention that if the object language has effects including non-termination, one has to be careful eliminating seemingly common expressions. For example, in \a i -> if i >= 0 then a ! i else if i > 0 then a ! i + a ! (i-1) else .... we see the expression (a ! i) repeated in both branches of the conditional. Eliminating the `duplicate' by pulling it out \a i -> let t = a ! i in if i >= 0 then t else if i > 0 then t + a ! (i-1) else .... would be wrong, wouldn't it? This issue has been extensively investigated in the Fortran compiler community; Elliott, Finne and de Moor's ``Compiling Embedded Languages'' (JFP 2003) talks about it at length. The standard technique to detect occurrences of common subexpressions is so-called hash-consing. There are (OCaml) libraries for it: author = {Jean-Christophe Filli{\^a}tre and Sylvain Conchon}, title = {Type-Safe Modular Hash-Consing}, pages = {12--19}, crossref = "ml2006", doi = "10.1145/1159876.1159880", The upcoming distilled tutorial at DSL 2011 http://dsl2011.bordeaux.inria.fr/index.php?option=com_content&view=article&… will present a Haskell library for hash-consing. The library can work with the standard Haskell Hash-tables or without them (using Data.Map, for example). The library does _not_ rely on Stable names and other internal GHC operations with unstable semantics. The library will find all common sub-expressions. Incidentally, despite the Lisp-sounding name, hash-consing was invented before Lisp. It was described, for the English audience, in the first volume of Comm. ACM, in 1958: @Article{ Ershov-hash-consing, author = {A. P. Ershov}, title = {On programming of arithmetic operations}, journal = "Communications of the {ACM}", year = 1958, volume = 1, number = 8, pages = {3--6}, doi ="10.1145/368892.368907", url = "http://portal.acm.org/citation.cfm?id=368907" } The translation is quite accurate, as far as I could see, but misses the flowcharts and the diagram of the original paper. This short paper fully describes what we now call hash tables, hash functions, useful properties of hash functions, and hash-consing. The article analyzes the time complexity of the algorithm. Since the algorithm has two exits, writing programs in the continuation-passing style must have been familiar back then. The library to be presented at DSL 2011 unwittingly follows Ershov's algorithm closely. The library is (hopefully) better described (see the preface to the English translation of Ershov's paper). Nowadays, starting a paper with the phrase ``All unexplained terms are those from [1]'' (where [1] is the single reference) would not be taken kindly by reviewers.

4 3

fyi GHC 7.2.1 release on the benchmarks game
by Isaac Gouy 12 Aug '11

12 Aug '11

1) Some of the GHC programs contributed to the benchmarks game have problems with recent GHC releases - meteor-contest #5 - Ambiguous occurrence `permutations' http://shootout.alioth.debian.org/u64q/program.php?test=meteor&lang=ghc&id=… - regex-dna #2 - Precedence parsing error http://shootout.alioth.debian.org/u64q/program.php?test=regexdna&lang=ghc&i… - reverse-complement #2 - parse error on input `->' http://shootout.alioth.debian.org/u64q/program.php?test=revcomp&lang=ghc&id… - reverse-complement #3 - Could not find module `Monad' http://shootout.alioth.debian.org/u64q/program.php?test=revcomp&lang=ghc&id… 2) I noticed `-fvia-C` has now gone away and there were half-a-dozen programs that had been written to use `-fvia-C` so how might that effect performance of those programs?

4 4

Distributions link on Hackage
by Peter Simons 12 Aug '11

12 Aug '11

Hi, the home page of a package on Hackage links to various distributions to show which versions are available, i.e. Fedora, Debian, FreeBSD, etc. In NixOS, we have fairly up-to-date package set, and I would like to see that distribution included on Hackage. Now I wonder how to get that done? Can anyone advice on the procedure to add support for a distribution to Hackage? Take care, Peter

2 1

Potential problem with AC-Vector-Fancy package
by Dave Tapley 12 Aug '11

12 Aug '11

Is anyone maintaining the AC-Vector-Fancy package? I haven't had a reply from the latest maintainer (Andrew Coppin) on Hackage, so I thought I'd open it up to cafe: I think I have found a problem with the union function: If you look here: http://hpaste.org/49889 You will see that line 4 gives a different result to lines 6, 8, 10; this shouldn't be the case because union is commutative.

3 3

Building ? using kleene closure {not haskell specific}
by C K Kashyap 12 Aug '11

12 Aug '11

Hello gentle Haskell folks, I happened to read "Beautiful code"'s chapter 1 today and found Brian Kerninghan's regex implementation. In it he only shows the * meta character. I can easily understand how + can be built but am having trouble with building ? (zero or one). I'd really appreciate it if some one could help me understand it. Regards, Kashyap

3 3

Help understanding Haskell runtime costs
by Thiago Negri 12 Aug '11

12 Aug '11

Hello all, I'm relatively new to Haskell and trying to solve some online judge's problems in it. One of the problems is to say if a given sentence is a tautogram or not. A tautogram is just a sentence with all the words starting with the same letter. My first try (solution is ok) was to do it as haskeller as possible, trying to overcome my imperative mind. But it did bad at performance (0.30 secs of runtime, 4.6 mb of memory): -- code start import Data.Char (toLower) main = getContents >>= mapM_ (putStrLn . toStr . isTautogram . words) . takeWhile (/= "*") . lines toStr :: Bool -> [Char] toStr True = "Y" toStr False = "N" isTautogram :: [[Char]] -> Bool isTautogram (x:[]) = True isTautogram (x:xs) = all ((== firstChar) . toLower . head) xs where firstChar = toLower . head $ x -- code end I tried to profile the code, but didn't find anything useful. My bet is that all this "words . lines" is consuming more memory than necessary, maybe saving space for the lines already processed. Then I tried a some-what tail-call function, consuming one line at each iteration: -- code start import Data.Char (toLower) main :: IO () main = getLine >>= mainLoop mainLoop :: [Char] -> IO () mainLoop s | (head s) == '*' = return () | otherwise = (putStrLn . toStr . isTautogram . words $ s) >> main toStr :: Bool -> [Char] toStr True = "Y" toStr False = "N" isTautogram :: [[Char]] -> Bool isTautogram (x:[]) = True isTautogram (x:xs) = all ((== firstChar) . toLower . head) xs where firstChar = toLower . head $ x -- code end Note that the only thing that changed between the two tries was the main-loop. The second version runs faster (got 0.11 secs) and with less memory (3.6 mb) Can someone explain to me what is really going on? Maybe pointing out how I can achieve these optimizations using profiling information... Thanks, Thiago.

2 2

Trouble with readProcess
by Charles-Pierre Astolfi 12 Aug '11

12 Aug '11

Hi -cafe, I'm using readProcess and I don't know how to handle this issue: readProcess cmd [opt1,opt2] seems to execute the following: $ cmd "opt1" "opt2" That is usually fine, but I'm using an external program that doesn't understand the quotes, so I need to execute instead: $ cmd opt1 opt2 How should I do that? -- Cp

4 5

ANNOUNCE: Chell: A quiet test runner (low-output alternative to test-framework)
by John Millikin 11 Aug '11

11 Aug '11

Homepage: https://john-millikin.com/software/chell/ Hackage: http://hackage.haskell.org/package/chell -------- This is just a quick package I whipped up out of frustration with test-framework scrolling an error message out of sight, for the millionth time. Chell has the same general purpose (aggregate your assertions + properties + whatever into a single executable), but only prints when a test fails or aborts. It also has a small built-in test library, similar to HUnit, so you don't need to depend on 2-3 separate libraries if you're just doing simple tests. Cool features thereof: * it reports the line number of failed assertions * you can use $expect instead of $assert, so even if it fails, the test keeps going (all the failures are printed at the end) * you can add "notes" to a test, which are saved in logs and reports. you can put in any sort of metadata you want (nice for figuring out why a test is failing) * assertions for text diffs, so if you're testing two big chunks of text for equality you don't have to copy+paste to see what's different.

2 3

ANNOUNCE: Chell: A quiet test runner (low-output alternative to test-framework)
by Greg Weber 11 Aug '11

11 Aug '11

Hi John, I am wondering if you have seen the hspec package? [1] It seems to solve all the problems you are with chell, including that it silences Hunit output. We are using it for all the Yesod tests now. Thanks, Greg Weber [1]: http://hackage.haskell.org/packages/archive/hspec/0.6.1/doc/html/Test-Hspec…

4 8

Re: [Haskell-cafe] [Haskell] ANNOUNCE: GHC version 7.2.1
by Henning Thielemann 11 Aug '11

11 Aug '11

On 09.08.2011 22:01, Ian Lynagh wrote: > > The GHC Team is pleased to announce a new major release of GHC, 7.2.1. > > The 7.2 branch is intended to be more of a "technology preview" than > normal GHC stable branches; in particular, it supports a significantly > improved version of DPH, as well as new features such as compiler > plugins and "safe Haskell". The design of these new features may evolve > as we get more experience with them. See the release notes for more > details of what's new and what's changed. These sound like a lot of exciting news. The release notes also mention a VECTORISE pragma, that is not mentioned in http://www.haskell.org/ghc/docs/7.2.1/html/users_guide/pragmas.html and not in the index. Is it about the planned GHC support for SSE/AltiVec vector units or is it about DPH?

2 1

How to use cabal macros in .hsc files
by Bas van Dijk 11 Aug '11

11 Aug '11

Hello, Currently it's not possible to use cabal macros like MIN_VERSION_base(x,y,z) in .hsc files: http://hackage.haskell.org/trac/hackage/ticket/870 Is there a workaround to get the same effect? Regards, Bas

2 1

New releases and BSD3 license
by John Goerzen 11 Aug '11

11 Aug '11

Hello, I would like to announce new versions of the following: hslogger convertible HDBC HDBC-odbc HDBC-postgresql HDBC-sqlite3 By popular, insistent, persistent, and patient request <grin>, all have been relicensed under the 3-clause BSD license. I am also working to make that happen with MissingH, but have to receive permission from a few third parties first. Additionally, this will be my last upload of the HDBC* packages. Nicolas Wu has kindly agreed to step in as HDBC maintainer. Nicolas has recently contributed a lot of good things towards HDBC and has more time to maintain it than I do. Thanks, -- John Goerzen

3 3

Additional functions of GMP
by Artyom Kazak 11 Aug '11

11 Aug '11

GMP has a lot of functions, such as extracting roots, primality test, Legendre symbol, factorial and so on. These can be written in Haskell, of course, but isn't it better to use existing functions? They are also much faster than similar functions from NumericPrelude, I believe. I have heard GHC 7.2.1 now includes module named GHC.Integer.Logarithms, but I can't find its description anywhere. So, my question is: can I use full power of GMP's functions, and if I can — how?

2 2

Re: [Haskell-cafe] ANNOUNCE: yap-0.0 - yet another prelude
by Sebastian Fischer 11 Aug '11

11 Aug '11

[switched to Cafe] On Wed, Aug 10, 2011 at 11:46 PM, Henning Thielemann <lemming(a)henning-thielemann.de> wrote: > > On Wed, 10 Aug 2011, Paterson, Ross wrote: > >> Yet another restructuring of the Prelude numeric classes on algebraic >> lines, proposed for a revision of the Haskell Prelude: >> >> http://hackage.haskell.org/package/yap-0.0 > > A nice lightweight design, both in terms of the use of type extensions and > import dependencies, that should people encourage to use it, when they are > afraid of changing to a more radical approach like numeric-prelude. I would > have prefered the name AdditiveGroup to AbelianGroup, since with '+' and '-' > and '0' I associate more than just the laws of an Abelian group. The > multiplicative group of rational numbers is abelian, too. I'm curious: what laws do you have in mind for '+', '-', and '0' that do not hold in the multiplicative group of rational numbers with (+) = (*); (-) = (/); 0 = 1 ? Sebastian

3 2

Haskell Weekly News: Issue 194
by Daniel Santa Cruz 11 Aug '11

11 Aug '11

Welcome to issue 194 of the HWN, a newsletter covering developments in the Haskell community. This release covers the week of July 31 to August 6, 2011. [1] http://goo.gl/8hDku You can find a HTML rendition of this newsletter at: http://contemplatecode.blogspot.com/2011/08/haskell-weekly-news-issue-194.h… Announcements Andy Gill has issued a call for papers for the 23rd Symposium on Implementation and Application of Functinal Languages (IFL 2011) to be held at the University of Kansan, in Lawrence, Kansas, USA. The symposium is scheduled for October 3-5, 2011. [2] http://goo.gl/hHD2H Anil Madhavapeddy issued a call for participation to the Commercial Users of Functional Programming Workshop (CUFP 2011), which will be co-located with the ICFP 2011 in Tokyo, Japan, on September 22-24, 2011. [3] http://goo.gl/BvPpj The GHC team annouced the release of GHC 7.2.1 [4] http://goo.gl/0gTL3 New and Updated Projects * Eddie (Mike Meyer): A tool for shell scripting with haskell. [5] http://goo.gl/tzdbv * HROOT (Ian-Woo Kim): Haskell binding to the ROOT analysis package. [6] http://goo.gl/qJ1Bb * vector-algorithms (Dan Doel): Efficient Algorithms for Vector Arrays. [7] http://goo.gl/YZmxR * Alex (Simon Marlow): Update. A lexical analyser generator for Haskell. [8] http://goo.gl/dDYrl Quotes of the Week * kmc: when computer scientists rebuild the world after the apocalypse, we will have hanging gardens with trees that grow downward * kmc: a wise man once said that the entire world can be described as convex combinations of drugs, math, and cardboard * roconnor: as a rule of thumb, avoid any packages shipped with the Haskell Plaform. * kmc: Try the new GHC IO Scheduler! It's got what plants crave! * kmc: I refuse to believe that any loving god would invent the monomorphism restriction * AlanPerlis: It is easier to write an incorrect program than understand a correct one. * [kmc] do you have a theory where the stack overflow is coming from? [copumpkin] joel spolsky * @faq is it possible to find things Haskell can't do? [lambdabot] The answer is: Yes! Haskell can do that. * kmc: Haskell isn't really designed by mathematicians. it's designed by people who programmers would consider to be mathematicians and mathematicians would consider to be programmers Top Reddit Stories * "I'm very tempted to want to move to a functional programming language. Haskell or Ocaml or something" -John Carmack Domain: youtube.com, Score: 120, Comments: 62 On Reddit: [9] http://goo.gl/enBuK Original: [10] http://goo.gl/WXfZy * That seems like a challenge! Whatever happened to the hs->js compiler? Domain: xkcd.com, Score: 48, Comments: 12 On Reddit: [11] http://goo.gl/okkWU Original: [12] http://goo.gl/HykNt * The Conditional Choice Operator Domain: zenzike.com, Score: 47, Comments: 15 On Reddit: [13] http://goo.gl/npdIK Original: [14] http://goo.gl/tdb4J * Haskell For Kids! Introduction to My Upcoming Class Domain: cdsmith.wordpress.com, Score: 47, Comments: 31 On Reddit: [15] http://goo.gl/Gnmg9 Original: [16] http://goo.gl/y1pEF * seL4, a formally verified version of the L4 microkernel, was spec-prototyped in Haskell (PDF) Domain: sigops.org, Score: 23, Comments: 8 On Reddit: [17] http://goo.gl/fq0t9 Original: [18] http://goo.gl/mCrEu * Hi guys, I made a Haskell to Clojure translator. Check it out :D Domain: github.com, Score: 17, Comments: 21 On Reddit: [19] http://goo.gl/Fxdwa Original: [20] http://goo.gl/OL86U * Moderator Guidelines : Them's the rules. Domain: self.haskell, Score: 12, Comments: 0 On Reddit: [21] http://goo.gl/UPz94 Original: [22] http://goo.gl/UPz94 * Library of conditional one-liners and combinators? Domain: self.haskell, Score: 11, Comments: 39 On Reddit: [23] http://goo.gl/dTmX1 Original: [24] http://goo.gl/dTmX1 * Zoom, a thor/rake-like task runner for Haskell (very alpha) Domain: github.com, Score: 10, Comments: 3 On Reddit: [25] http://goo.gl/KkW9v Original: [26] http://goo.gl/LqYUE * Yesod form overhaul Domain: yesodweb.com, Score: 8, Comments: 1 On Reddit: [27] http://goo.gl/biQuv Original: [28] http://goo.gl/lxuYj * ETA on the Haskell Platform 2011.4.0.0 release? Domain: self.haskell, Score: 8, Comments: 3 On Reddit: [29] http://goo.gl/gydgP Original: [30] http://goo.gl/gydgP Top StackOverflow Questions * Speed comparison C vs python vs erlang vs haskell votes: 50, answers: 8 Read on SO: [31] http://goo.gl/XEZ9Z * Recursion schemes for dummies? votes: 37, answers: 2 Read on SO: [32] http://goo.gl/nnhGb * Is it possible to place inequality constraints on haskell type variables? votes: 11, answers: 1 Read on SO: [33] http://goo.gl/VnexA * Haskell: Prefer pattern-matching or member access? votes: 9, answers: 6 Read on SO: [34] http://goo.gl/E225N * Difference between TVar and TMVar votes: 7, answers: 2 Read on SO: [35] http://goo.gl/lmn1R * Java's Interface and Haskell's type class: differences and similarities? votes: 7, answers: 6 Read on SO: [36] http://goo.gl/fMGpH * Haskell code accompanying the Paul Hudak 1994 US Navy experiment paper [migrated] votes: 7, answers: 0 Read on SO: [37] http://goo.gl/fpVO5 About the Haskell Weekly News To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. Until next time, Daniel Santa Cruz References 1. http://haskell.org/ 2. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18868 3. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18873 4. http://www.haskell.org/ghc/download_ghc_7_2_1 5. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18867 6. http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/91469 7. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18871 8. http://permalink.gmane.org/gmane.comp.lang.haskell.general/18874 9. http://www.youtube.com/watch?v=4zgYG-_ha28&feature=player_detailpage#t=4193s 10. http://www.reddit.com/r/haskell/comments/jap3x/im_very_tempted_to_want_to_m… 11. http://www.xkcd.com/934/ 12. http://www.reddit.com/r/haskell/comments/j9nef/that_seems_like_a_challenge_… 13. http://zenzike.com/posts/2011-08-01-the-conditional-choice-operator 14. http://www.reddit.com/r/haskell/comments/j6rbd/the_conditional_choice_opera… 15. http://cdsmith.wordpress.com/2011/08/03/haskell-for-kids-introduction/ 16. http://www.reddit.com/r/haskell/comments/j8ac0/haskell_for_kids_introductio… 17. http://www.sigops.org/sosp/sosp09/papers/klein-sosp09.pdf 18. http://www.reddit.com/r/haskell/comments/ja27r/sel4_a_formally_verified_ver… 19. https://github.com/dmead/Clojure-translate 20. http://www.reddit.com/r/haskell/comments/jarp0/hi_guys_i_made_a_haskell_to_… 21. http://www.reddit.com/r/haskell/comments/j8df0/moderator_guidelines_thems_t… 22. http://www.reddit.com/r/haskell/comments/j8df0/moderator_guidelines_thems_t… 23. http://www.reddit.com/r/haskell/comments/j51yw/library_of_conditional_oneli… 24. http://www.reddit.com/r/haskell/comments/j51yw/library_of_conditional_oneli… 25. https://github.com/iand675/Zoom 26. http://www.reddit.com/r/haskell/comments/ja6fo/zoom_a_thorrakelike_task_run… 27. http://www.yesodweb.com/blog/2011/08/yesod-form-overhaul 28. http://www.reddit.com/r/haskell/comments/j8gta/yesod_form_overhaul/ 29. http://www.reddit.com/r/haskell/comments/jaa8t/eta_on_the_haskell_platform_… 30. http://www.reddit.com/r/haskell/comments/jaa8t/eta_on_the_haskell_platform_… 31. http://stackoverflow.com/questions/6964392/speed-comparison-c-vs-python-vs-… 32. http://stackoverflow.com/questions/6941904/recursion-schemes-for-dummies 33. http://stackoverflow.com/questions/6939043/is-it-possible-to-place-inequali… 34. http://stackoverflow.com/questions/6913130/haskell-prefer-pattern-matching-… 35. http://stackoverflow.com/questions/6915079/difference-between-tvar-and-tmvar 36. http://stackoverflow.com/questions/6948166/javas-interface-and-haskells-typ… 37. http://stackoverflow.com/questions/6953020/haskell-code-accompanying-the-pa…

1 0

Announce: file-location 0.2.4
by Greg Weber 11 Aug '11

11 Aug '11

Were you excited when Simon Marlow announced he might be able to add stack traces to Haskell? Would you settle for just the first line of the stack trace? It is a little known fact that template haskell exposes the file and line number information. file-location contains common debugging/error/exception functions and template haskell versions that give file location information. > $(err "OH NO!") main:Main main.hs:16:1 OH NO! > debug [1,2,3] DEBUG: [1,2,3] [1,2,3] > $(dbg) [1,2,3] DEBUG main:Main main.hs:1:3 [1,2,3] [1,2,3] ($(thrwIO) AException) `catch` \e -> putStrLn ("Caught " ++ show (e :: AException)) Caught AException "main:Main test/main.hs:25:6" Don't like the exception dependency? Use version 0.2.3 for now until the exceptions are split into a separate package. Just want the debug helpers (like the debug function) but not interested in the template haskell? The library is already split into modules based on dependencies. The near future plan is to separate this into separate packages, including one with the non-TH debug helpers. Also see the github README for more examples: https://github.com/gregwebs/FileLocation.hs I think haskell could use a few more debug helpers. Perhaps some of these could be pushed back into the standard distribution. Thanks, and I am looking forward to your feedback, Greg Weber

1 1

Type level Roman numerals and skew binary random access lists (formatting hopefully corrected)
by Ivan Tomac 10 Aug '11

10 Aug '11

Apologies for the repost. The post is a literate Haskell file and as my first attempt was formatted for 80 character lines, it no longer worked after the lines got mangled. Hopefully this time it'll come out right. --------------------------------------------------------------------- I've recently been playing with Sebastian Fischer's explicit sharing monad library (found at http://sebfisch.github.com/explicit-sharing) and after looking at the code noticed the implementation memoizes values into an IntMap of untyped values that are coerced into the correct type on retrieval, which is a sensible and practical way to implement this. Just for fun I thought I'd have a go at implementing a (very impractical) version without type casting but, disappointingly, I didn't quite get there. I ran out of steam by the time I got around to playing with parameterized monads by which stage the type signatures started looking a bit scary. That and I needed to get back to my projects. This has been sitting on my hard drive for a couple of weeks now and I've finally decided to clean it up and post it, maybe someone else will find it amusing. The post is about HList inspired type level implementation of Okasaki's skew binary random access lists indexed by Roman numerals, using ideas from Ralf Hinze's paper "Functional Pearl: Typed Quote/Antiquote - Or: Compile-time Parsing" and some fun tricks from the MLton wiki: http://www.cs.ox.ac.uk/ralf.hinze/publications/Quote.pdf http://mlton.org/Fold http://mlton.org/Fold01N http://mlton.org/VariableArityPolymorphism With that out of the way, we start of by declaring all the different extensions we'll need. > {-# LANGUAGE FlexibleInstances #-} > {-# LANGUAGE FunctionalDependencies #-} > {-# LANGUAGE MultiParamTypeClasses #-} > {-# LANGUAGE ScopedTypeVariables #-} > {-# LANGUAGE TypeFamilies #-} > {-# LANGUAGE TypeSynonymInstances #-} These two are ugly. We need undecidable instances for bunch of things and overlapping instances for the type equality trick borrowed from the HList paper: http://homepages.cwi.nl/~ralf/HList/paper.pdf > {-# LANGUAGE OverlappingInstances #-} > {-# LANGUAGE UndecidableInstances #-} For GHC 7 we also need to increase the context stack. > {-# OPTIONS_GHC -fcontext-stack=100 #-} Define Boolean values at the type level. > data T = T > data F = F And now Peano numbers. We don't actually use the constructors for anything but if we omitted them we'd have to use another extension, EmptyDataDecls. > data Z = Z > data S n = S n Here we create some types for heterogeneous lists and trees. Note that Pair has an extra type parameter. We provide two different versions of the cons operation. One requires that extra parameter but does not require undecidable instances. Unfortunately we still need undecidable instances later on for indexing. > data Pair i x y = Pair x y deriving Show > data Nil = Nil deriving Show > data Tree l x r = Node l x r deriving Show > data Leaf x = Leaf x deriving Show > > type Pair' x y = Pair () x y > > nil :: Nil > nil = Nil Equality, less than, addition, subtraction and multiplication by 2 type functions for Peano numbers. > type family Equals m n > > type instance Equals Z Z = T > type instance Equals Z (S n) = F > type instance Equals (S n) Z = F > type instance Equals (S m) (S n) = Equals m n > > type family LessThan m n > > type instance LessThan Z Z = F > type instance LessThan Z (S n) = T > type instance LessThan (S n) Z = F > type instance LessThan (S m) (S n) = LessThan m n > > type family Add m n > > type instance Add Z n = n > type instance Add n Z = n > type instance Add (S m) (S n) = S (S (Add m n)) > > type family Sub m n > > type instance Sub n Z = n > type instance Sub (S m) (S n) = Sub m n > > type family Mul2 n > > type instance Mul2 Z = Z > type instance Mul2 (S n) = S (S (Mul2 n)) And finally tree depth and weight/size. > type family Depth t > > type instance Depth (Leaf x ) = S Z > type instance Depth (Tree l x r) = S (Depth l) > > type family Weight t > > type instance Weight (Leaf x ) = S Z > type instance Weight (Tree l x r) = S (Mul2 (Weight l)) For reference, here is normal implementation of random access lists newtype List a = List { unList :: [(Int, Tree a)] } deriving Show data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving Show cons :: a -> List a -> List a cons x (List wts) = List $ case wts of (v, l) : (w, r) : wts' | v == w -> (1 + w + w, Node l x r) : wts' _ -> (1 , Leaf x ) : wts List here is a list of pairs of balanced binary trees and their weights. The cons function has exactly two cases. The second case is trivial, we are mostly interested in the first case. If the weights of the two trees at the front of the list are the same, we combine them into a new tree with the newly inserted element at the top. Now we are ready to implement cons. This first version is simpler but requires undecidable instances. > class Cons' x y z | x y -> z where cons' :: x -> y -> z Here we cover the cases of inserting an element into an empty list, and inserting an element into a list with a single element. These cover two out of four different possibilities when inserting a new element. > instance Cons' x Nil (Pair' (Leaf x) Nil) where cons' = Pair . Leaf > > instance Cons' x (Pair' y Nil) (Pair' (Leaf x) (Pair' y Nil)) where > cons' = Pair . Leaf The remaining two cases occur when we have at least two elements in the list. This is where we need to compare weights of trees. First observation is that we don't need weight of a tree, depth is sufficient. Now we have a problem. We'd like to be able to write something like instance (Depth l ~ u, Depth r ~ v, Equals u v ~ T) => Cons' x (Pair' l (Pair' r y)) (Pair' (Tree l x r) y) where ... instance (Depth l ~ u, Depth r ~ v, Equals u v ~ F) => Cons' x y (Pair' (Leaf x) y) where ... but we get a functional dependency conflict in the second instance as the type variable y might stand for Pair' l (Pair' r y) and the functional dependency already says the result should be Pair' (Tree l x r) y, not Pair' (Leaf x) (Pair' l (Pair' r y)). We need to merge these two instances into one and then branch on the result of the comparison of tree depths. To do this, we introduce another type class to do the branching. > class ConsIf c x y z | c x y -> z where consIf :: c -> x -> y -> z And merge the instances. > instance ( Depth l ~ u > , Depth r ~ v > , Equals u v ~ c > , ConsIf c x (Pair' l (Pair' r y)) z ) => > > Cons' x (Pair' l (Pair' r y)) z where > > cons' = consIf (undefined :: c) > > instance ConsIf F x y (Pair' (Leaf x) y) where consIf _ = Pair . Leaf > > instance (Depth l ~ u, Depth r ~ u) => > > ConsIf T x (Pair' l (Pair' r y)) (Pair' (Tree l x r) y) where > > consIf _ x (Pair l (Pair r y)) = Pair (Node l x r) y We can now test our cons function. > t0' = cons' 'a' > $ cons' (33 :: Int) > $ cons' (4.4 :: Float) > $ cons' (88 :: Integer) > $ cons' ([1 .. 8] :: [Int]) > $ cons' "moose" > $ cons' ((6, 3) :: (Int, Int)) > $ nil And ghci tells us the type is *Main> :t t0' t0' :: Pair' (Tree (Tree (Leaf Float) Int (Leaf Integer)) Char (Tree (Leaf [Char]) [Int] (Leaf (Int, Int)))) Nil Now we get to the second version that doesn't need the undecidable instances extension. In this one we go a step back and attempt to keep track of depth information in the type of the list. When we again end up at the point where we need to compare if two trees at the front of the list are of the same depth, we run into a problem. instance Cons x (Pair i l (Pair i r y)) (Pair (S i) (Tree l x r) y) where ... instance Cons x (Pair i y (Pair j z w)) (Pair (S Z) x (Pair i y (Pair j z w))) where ... This clearly won't work as we again get a functional dependency conflict. The j type variable could be the same as i in which case we have two different rules for what the result of consing x with (Pair i l (Pair i r y)) should be. As we don't want to use undecidable instances, we are stuck. Unless we can find a way to disambiguate the two instances. Instead of keeping track of depth information, we could try to track how many elements we need to complete a new tree. That way instead of counting up, we are counting down towards zero and it becomes easy to differentiate the two instances as only the one where the depths of the two trees are equal will contain a Z. Keeping track of how many elements are missing turns out to be a problem, at least as long as we don't want to use undecidable instances. Fortunately we can replace the number of elements missing with the number of levels the tree at the front needs before its depth matches the tree that follows. > class Cons x y z | x y -> z where cons :: x -> y -> z Inserting an element into an empty list involves adding the element to the front and setting its the depth counter to 1. > instance Cons x Nil (Pair (S Z) (Leaf x) Nil) where cons = Pair . Leaf If we are inserting an element into a list that already has a single tree, we again add the new element to the front, set its counter to 1 and we decrement the counter of the tree that now follows the newly inserted element. > instance Cons x (Pair (S i) y Nil) > (Pair (S Z) (Leaf x) (Pair i y Nil)) where > > cons x (Pair y z) = Pair (Leaf x) (Pair y z) Here we have the case where the list already contains at least two trees but their depths are not equal. Like with the previous instance we insert the new element to the front and decrement the counter of the tree that now follows it. > instance Cons x (Pair (S i) y (Pair (S j) z w)) > (Pair (S Z) (Leaf x) (Pair i y (Pair (S j) z w))) where > > cons x (Pair y z) = Pair (Leaf x) (Pair y z) That means we are left with one more case to handle. The case when the depths of the two trees are the same, or rather when the counter reaches 0. As we merge the two trees and create a new tree, we must also decrement the counter of the tree that follows. What this means is that we really need two instances. One where there are only two trees of the same depth in the list, and one where those two trees are followed by at least one more tree. > instance (Depth l ~ i, Depth r ~ i) => > Cons x (Pair i l (Pair Z r Nil)) > (Pair (S i) (Tree l x r) Nil) where > > cons x (Pair l (Pair r y)) = Pair (Node l x r) y As we merge the trees into a new tree, we reset and increment the depth counter. Note that we are using the first tree's counter. Reason for that is that the counter must represent the tree's depth as the tree at the front was either just inserted and so its counter is 1, or it was created when two smaller trees merged and its counter was set to its depth. Finally we must also decrement the counter of the tree that follows. > instance (Depth l ~ i, Depth r ~ i) => > Cons x (Pair i l (Pair Z r (Pair (S j) y z))) > (Pair (S i) (Tree l x r) (Pair j y z)) where > > cons x (Pair l (Pair r (Pair y z))) = Pair (Node l x r) (Pair y z) Now we can test the new cons function. > t0 = cons 'a' > $ cons (33 :: Int) > $ cons (4.4 :: Float) > $ cons (88 :: Integer) > $ cons ([1 .. 8] :: [Int]) > $ cons "moose" > $ cons ((6, 3) :: (Int, Int)) > $ nil The type is slightly more verbose. *Main> :t t0 t0 :: Pair (S (S (S Z))) (Tree (Tree (Leaf Float) Int (Leaf Integer)) Char (Tree (Leaf [Char]) [Int] (Leaf (Int, Int)))) Nil Here we introduce our wrapper for Roman numerals though we won't get to play with those just yet. > newtype R n = R { unR :: Int } deriving Show We want to get indexing and updates out of the way first. The reference implementation for the indexing function is a bit more complex than the cons function. Each of the cases we need to handle has been marked with a comment so we can see which instance matches which part of the code. index :: List a -> Int -> Maybe a index (List ((w, t) : wts)) i | i < w = index' w i t -- 1 | otherwise = index (List wts) (i - w) -- 2 where index' 1 0 (Leaf x ) = Just x -- 3 index' _ _ (Leaf _ ) = Nothing index' w i (Node l x r) | i == 0 = Just x -- 4 | i <= w' = index' w' (i - 1 ) l -- 5 | otherwise = index' w' (i - 1 - w') r -- 6 where w' = w `div` 2 index _ _ = Nothing We don't need to do anything when the index is out of range - the type system takes care of that for us. > class Index i x y | i y -> x where index :: y -> R i -> x > class IndexIf c i x y | c i y -> x where indexIf :: c -> y -> R i -> x First we handle the easy cases. > instance Index Z x (Leaf x ) where index (Leaf x ) _ = x -- 3 > instance Index Z x (Tree l x r) where index (Node _ x _) _ = x -- 4 Cases 5 and 6 require the use of a second type class so we can branch on the result of the comparison i <= w, though we rewrite it to w < i' + 1 to make use of the LessThan type family and to differentiate instance 6 from instance 4. Instead of halving the weight of the tree we are currently working on, we get the weight of one of its children. > instance ( Weight l ~ w > , LessThan w (S i) ~ c > , IndexIf c i x (Tree l y r) ) => > > Index (S i) x (Tree l y r) where > > index t _ = indexIf (undefined :: c) t (undefined :: R i) -- 5, 6 > > instance Index i x l => IndexIf F i x (Tree l y r) where > indexIf _ (Node l _ _) = index l -- 5 > > instance ( Weight r ~ w > , Sub i w ~ j > , Index j x r ) => IndexIf T i x (Tree l y r) where > > indexIf _ (Node _ _ r) _ = index r (undefined :: R j) -- 6 Cases 1 and 2 are handled in a similar way. > instance ( Weight t ~ w > , LessThan i w ~ c > , IndexIf c i x (Pair j t y) ) => Index i x (Pair j t y) where > > index = indexIf (undefined :: c) -- 1, 2 > > instance Index i x t => IndexIf T i x (Pair j t y) where > indexIf _ (Pair t _) = index t -- 1 > > instance ( Weight t ~ w > , Sub i w ~ j > , Index j x y ) => IndexIf F i x (Pair k t y) where > > indexIf _ (Pair _ y) _ = index y (undefined :: R j) -- 2 Update is similar. update :: Int -> a -> List a -> List a update i x (List ((w, t) : wts)) = List $ if i < w then (w, update' w i t) : wts -- 1 else (w, t) : unList (update (i - w) x (List wts)) -- 2 where update' 1 0 (Leaf _ ) = Leaf x -- 3 update' _ _ (Leaf _ ) = error "update" update' w i (Node l x' r) | i == 0 = Node l x r -- 4 | i <= w' = Node l' x' r -- 5 | otherwise = Node l x' r' -- 6 where w' = w `div` 2 l' = update' w' (i - 1 ) l r' = update' w' (i - 1 - w') r update _ _ _ = error "update" > class Index i x z => Update i x y z | i x y -> z where > update :: y -> R i -> x -> z > > class UpdateIf c i x y z | c i x y -> z where > updateIf :: c -> y -> R i -> x -> z > > instance Update Z x (Leaf y) (Leaf x) where > update _ _ x = Leaf x -- 3 > > instance Update Z x (Tree l y r) (Tree l x r) where > update (Node l _ r) _ x = Node l x r -- 4 > > instance ( Weight l ~ w > , LessThan w (S i) ~ c > , Index (S i) x t > , UpdateIf c i x (Tree l y r) t) => > > Update (S i) x (Tree l y r) t where > > update t _ = updateIf (undefined :: c) t (undefined :: R i) -- 5, 6 > > instance Update i x l l' => > UpdateIf F i x (Tree l y r) (Tree l' y r) where > > updateIf _ (Node l y r) i x = Node (update l i x) y r -- 5 > > instance ( Weight r ~ w > , Sub i w ~ j > , Update j x r r' ) => > > UpdateIf T i x (Tree l y r) (Tree l y r') where > > updateIf _ (Node l y r) _ x = -- 6 > Node l y (update r (undefined :: R j) x) > > instance ( Weight t ~ w > , LessThan i w ~ c > , Index i x p > , UpdateIf c i x (Pair j t y) p ) => > > Update i x (Pair j t y) p where > > update = updateIf (undefined :: c) -- 1, 2 > > instance Update i x t t' => > UpdateIf T i x (Pair j t y) (Pair j t' y) where > > updateIf _ (Pair t y) i x = Pair (update t i x) y -- 1 > > instance ( Weight t ~ w > , Sub i w ~ j > , Update j x y z ) => > > UpdateIf F i x (Pair k t y) (Pair k t z) where > > updateIf _ (Pair t y) _ x = -- 2 > Pair t (update y (undefined :: R j) x) Maybe we could combine Update and Index type classes into a single class? But we won't attempt that here. Now that we have indexing and updates, we need values we can use to index the list. Typing Z, S Z, S (S Z) and so on is too tedious and not very readable. We could use templates to predefine a whole bunch of type level numbers. That's kind of ugly though. And we can do it without using any extensions, in plain Haskell 98. We start off by making I a type synonym for S. Then we define types II to X, XX to C in steps of 10, CC to M in steps of 100 and finally we define MM and MMM. I don't know how Roman numerals are supposed to work above 3999 so that's the largest number we will be able to encode. Probably for the best as the type system doesn't seem too happy about having to deal with types of this sort. > type I n = S n > > type II n = I (I n) > type III n = I (II n) > type IV n = I (III n) > type V n = I (IV n) > type VI n = I (V n) > type VII n = I (VI n) > type VIII n = I (VII n) > type IX n = I (VIII n) > type X n = I (IX n) > > type XX n = X (X n) > type XXX n = X (XX n) > type XL n = X (XXX n) > type L n = X (XL n) > type LX n = X (L n) > type LXX n = X (LX n) > type LXXX n = X (LXX n) > type XC n = X (LXXX n) > type C n = X (XC n) > > type CC n = C (C n) > type CCC n = C (CC n) > type CD n = C (CCC n) > type D n = C (CD n) > type DC n = C (D n) > type DCC n = C (DC n) > type DCCC n = C (DCC n) > type CM n = C (DCCC n) > type M n = C (CM n) > > type MM n = M (M n) > type MMM n = M (MM n) Now for the fun part. We'd like to be able to construct only valid Roman numerals and that the type signatures match the values. We start of by defining the return and lift functions as described in Ralf Hinze's paper. We don't go all the way to creating a monad as these two functions are the only thing we need. > ret a f = f a > lift f = ret . f Now before we continue, we need a way to ensure that only valid numbers are constructed. We can group numbers in the range I to X into one group, let's call it ones, X to C into group tens, C to M into group hundreds and M, MM and MMM are in group thousands. A valid number can have at most 1 digit from each group. Digits also have to be ordered from largest to smallest, left to right. To do that, we could try and reuse the LessThen type family from before and add constraints so that a digit from the tens group can only be appended to a number less than ten. And a digit from the hundreds group can only be applied to a number less than a hundred. This approach works but it makes the GHC's type system choke and evaluating types of expressions takes minutes. We could also create a class for each of the groups and a set of combinators that can only be applied to a group of a lower rank. This works better. But we can go a step further than that - we don't actually need any type classes. All we need is one more phantom type for the rank of the number. So we introduce a second type that resembles R, only has one extra type variable. > newtype R' n s = R' { unR' :: Int } deriving Show Here we make use of ret and lift to create polyvariadic functions for constructing Roman numerals. rn starts the construction and nr finalizes it. > rn :: ((R' n s -> R n) -> r) -> r > rn f = ret (R . unR') f > > nr :: (R' Z (IV Z) -> r) -> r > nr f = f (R' 0) Trying them in ghci we get *Main> rn nr R {unR = 0} *Main> :t rn nr rn nr :: R Z We have a zero. Notice in the type signature for nr, rank of zero is 4. Now we need to generate the digits. We can use a single function to generate all of them. > mkR n = lift (\f -> f . R' . (+ n) . unR') And we encode the constraints in the type. Digits from the ones group can only be applied to a number of rank 4. There is only one number of rank 4 and that is zero. Applying a digit from the ones group to a zero gives us a number of rank 3. Digits from the tens group can be applied to numbers of ranks 3 or 4 and return a number of rank 2. And so on. > type RF n m s t k r = (R' n s -> k) -> ((R' m t -> k) -> r) -> r > > i :: RF (I n) n (III Z) (IV s) k r > ii :: RF (II n) n (III Z) (IV s) k r > iii :: RF (III n) n (III Z) (IV s) k r > iv :: RF (IV n) n (III Z) (IV s) k r > v :: RF (V n) n (III Z) (IV s) k r > vi :: RF (VI n) n (III Z) (IV s) k r > vii :: RF (VII n) n (III Z) (IV s) k r > viii :: RF (VIII n) n (III Z) (IV s) k r > ix :: RF (IX n) n (III Z) (IV s) k r > > x :: RF (X n) n (II Z) (III s) k r > xx :: RF (XX n) n (II Z) (III s) k r > xxx :: RF (XXX n) n (II Z) (III s) k r > xl :: RF (XL n) n (II Z) (III s) k r > l :: RF (L n) n (II Z) (III s) k r > lx :: RF (LX n) n (II Z) (III s) k r > lxx :: RF (LXX n) n (II Z) (III s) k r > lxxx :: RF (LXXX n) n (II Z) (III s) k r > xc :: RF (XC n) n (II Z) (III s) k r > > c :: RF (C n) n (I Z) (II s) k r > cc :: RF (CC n) n (I Z) (II s) k r > ccc :: RF (CCC n) n (I Z) (II s) k r > cd :: RF (CD n) n (I Z) (II s) k r > d :: RF (D n) n (I Z) (II s) k r > dc :: RF (DC n) n (I Z) (II s) k r > dcc :: RF (DCC n) n (I Z) (II s) k r > dccc :: RF (DCCC n) n (I Z) (II s) k r > cm :: RF (CM n) n (I Z) (II s) k r > > m :: RF (M n) n Z (I s) k r > mm :: RF (MM n) n Z (I s) k r > mmm :: RF (MMM n) n Z (I s) k r > > i = mkR 1 > ii = mkR 2 > iii = mkR 3 > iv = mkR 4 > v = mkR 5 > vi = mkR 6 > vii = mkR 7 > viii = mkR 8 > ix = mkR 9 > > x = mkR 10 > xx = mkR 20 > xxx = mkR 30 > xl = mkR 40 > l = mkR 50 > lx = mkR 60 > lxx = mkR 70 > lxxx = mkR 80 > xc = mkR 90 > > c = mkR 100 > cc = mkR 200 > ccc = mkR 300 > cd = mkR 400 > d = mkR 500 > dc = mkR 600 > dcc = mkR 700 > dccc = mkR 800 > cm = mkR 900 > > m = mkR 1000 > mm = mkR 2000 > mmm = mkR 3000 We can now try to construct a number such as 2011. > r2011 = rn mm x i nr *Main> r2011 R {unR = 2011} *Main> :t r2011 r2011 :: R (MM (X (I Z))) The type reflects the value we entered. Attempting to construct an invalid number gives us an error *Main> rn v vi nr <interactive>:1:0: Couldn't match expected type `Z' against inferred type `S s' Probable cause: `rn' is applied to too many arguments In the expression: rn v vi nr In the definition of `it': it = rn v vi nr I'll finish off this post with a generic map function. Here we use the type equality trick from the HList paper. > class GMap t p q | t p -> q where gmap :: t -> p -> q > class GMapIf c t p q | c t p -> q where gmapIf :: c -> t -> p -> q > > instance GMap (a -> b) Nil Nil where gmap _ = id > > instance ( TypeEq a x c > , GMapIf c (a -> b) (Leaf x) (Leaf y) ) => > > GMap (a -> b) (Leaf x) (Leaf y) where > > gmap = gmapIf (undefined :: c) > > instance ( TypeEq a x c > , GMapIf c (a -> b) (Tree l x r) (Tree l' y r') ) => > > GMap (a -> b) (Tree l x r) (Tree l' y r') where > > gmap = gmapIf (undefined :: c) > > instance ( GMap (a -> b) x y > , GMap (a -> b) p q ) => > > GMap (a -> b) (Pair i x p) (Pair i y q) where > > gmap f (Pair x p) = Pair (gmap f x) (gmap f p) > > instance GMapIf F (a -> b) (Leaf x) (Leaf x) where gmapIf _ _ = id > > instance GMapIf T (a -> b) (Leaf a) (Leaf b) where > gmapIf _ f (Leaf a) = Leaf (f a) > > instance ( GMap (a -> b) l l' > , GMap (a -> b) r r' ) => > > GMapIf F (a -> b) (Tree l x r) (Tree l' x r') where > > gmapIf _ f (Node l x r) = Node (gmap f l) x (gmap f r) > > instance ( GMap (a -> b) l l' > , GMap (a -> b) r r' ) => > > GMapIf T (a -> b) (Tree l a r) (Tree l' b r') where > > gmapIf _ f (Node l a r) = Node (gmap f l) (f a) (gmap f r) > > type family Cast a > type family Cast' t a > type family Cast'' t a > > type instance Cast a = Cast' () a > type instance Cast' t a = Cast'' t a > type instance Cast'' () a = a > > class TypeEq x y c | x y -> c > > instance Cast c ~ F => TypeEq x y c > > instance TypeEq Char Char T > instance TypeEq Int Int T > instance TypeEq Float Float T > instance TypeEq a a T => TypeEq [a] [a] T And a few tests to see if it all works. > t1 = gmap (length :: String -> Int) t0 > t2 = gmap (length :: [Int] -> Int) t1 > t3 = gmap ((+ 1000) :: Int -> Int) t2 > > t4 = cons (t0 `index` rn iv nr) t3 > > t5 = update t4 (rn iv nr) "asdf" > > t1' = gmap (length :: String -> Int) t0' > t2' = gmap (length :: [Int] -> Int) t1' > t3' = gmap ((+ 1000) :: Int -> Int) t2' > > t4' = cons' (t0' `index` rn iv nr) t3' > > t5' = update t4' (rn iv nr) "asdf" As a bonus the implementation of type-level Roman numerals in Standard ML. SML/NJ has a fit trying to load the code. It seems to cope with it if constructors for values above 100 are commented out. And it gives really nice type signatures. MLton has no problems compiling the code, but fully expands all type signatures. (**********************************************************************) signature ROMAN = sig type z type 'n i type 'n ii = 'n i i type 'n iii = 'n i ii type 'n iv = 'n i iii type 'n v = 'n i iv type 'n vi = 'n i v type 'n vii = 'n i vi type 'n viii = 'n i vii type 'n ix = 'n i viii type 'n x = 'n i ix type 'n xx = 'n x x type 'n xxx = 'n x xx type 'n xl = 'n x xxx type 'n l = 'n x xl type 'n lx = 'n x l type 'n lxx = 'n x lx type 'n lxxx = 'n x lxx type 'n xc = 'n x lxxx type 'n c = 'n x xc type 'n cc = 'n c c type 'n ccc = 'n c cc type 'n cd = 'n c ccc type 'n d = 'n c cd type 'n dc = 'n c d type 'n dcc = 'n c dc type 'n dccc = 'n c dcc type 'n cm = 'n c dccc type 'n m = 'n c cm type 'n mm = 'n m m type 'n mmm = 'n m mm type 'n r type ('n, 's) r' val toInt : 'n r -> int val <| : ((('n, 's) r' -> 'n r) -> 'r) -> 'r val |> : ((z, z iv) r' -> 'r) -> 'r type ('n, 'm, 's, 't, 'k, 'r) rf = (('n, 's) r' -> 'k) -> ((('m, 't) r' -> 'k) -> 'r) -> 'r val i : ('n i , 'n, z iii, 's iv , 'k, 'r) rf val ii : ('n ii , 'n, z iii, 's iv , 'k, 'r) rf val iii : ('n iii , 'n, z iii, 's iv , 'k, 'r) rf val iv : ('n iv , 'n, z iii, 's iv , 'k, 'r) rf val v : ('n v , 'n, z iii, 's iv , 'k, 'r) rf val vi : ('n vi , 'n, z iii, 's iv , 'k, 'r) rf val vii : ('n vii , 'n, z iii, 's iv , 'k, 'r) rf val viii : ('n viii, 'n, z iii, 's iv , 'k, 'r) rf val ix : ('n ix , 'n, z iii, 's iv , 'k, 'r) rf val x : ('n x , 'n, z ii , 's iii, 'k, 'r) rf val xx : ('n xx , 'n, z ii , 's iii, 'k, 'r) rf val xxx : ('n xxx , 'n, z ii , 's iii, 'k, 'r) rf val xl : ('n xl , 'n, z ii , 's iii, 'k, 'r) rf val l : ('n l , 'n, z ii , 's iii, 'k, 'r) rf val lx : ('n lx , 'n, z ii , 's iii, 'k, 'r) rf val lxx : ('n lxx , 'n, z ii , 's iii, 'k, 'r) rf val lxxx : ('n lxxx, 'n, z ii , 's iii, 'k, 'r) rf val xc : ('n xc , 'n, z ii , 's iii, 'k, 'r) rf val c : ('n c , 'n, z i , 's ii , 'k, 'r) rf val cc : ('n cc , 'n, z i , 's ii , 'k, 'r) rf val ccc : ('n ccc , 'n, z i , 's ii , 'k, 'r) rf val cd : ('n cd , 'n, z i , 's ii , 'k, 'r) rf val d : ('n d , 'n, z i , 's ii , 'k, 'r) rf val dc : ('n dc , 'n, z i , 's ii , 'k, 'r) rf val dcc : ('n dcc , 'n, z i , 's ii , 'k, 'r) rf val dccc : ('n dccc, 'n, z i , 's ii , 'k, 'r) rf val cm : ('n cm , 'n, z i , 's ii , 'k, 'r) rf val m : ('n m , 'n, z , 's i , 'k, 'r) rf val mm : ('n mm , 'n, z , 's i , 'k, 'r) rf val mmm : ('n mmm , 'n, z , 's i , 'k, 'r) rf end structure Roman :> ROMAN = struct datatype z = Z datatype 'n i = I of 'n type 'n ii = 'n i i type 'n iii = 'n i ii type 'n iv = 'n i iii type 'n v = 'n i iv type 'n vi = 'n i v type 'n vii = 'n i vi type 'n viii = 'n i vii type 'n ix = 'n i viii type 'n x = 'n i ix type 'n xx = 'n x x type 'n xxx = 'n x xx type 'n xl = 'n x xxx type 'n l = 'n x xl type 'n lx = 'n x l type 'n lxx = 'n x lx type 'n lxxx = 'n x lxx type 'n xc = 'n x lxxx type 'n c = 'n x xc type 'n cc = 'n c c type 'n ccc = 'n c cc type 'n cd = 'n c ccc type 'n d = 'n c cd type 'n dc = 'n c d type 'n dcc = 'n c dc type 'n dccc = 'n c dcc type 'n cm = 'n c dccc type 'n m = 'n c cm type 'n mm = 'n m m type 'n mmm = 'n m mm type 'n r = int datatype ('n, 's) r' = R of int type ('n, 'm, 's, 't, 'k, 'r) rf = (('n, 's) r' -> 'k) -> ((('m, 't) r' -> 'k) -> 'r) -> 'r fun toInt n = n local fun unR (R n) = n fun ret a f = f a fun lift f = ret o f fun mkR n k = lift (fn g => g o R o (fn x => x + n) o unR) k in fun <| f = ret unR f fun |> f = f (R 0) fun i k = mkR 1 k fun ii k = mkR 2 k fun iii k = mkR 3 k fun iv k = mkR 4 k fun v k = mkR 5 k fun vi k = mkR 6 k fun vii k = mkR 7 k fun viii k = mkR 8 k fun ix k = mkR 9 k fun x k = mkR 10 k fun xx k = mkR 20 k fun xxx k = mkR 30 k fun xl k = mkR 40 k fun l k = mkR 50 k fun lx k = mkR 60 k fun lxx k = mkR 70 k fun lxxx k = mkR 80 k fun xc k = mkR 90 k fun c k = mkR 100 k fun cc k = mkR 200 k fun ccc k = mkR 300 k fun cd k = mkR 400 k fun d k = mkR 500 k fun dc k = mkR 600 k fun dcc k = mkR 700 k fun dccc k = mkR 800 k fun cm k = mkR 900 k fun m k = mkR 1000 k fun mm k = mkR 2000 k fun mmm k = mkR 3000 k end end

1 0

alex 3.0 broken with Data.ByteString.Lazy - w2c conversion missing (fix attached)
by Eugene Kirpichov 10 Aug '11

10 Aug '11

Hi Simon, I found a bug in alex-3.0 and I'm attaching a fixed source file - templates/wrappers.hs (modified against alex-3.0 from cabal unpack). Explanation: I was installing bytestring-lexing 0.2.1 and it failed to install with alex 3.0, which was released on Aug 4. It succeeded, however, with the most recent earlier alex 2.3.5. Turns out that the wrapper for lazy bytestrings (strict are ok) had alexGetByte not doing w2c conversion: alexGetByte (_, cs) | ByteString.null cs = Nothing | otherwise = Just (ByteString.head cs, (ByteString.head cs, ByteString.tail cs)) It should say ByteString.w2c $ ByteString.head cs here. With this and an additional import of Data.ByteString.Internal (w2c), the generated code compiles. To reproduce, cabal unpack bytestring-lexing and try installing it. Installation will fail, then manually alex the .x files in Data/ByteString/Lex{,/Lazy} and try ghci'ing to them, doing the modification I did and ghci'ing again. -- Eugene Kirpichov Principal Engineer, Mirantis Inc. http://www.mirantis.com/ Editor, http://fprog.ru/

2 1

Type level Roman numerals and skew binary random access lists
by Ivan Tomac 10 Aug '11

10 Aug '11

I've recently been playing with Sebastian Fischer's explicit sharing monad library (found at http://sebfisch.github.com/explicit-sharing) and after looking at the code noticed the implementation memoizes values into an IntMap of untyped values that are coerced into the correct type on retrieval, which is a sensible and practical way to implement this. Just for fun I thought I'd have a go at implementing a (very impractical) version without type casting but, disappointingly, I didn't quite get there. I ran out of steam by the time I got around to playing with parameterized monads by which stage the type signatures started looking a bit scary. That and I needed to get back to my projects. This has been sitting on my hard drive for a couple of weeks now and I've finally decided to clean it up and post it, maybe someone else will find it amusing. The post is about HList inspired type level implementation of Okasaki's skew binary random access lists indexed by Roman numerals, using ideas from Ralf Hinze's paper "Functional Pearl: Typed Quote/Antiquote - Or: Compile-time Parsing" and some fun tricks from the MLton wiki: http://www.cs.ox.ac.uk/ralf.hinze/publications/Quote.pdf http://mlton.org/Fold http://mlton.org/Fold01N http://mlton.org/VariableArityPolymorphism With that out of the way, we start of by declaring all the different extensions we'll need. > {-# LANGUAGE FlexibleInstances #-} > {-# LANGUAGE FunctionalDependencies #-} > {-# LANGUAGE MultiParamTypeClasses #-} > {-# LANGUAGE ScopedTypeVariables #-} > {-# LANGUAGE TypeFamilies #-} > {-# LANGUAGE TypeSynonymInstances #-} These two are ugly. We need undecidable instances for bunch of things and overlapping instances for the type equality trick borrowed from the HList paper: http://homepages.cwi.nl/~ralf/HList/paper.pdf > {-# LANGUAGE OverlappingInstances #-} > {-# LANGUAGE UndecidableInstances #-} For GHC 7 we also need to increase the context stack. > {-# OPTIONS_GHC -fcontext-stack=100 #-} Define Boolean values at the type level. > data T = T > data F = F And now Peano numbers. We don't actually use the constructors for anything but if we omitted them we'd have to use another extension, EmptyDataDecls. > data Z = Z > data S n = S n Here we create some types for heterogeneous lists and trees. Note that Pair has an extra type parameter. We provide two different versions of the cons operation. One requires that extra parameter but does not require undecidable instances. Unfortunately we still need undecidable instances later on for indexing. > data Pair i x y = Pair x y deriving Show > data Nil = Nil deriving Show > data Tree l x r = Node l x r deriving Show > data Leaf x = Leaf x deriving Show > > type Pair' x y = Pair () x y > > nil :: Nil > nil = Nil Equality, less than, addition, subtraction and multiplication by 2 type functions for Peano numbers. > type family Equals m n > > type instance Equals Z Z = T > type instance Equals Z (S n) = F > type instance Equals (S n) Z = F > type instance Equals (S m) (S n) = Equals m n > > type family LessThan m n > > type instance LessThan Z Z = F > type instance LessThan Z (S n) = T > type instance LessThan (S n) Z = F > type instance LessThan (S m) (S n) = LessThan m n > > type family Add m n > > type instance Add Z n = n > type instance Add n Z = n > type instance Add (S m) (S n) = S (S (Add m n)) > > type family Sub m n > > type instance Sub n Z = n > type instance Sub (S m) (S n) = Sub m n > > type family Mul2 n > > type instance Mul2 Z = Z > type instance Mul2 (S n) = S (S (Mul2 n)) And finally tree depth and weight/size. > type family Depth t > > type instance Depth (Leaf x ) = S Z > type instance Depth (Tree l x r) = S (Depth l) > > type family Weight t > > type instance Weight (Leaf x ) = S Z > type instance Weight (Tree l x r) = S (Mul2 (Weight l)) For reference, here is normal implementation of random access lists newtype List a = List { unList :: [(Int, Tree a)] } deriving Show data Tree a = Leaf a | Node (Tree a) a (Tree a) deriving Show cons :: a -> List a -> List a cons x (List wts) = List $ case wts of (v, l) : (w, r) : wts' | v == w -> (1 + w + w, Node l x r) : wts' _ -> (1 , Leaf x ) : wts List here is a list of pairs of balanced binary trees and their weights. The cons function has exactly two cases. The second case is trivial, we are mostly interested in the first case. If the weights of the two trees at the front of the list are the same, we combine them into a new tree with the newly inserted element at the top. Now we are ready to implement cons. This first version is simpler but requires undecidable instances. > class Cons' x y z | x y -> z where cons' :: x -> y -> z Here we cover the cases of inserting an element into an empty list, and inserting an element into a list with a single element. These cover two out of four different possibilities when inserting a new element. > instance Cons' x Nil (Pair' (Leaf x) Nil) where cons' = Pair . Leaf > > instance Cons' x (Pair' y Nil) (Pair' (Leaf x) (Pair' y Nil)) where > cons' = Pair . Leaf The remaining two cases occur when we have at least two elements in the list. This is where we need to compare weights of trees. First observation is that we don't need weight of a tree, depth is sufficient. Now we have a problem. We'd like to be able to write something like instance (Depth l ~ u, Depth r ~ v, Equals u v ~ T) => Cons' x (Pair' l (Pair' r y)) (Pair' (Tree l x r) y) where ... instance (Depth l ~ u, Depth r ~ v, Equals u v ~ F) => Cons' x y (Pair' (Leaf x) y) where ... but we get a functional dependency conflict in the second instance as the type variable y might stand for Pair' l (Pair' r y) and the functional dependency already says the result should be Pair' (Tree l x r) y, not Pair' (Leaf x) (Pair' l (Pair' r y)) We need to merge these two instances into one and then branch on the result of the comparison of tree depths. To do this, we introduce another type class to do the branching. > class ConsIf c x y z | c x y -> z where consIf :: c -> x -> y -> z And merge the instances. > instance ( Depth l ~ u > , Depth r ~ v > , Equals u v ~ c > , ConsIf c x (Pair' l (Pair' r y)) z ) => > > Cons' x (Pair' l (Pair' r y)) z where > > cons' = consIf (undefined :: c) > > instance ConsIf F x y (Pair' (Leaf x) y) where consIf _ = Pair . Leaf > > instance (Depth l ~ u, Depth r ~ u) => > > ConsIf T x (Pair' l (Pair' r y)) (Pair' (Tree l x r) y) where > > consIf _ x (Pair l (Pair r y)) = Pair (Node l x r) y We can now test our cons function. > t0' = cons' 'a' > $ cons' (33 :: Int) > $ cons' (4.4 :: Float) > $ cons' (88 :: Integer) > $ cons' ([1 .. 8] :: [Int]) > $ cons' "moose" > $ cons' ((6, 3) :: (Int, Int)) > $ nil And ghci tells us the type is *Main> :t t0' t0' :: Pair' (Tree (Tree (Leaf Float) Int (Leaf Integer)) Char (Tree (Leaf [Char]) [Int] (Leaf (Int, Int)))) Nil Now we get to the second version that doesn't need the undecidable instances extension. In this one we go a step back and attempt to keep track of depth information in the type of the list. When we again end up at the point where we need to compare if two trees at the front of the list are of the same depth, we run into a problem. instance Cons x (Pair i l (Pair i r y)) (Pair (S i) (Tree l x r) y) where ... instance Cons x (Pair i y (Pair j z w)) (Pair (S Z) x (Pair i y (Pair j z w))) where ... This clearly won't work as we again get a functional dependency conflict. The j type variable could be the same as i in which case we have two different rules for what the result of consing x with (Pair i l (Pair i r y)) should be. As we don't want to use undecidable instances, we are stuck. Unless we can find a way to disambiguate the two instances. Instead of keeping track of depth information, we could try to track how many elements we need to complete a new tree. That way instead of counting up, we are counting down towards zero and it becomes easy to differentiate the two instances as only the one where the depths of the two trees are equal will contain a Z. Keeping track of how many elements are missing turns out to be a problem, at least as long as we don't want to use undecidable instances. Fortunately we can replace the number of elements missing with the number of levels the tree at the front needs before its depth matches the tree that follows. > class Cons x y z | x y -> z where cons :: x -> y -> z Inserting an element into an empty list involves adding the element to the front and setting its the depth counter to 1. > instance Cons x Nil (Pair (S Z) (Leaf x) Nil) where cons = Pair . Leaf If we are inserting an element into a list that already has a single tree, we again add the new element to the front, set its counter to 1 and we decrement the counter of the tree that now follows the newly inserted element. > instance Cons x (Pair (S i) y Nil) (Pair (S Z) (Leaf x) (Pair i y Nil)) where > cons x (Pair y z) = Pair (Leaf x) (Pair y z) Here we have the case where the list already contains at least two trees but their depths are not equal. Like with the previous instance we insert the new element to the front and decrement the counter of the tree that now follows it. > instance Cons x (Pair (S i) y (Pair (S j) z w)) > (Pair (S Z) (Leaf x) (Pair i y (Pair (S j) z w))) where > > cons x (Pair y z) = Pair (Leaf x) (Pair y z) That means we are left with one more case to handle. The case when the depths of the two trees are the same, or rather when the counter reaches 0. As we merge the two trees and create a new tree, we must also decrement the counter of the tree that follows. What this means is that we really need two instances. One where there are only two trees of the same depth in the list, and one where those two trees are followed by at least one more tree. > instance (Depth l ~ i, Depth r ~ i) => > Cons x (Pair i l (Pair Z r Nil)) (Pair (S i) (Tree l x r) Nil) where > > cons x (Pair l (Pair r y)) = Pair (Node l x r) y As we merge the trees into a new tree, we reset and increment the depth counter. Note that we are using the first tree's counter. Reason for that is that the counter must represent the tree's depth as the tree at the front was either just inserted and so its counter is 1, or it was created when two smaller trees merged and its counter was set to its depth. Finally we must also decrement the counter of the tree that follows. > instance (Depth l ~ i, Depth r ~ i) => > Cons x (Pair i l (Pair Z r (Pair (S j) y z))) > (Pair (S i) (Tree l x r) (Pair j y z)) where > > cons x (Pair l (Pair r (Pair y z))) = Pair (Node l x r) (Pair y z) Now we can test the new cons function. > t0 = cons 'a' > $ cons (33 :: Int) > $ cons (4.4 :: Float) > $ cons (88 :: Integer) > $ cons ([1 .. 8] :: [Int]) > $ cons "moose" > $ cons ((6, 3) :: (Int, Int)) > $ nil The type is slightly more verbose. *Main> :t t0 t0 :: Pair (S (S (S Z))) (Tree (Tree (Leaf Float) Int (Leaf Integer)) Char (Tree (Leaf [Char]) [Int] (Leaf (Int, Int)))) Nil Here we introduce our wrapper for Roman numerals though we won't get to play with those just yet. > newtype R n = R { unR :: Int } deriving Show We want to get indexing and updates out of the way first. The reference implementation for the indexing function is a bit more complex than the cons function. Each of the cases we need to handle has been marked with a comment so we can see which instance matches which part of the code. index :: List a -> Int -> Maybe a index (List ((w, t) : wts)) i | i < w = index' w i t -- 1 | otherwise = index (List wts) (i - w) -- 2 where index' 1 0 (Leaf x ) = Just x -- 3 index' _ _ (Leaf _ ) = Nothing index' w i (Node l x r) | i == 0 = Just x -- 4 | i <= w' = index' w' (i - 1 ) l -- 5 | otherwise = index' w' (i - 1 - w') r -- 6 where w' = w `div` 2 index _ _ = Nothing We don't need to do anything when the index is out of range - the type system takes care of that for us. > class Index i x y | i y -> x where index :: y -> R i -> x > class IndexIf c i x y | c i y -> x where indexIf :: c -> y -> R i -> x First we handle the easy cases. > instance Index Z x (Leaf x ) where index (Leaf x ) _ = x -- 3 > instance Index Z x (Tree l x r) where index (Node _ x _) _ = x -- 4 Cases 5 and 6 require the use of a second type class so we can branch on the result of the comparison i <= w, though we rewrite it to w < i' + 1 to make use of the LessThan type family and to differentiate instance 6 from instance 4. Instead of halving the weight of the tree we are currently working on, we get the weight of one of its children. > instance ( Weight l ~ w > , LessThan w (S i) ~ c > , IndexIf c i x (Tree l y r) ) => Index (S i) x (Tree l y r) where > > index t _ = indexIf (undefined :: c) t (undefined :: R i) -- 5, 6 > > instance Index i x l => IndexIf F i x (Tree l y r) where > indexIf _ (Node l _ _) = index l -- 5 > > instance ( Weight r ~ w > , Sub i w ~ j > , Index j x r ) => IndexIf T i x (Tree l y r) where > > indexIf _ (Node _ _ r) _ = index r (undefined :: R j) -- 6 Cases 1 and 2 are handled in a similar way. > instance ( Weight t ~ w > , LessThan i w ~ c > , IndexIf c i x (Pair j t y) ) => Index i x (Pair j t y) where > > index = indexIf (undefined :: c) -- 1, 2 > > instance Index i x t => IndexIf T i x (Pair j t y) where > indexIf _ (Pair t _) = index t -- 1 > > instance ( Weight t ~ w > , Sub i w ~ j > , Index j x y ) => IndexIf F i x (Pair k t y) where > > indexIf _ (Pair _ y) _ = index y (undefined :: R j) -- 2 Update is similar. update :: Int -> a -> List a -> List a update i x (List ((w, t) : wts)) = List $ if i < w then (w, update' w i t) : wts -- 1 else (w, t) : unList (update (i - w) x (List wts)) -- 2 where update' 1 0 (Leaf _ ) = Leaf x -- 3 update' _ _ (Leaf _ ) = error "update" update' w i (Node l x' r) | i == 0 = Node l x r -- 4 | i <= w' = Node l' x' r -- 5 | otherwise = Node l x' r' -- 6 where w' = w `div` 2 l' = update' w' (i - 1 ) l r' = update' w' (i - 1 - w') r update _ _ _ = error "update" > class Index i x z => Update i x y z | i x y -> z where > update :: y -> R i -> x -> z > > class UpdateIf c i x y z | c i x y -> z where > updateIf :: c -> y -> R i -> x -> z > > instance Update Z x (Leaf y) (Leaf x) where > update _ _ x = Leaf x -- 3 > > instance Update Z x (Tree l y r) (Tree l x r) where > update (Node l _ r) _ x = Node l x r -- 4 > > instance ( Weight l ~ w > , LessThan w (S i) ~ c > , Index (S i) x t > , UpdateIf c i x (Tree l y r) t) => > > Update (S i) x (Tree l y r) t where > > update t _ = updateIf (undefined :: c) t (undefined :: R i) -- 5, 6 > > instance Update i x l l' => UpdateIf F i x (Tree l y r) (Tree l' y r) where > updateIf _ (Node l y r) i x = Node (update l i x) y r -- 5 > > instance ( Weight r ~ w > , Sub i w ~ j > , Update j x r r' ) => > > UpdateIf T i x (Tree l y r) (Tree l y r') where > > updateIf _ (Node l y r) _ x = -- 6 > Node l y (update r (undefined :: R j) x) > > instance ( Weight t ~ w > , LessThan i w ~ c > , Index i x p > , UpdateIf c i x (Pair j t y) p ) => Update i x (Pair j t y) p where > > update = updateIf (undefined :: c) -- 1, 2 > > instance Update i x t t' => UpdateIf T i x (Pair j t y) (Pair j t' y) where > updateIf _ (Pair t y) i x = Pair (update t i x) y -- 1 > > instance ( Weight t ~ w > , Sub i w ~ j > , Update j x y z ) => UpdateIf F i x (Pair k t y) (Pair k t z) where > > updateIf _ (Pair t y) _ x = -- 2 > Pair t (update y (undefined :: R j) x) Maybe we could combine Update and Index type classes into a single class? But we won't attempt that here. Now that we have indexing and updates, we need values we can use to index the list. Typing Z, S Z, S (S Z) and so on is too tedious and not very readable. We could use templates to predefine a whole bunch of type level numbers. That's kind of ugly though. And we can do it without using any extensions, in plain Haskell 98. We start off by making I a type synonym for S. Then we define types II to X, XX to C in steps of 10, CC to M in steps of 100 and finally we define MM and MMM. I don't know how Roman numerals are supposed to work above 3999 so that's the largest number we will be able to encode. Probably for the best as the type system doesn't seem too happy about having to deal with types of this sort. > type I n = S n > > type II n = I (I n) > type III n = I (II n) > type IV n = I (III n) > type V n = I (IV n) > type VI n = I (V n) > type VII n = I (VI n) > type VIII n = I (VII n) > type IX n = I (VIII n) > type X n = I (IX n) > > type XX n = X (X n) > type XXX n = X (XX n) > type XL n = X (XXX n) > type L n = X (XL n) > type LX n = X (L n) > type LXX n = X (LX n) > type LXXX n = X (LXX n) > type XC n = X (LXXX n) > type C n = X (XC n) > > type CC n = C (C n) > type CCC n = C (CC n) > type CD n = C (CCC n) > type D n = C (CD n) > type DC n = C (D n) > type DCC n = C (DC n) > type DCCC n = C (DCC n) > type CM n = C (DCCC n) > type M n = C (CM n) > > type MM n = M (M n) > type MMM n = M (MM n) Now for the fun part. We'd like to be able to construct only valid Roman numerals and that the type signatures match the values. We start of by defining the return and lift functions as described in Ralf Hinze's paper. We don't go all the way to creating a monad as these two functions are the only thing we need. > ret a f = f a > lift f = ret . f Now before we continue, we need a way to ensure that only valid numbers are constructed. We can group numbers in the range I to X into one group, let's call it ones, X to C into group tens, C to M into group hundreds and M, MM and MMM are in group thousands. A valid number can have at most 1 digit from each group. Digits also have to be ordered from largest to smallest, left to right. To do that, we could try and reuse the LessThen type family from before and add constraints so that a digit from the tens group can only be appended to a number less than ten. And a digit from the hundreds group can only be applied to a number less than a hundred. This approach works but it makes the GHC's type system choke and evaluating types of expressions takes minutes. We could also create a class for each of the groups and a set of combinators that can only be applied to a group of a lower rank. This works better. But we can go a step further than that - we don't actually need any type classes. All we need is one more phantom type for the rank of the number. So we introduce a second type that resembles R, only has one extra type variable. > newtype R' n s = R' { unR' :: Int } deriving Show Here we make use of ret and lift to create polyvariadic functions for constructing Roman numerals. rn starts the construction and nr finalizes it. > rn :: ((R' n s -> R n) -> r) -> r > rn f = ret (R . unR') f > > nr :: (R' Z (IV Z) -> r) -> r > nr f = f (R' 0) Trying them in ghci we get *Main> rn nr R {unR = 0} *Main> :t rn nr rn nr :: R Z We have a zero. Notice in the type signature for nr, rank of zero is 4. Now we need to generate the digits. We can use a single function to generate all of them. > mkR n = lift (\f -> f . R' . (+ n) . unR') And we encode the constraints in the type. Digits from the ones group can only be applied to a number of rank 4. There is only one number of rank 4 and that is zero. Applying a digit from the ones group to a zero gives us a number of rank 3. Digits from the tens group can be applied to numbers of ranks 3 or 4 and return a number of rank 2. And so on. > type RF n m s t k r = (R' n s -> k) -> ((R' m t -> k) -> r) -> r > > i :: RF (I n) n (III Z) (IV s) k r > ii :: RF (II n) n (III Z) (IV s) k r > iii :: RF (III n) n (III Z) (IV s) k r > iv :: RF (IV n) n (III Z) (IV s) k r > v :: RF (V n) n (III Z) (IV s) k r > vi :: RF (VI n) n (III Z) (IV s) k r > vii :: RF (VII n) n (III Z) (IV s) k r > viii :: RF (VIII n) n (III Z) (IV s) k r > ix :: RF (IX n) n (III Z) (IV s) k r > > x :: RF (X n) n (II Z) (III s) k r > xx :: RF (XX n) n (II Z) (III s) k r > xxx :: RF (XXX n) n (II Z) (III s) k r > xl :: RF (XL n) n (II Z) (III s) k r > l :: RF (L n) n (II Z) (III s) k r > lx :: RF (LX n) n (II Z) (III s) k r > lxx :: RF (LXX n) n (II Z) (III s) k r > lxxx :: RF (LXXX n) n (II Z) (III s) k r > xc :: RF (XC n) n (II Z) (III s) k r > > c :: RF (C n) n (I Z) (II s) k r > cc :: RF (CC n) n (I Z) (II s) k r > ccc :: RF (CCC n) n (I Z) (II s) k r > cd :: RF (CD n) n (I Z) (II s) k r > d :: RF (D n) n (I Z) (II s) k r > dc :: RF (DC n) n (I Z) (II s) k r > dcc :: RF (DCC n) n (I Z) (II s) k r > dccc :: RF (DCCC n) n (I Z) (II s) k r > cm :: RF (CM n) n (I Z) (II s) k r > > m :: RF (M n) n Z (I s) k r > mm :: RF (MM n) n Z (I s) k r > mmm :: RF (MMM n) n Z (I s) k r > > i = mkR 1 > ii = mkR 2 > iii = mkR 3 > iv = mkR 4 > v = mkR 5 > vi = mkR 6 > vii = mkR 7 > viii = mkR 8 > ix = mkR 9 > > x = mkR 10 > xx = mkR 20 > xxx = mkR 30 > xl = mkR 40 > l = mkR 50 > lx = mkR 60 > lxx = mkR 70 > lxxx = mkR 80 > xc = mkR 90 > > c = mkR 100 > cc = mkR 200 > ccc = mkR 300 > cd = mkR 400 > d = mkR 500 > dc = mkR 600 > dcc = mkR 700 > dccc = mkR 800 > cm = mkR 900 > > m = mkR 1000 > mm = mkR 2000 > mmm = mkR 3000 We can now try to construct a number such as 2011. > r2011 = rn mm x i nr *Main> r2011 R {unR = 2011} *Main> :t r2011 r2011 :: R (MM (X (I Z))) The type reflects the value we entered. Attempting to construct an invalid number gives us an error *Main> rn v vi nr <interactive>:1:0: Couldn't match expected type `Z' against inferred type `S s' Probable cause: `rn' is applied to too many arguments In the expression: rn v vi nr In the definition of `it': it = rn v vi nr I'll finish off this post with a generic map function. Here we use the type equality trick from the HList paper. > class GMap t p q | t p -> q where gmap :: t -> p -> q > class GMapIf c t p q | c t p -> q where gmapIf :: c -> t -> p -> q > > instance GMap (a -> b) Nil Nil where gmap _ = id > > instance ( TypeEq a x c > , GMapIf c (a -> b) (Leaf x) (Leaf y) ) => > > GMap (a -> b) (Leaf x) (Leaf y) where gmap = gmapIf (undefined :: c) > > instance ( TypeEq a x c > , GMapIf c (a -> b) (Tree l x r) (Tree l' y r') ) => > > GMap (a -> b) (Tree l x r) (Tree l' y r') where > > gmap = gmapIf (undefined :: c) > > instance ( GMap (a -> b) x y > , GMap (a -> b) p q ) => > > GMap (a -> b) (Pair i x p) (Pair i y q) where > > gmap f (Pair x p) = Pair (gmap f x) (gmap f p) > > instance GMapIf F (a -> b) (Leaf x) (Leaf x) where gmapIf _ _ = id > > instance GMapIf T (a -> b) (Leaf a) (Leaf b) where > gmapIf _ f (Leaf a) = Leaf (f a) > > instance ( GMap (a -> b) l l' > , GMap (a -> b) r r' ) => > > GMapIf F (a -> b) (Tree l x r) (Tree l' x r') where > > gmapIf _ f (Node l x r) = Node (gmap f l) x (gmap f r) > > instance ( GMap (a -> b) l l' > , GMap (a -> b) r r' ) => > > GMapIf T (a -> b) (Tree l a r) (Tree l' b r') where > > gmapIf _ f (Node l a r) = Node (gmap f l) (f a) (gmap f r) > > type family Cast a > type family Cast' t a > type family Cast'' t a > > type instance Cast a = Cast' () a > type instance Cast' t a = Cast'' t a > type instance Cast'' () a = a > > class TypeEq x y c | x y -> c > > instance Cast c ~ F => TypeEq x y c > > instance TypeEq Char Char T > instance TypeEq Int Int T > instance TypeEq Float Float T > instance TypeEq a a T => TypeEq [a] [a] T And a few tests to see if it all works. > t1 = gmap (length :: String -> Int) t0 > t2 = gmap (length :: [Int] -> Int) t1 > t3 = gmap ((+ 1000) :: Int -> Int) t2 > > t4 = cons (t0 `index` rn iv nr) t3 > > t5 = update t4 (rn iv nr) "asdf" > > t1' = gmap (length :: String -> Int) t0' > t2' = gmap (length :: [Int] -> Int) t1' > t3' = gmap ((+ 1000) :: Int -> Int) t2' > > t4' = cons' (t0' `index` rn iv nr) t3' > > t5' = update t4' (rn iv nr) "asdf" As a bonus the implementation of type-level Roman numerals in Standard ML. SML/NJ has a fit trying to load the code. It seems to cope with it if constructors for values above 100 are commented out. And it gives really nice type signatures. MLton has no problems compiling the code, but fully expands all type signatures. (*****************************************************************************) signature ROMAN = sig type z type 'n i type 'n ii = 'n i i type 'n iii = 'n i ii type 'n iv = 'n i iii type 'n v = 'n i iv type 'n vi = 'n i v type 'n vii = 'n i vi type 'n viii = 'n i vii type 'n ix = 'n i viii type 'n x = 'n i ix type 'n xx = 'n x x type 'n xxx = 'n x xx type 'n xl = 'n x xxx type 'n l = 'n x xl type 'n lx = 'n x l type 'n lxx = 'n x lx type 'n lxxx = 'n x lxx type 'n xc = 'n x lxxx type 'n c = 'n x xc type 'n cc = 'n c c type 'n ccc = 'n c cc type 'n cd = 'n c ccc type 'n d = 'n c cd type 'n dc = 'n c d type 'n dcc = 'n c dc type 'n dccc = 'n c dcc type 'n cm = 'n c dccc type 'n m = 'n c cm type 'n mm = 'n m m type 'n mmm = 'n m mm type 'n r type ('n, 's) r' val toInt : 'n r -> int val <| : ((('n, 's) r' -> 'n r) -> 'r) -> 'r val |> : ((z, z iv) r' -> 'r) -> 'r type ('n, 'm, 's, 't, 'k, 'r) rf = (('n, 's) r' -> 'k) -> ((('m, 't) r' -> 'k) -> 'r) -> 'r val i : ('n i , 'n, z iii, 's iv , 'k, 'r) rf val ii : ('n ii , 'n, z iii, 's iv , 'k, 'r) rf val iii : ('n iii , 'n, z iii, 's iv , 'k, 'r) rf val iv : ('n iv , 'n, z iii, 's iv , 'k, 'r) rf val v : ('n v , 'n, z iii, 's iv , 'k, 'r) rf val vi : ('n vi , 'n, z iii, 's iv , 'k, 'r) rf val vii : ('n vii , 'n, z iii, 's iv , 'k, 'r) rf val viii : ('n viii, 'n, z iii, 's iv , 'k, 'r) rf val ix : ('n ix , 'n, z iii, 's iv , 'k, 'r) rf val x : ('n x , 'n, z ii , 's iii, 'k, 'r) rf val xx : ('n xx , 'n, z ii , 's iii, 'k, 'r) rf val xxx : ('n xxx , 'n, z ii , 's iii, 'k, 'r) rf val xl : ('n xl , 'n, z ii , 's iii, 'k, 'r) rf val l : ('n l , 'n, z ii , 's iii, 'k, 'r) rf val lx : ('n lx , 'n, z ii , 's iii, 'k, 'r) rf val lxx : ('n lxx , 'n, z ii , 's iii, 'k, 'r) rf val lxxx : ('n lxxx, 'n, z ii , 's iii, 'k, 'r) rf val xc : ('n xc , 'n, z ii , 's iii, 'k, 'r) rf val c : ('n c , 'n, z i , 's ii , 'k, 'r) rf val cc : ('n cc , 'n, z i , 's ii , 'k, 'r) rf val ccc : ('n ccc , 'n, z i , 's ii , 'k, 'r) rf val cd : ('n cd , 'n, z i , 's ii , 'k, 'r) rf val d : ('n d , 'n, z i , 's ii , 'k, 'r) rf val dc : ('n dc , 'n, z i , 's ii , 'k, 'r) rf val dcc : ('n dcc , 'n, z i , 's ii , 'k, 'r) rf val dccc : ('n dccc, 'n, z i , 's ii , 'k, 'r) rf val cm : ('n cm , 'n, z i , 's ii , 'k, 'r) rf val m : ('n m , 'n, z , 's i , 'k, 'r) rf val mm : ('n mm , 'n, z , 's i , 'k, 'r) rf val mmm : ('n mmm , 'n, z , 's i , 'k, 'r) rf end structure Roman :> ROMAN = struct datatype z = Z datatype 'n i = I of 'n type 'n ii = 'n i i type 'n iii = 'n i ii type 'n iv = 'n i iii type 'n v = 'n i iv type 'n vi = 'n i v type 'n vii = 'n i vi type 'n viii = 'n i vii type 'n ix = 'n i viii type 'n x = 'n i ix type 'n xx = 'n x x type 'n xxx = 'n x xx type 'n xl = 'n x xxx type 'n l = 'n x xl type 'n lx = 'n x l type 'n lxx = 'n x lx type 'n lxxx = 'n x lxx type 'n xc = 'n x lxxx type 'n c = 'n x xc type 'n cc = 'n c c type 'n ccc = 'n c cc type 'n cd = 'n c ccc type 'n d = 'n c cd type 'n dc = 'n c d type 'n dcc = 'n c dc type 'n dccc = 'n c dcc type 'n cm = 'n c dccc type 'n m = 'n c cm type 'n mm = 'n m m type 'n mmm = 'n m mm type 'n r = int datatype ('n, 's) r' = R of int type ('n, 'm, 's, 't, 'k, 'r) rf = (('n, 's) r' -> 'k) -> ((('m, 't) r' -> 'k) -> 'r) -> 'r fun toInt n = n local fun unR (R n) = n fun ret a f = f a fun lift f = ret o f fun mkR n k = lift (fn g => g o R o (fn x => x + n) o unR) k in fun <| f = ret unR f fun |> f = f (R 0) fun i k = mkR 1 k fun ii k = mkR 2 k fun iii k = mkR 3 k fun iv k = mkR 4 k fun v k = mkR 5 k fun vi k = mkR 6 k fun vii k = mkR 7 k fun viii k = mkR 8 k fun ix k = mkR 9 k fun x k = mkR 10 k fun xx k = mkR 20 k fun xxx k = mkR 30 k fun xl k = mkR 40 k fun l k = mkR 50 k fun lx k = mkR 60 k fun lxx k = mkR 70 k fun lxxx k = mkR 80 k fun xc k = mkR 90 k fun c k = mkR 100 k fun cc k = mkR 200 k fun ccc k = mkR 300 k fun cd k = mkR 400 k fun d k = mkR 500 k fun dc k = mkR 600 k fun dcc k = mkR 700 k fun dccc k = mkR 800 k fun cm k = mkR 900 k fun m k = mkR 1000 k fun mm k = mkR 2000 k fun mmm k = mkR 3000 k end end

1 0

Continuation Workshop 2011: Call for participation
by oleg＠okmij.org 10 Aug '11

10 Aug '11

ACM SIGPLAN Continuation Workshop 2011 http://logic.cs.tsukuba.ac.jp/cw2011/ co-located with ICFP 2011, Tokyo, Japan Saturday, September 24, 2011 Call for Participation Early Registration deadline is August 15! Continuations have been discovered many times, which highlights their many applications in programming language semantics and program analysis, linguistics, logic, parallel processing, compilation and web programming. Recently, there has been a surge of interest specifically in delimited continuations: new implementations (in Scala, Ruby, OCaml, Haskell), new applications (to probabilistic programming, event-driven distributed processing), substructural and constructive logics, natural language semantics. The goal of the Continuation Workshop is to make continuations more accessible and useful -- to practitioners and to researchers in various areas of computer science and outside computer science. We wish to promote communication among the implementors and users in many fields. We would like to publicize the applications of continuations in academic (logic, linguistics) and practical fields and various programming languages (OCaml, Haskell, Scala, Ruby, Scheme, etc.). Invited talks ------------- Mats Rooth, Cornell University http://conf.ling.cornell.edu/mr249/ >From Logic to Effects and Back Noam Zeilberger, Universite' Paris 7 http://www.pps.jussieu.fr/~noam/ Tutorials --------- In the evening before the workshop, there will be a tutorial session ``Introduction to Programming with Shift and Reset'' Tutorial date and time: Friday, September 23, 2011, 19:00-21:00 Tutorial place: IIJ (next to NII, the place of the ICFP conference) Tutorial speakers: Kenichi Asai and Oleg Kiselyov Presentations ------------- Non-Deterministic Search Library Kenichi ASAI, Chihiro KANEKO `Focus movement' by delimited continuations Daisuke BEKKI Swarm: transparent scalability through portable continuations James DOUGLAS Correctness of Functions with Shift and Reset Noriko HIROTA, Kenichi ASAI Yield, the control operator: applications and a conjecture Roshan P. JAMES, Amr SABRY Demonstration of Continuation based C on GCC Shinji KONO Modular rollback through free monads Conor McBRIDE, Olin SHIVERS, Aaron TURON Using delimited continuations for distributed computing with the CIEL engine Derek G. MURRAY, Malte SCHWARZKOPF, Christopher SMOWTON, Steven SMITH, Anil MADHAVAPEDDY, Steven HAND The limit of the CPS hierarchy Josef SVENNINGSSON Visualizing continuations Naoki TAKASHIMA, Yukiyoshi KAMEYAMA

1 0

Error in the asynchronous exception operational semantics
by Edward Z. Yang 10 Aug '11

10 Aug '11

Hello all, I was recently reading "Asynchronous Exceptions as an Effect" by Harrison, Allwein, Gill and Procter, and noticed at the end that they found an error in the operational semantics described in "Asynchronous Exceptions in Haskell" by the Simons and Andrew Moran. Does anyone know what this error was, and whether or not it was corrected in the December 12, 2006 version of the paper floating around on the net? Thanks, Edward

2 1

Re: [Haskell-cafe] Problems building lambdabot on osx
by John Lato 10 Aug '11

10 Aug '11

> From: Brandon Allbery <allbery.b(a)gmail.com> > > On Mon, Aug 8, 2011 at 21:38, Adam Turoff <adam.turoff(a)gmail.com> wrote: > >> First, there's the issue with linking against libiconv, which is solved >> this >> way: >> >> cabal install --extra-lib-dirs=/usr/lib >> >> That leaves a whole mess of link errors against libHSreadline: >> > > Yes, because now it's finding the system readline, which isn't actually > readline (Apple ships a "readline" which is actually BSD "editline", so you > get missing symbols for things editline doesn't support such as completion). > I think you'll need to temporarily deactivate MacPorts' iconv instead of > using --extra-lib-dirs. > > This can't really be fixed by either GHC or MacPorts; there doesn't seem to > be a good solution as yet, although the MacPorts folks may end up > implementing a hacky solution because Apple has introduced *another* > MacPorts-breaking library conflict in Lion (libnotify). Yep, this is Apple's problem and everyone else just has to put up with it. If you want to mix macports and a non-macports ghc, I think the best solution is to self-compile ghc against the macports libiconv. This is easy, just configure ghc with ./configure --with-iconv-includes=/opt/local/include --with-iconv-libraries=/opt/local/lib I haven't had a problem since I started building ghc this way (10.5 and 10.6). John L.

2 1

Analyzing slow performance of a Haskell program
by Chris Yuen 10 Aug '11

10 Aug '11

Hello Cafe, I was trying to solve ITA Software's "Word Nubmers" puzzle ( http://www.itasoftware.com/careers/puzzle_archive.html) using a brute force approach. Here's a my version of a quick recap of the problem: > A wordNumber is defined as > > wordNumber 1 = "one" > wordNumber 2 = "onetwo" > wordNumber 3 = "onethree" > wordNumber 15 = "onetwothreefourfivesixseveneightnineteneleventwelvethirteenfourteenfifteen" > ... > > Problem: Find the 51-billion-th letter of (wordNumber Infinity); assume that letter is found at 'wordNumber x', also find 'sum [1..x]' >From an imperative perspective, a naive algorithm would be to have 2 counters, keep counting the length of each wordNumber and "break" to return the result. The imperative brute-force approach is implemented in C# here: http://ideone.com/JjCb3. It takes about 1.5 minutes to find the answer on my computer. Then I implemented a brute-force Haskell version: http://ideone.com/ngfFq. It cannot finish the calculation in 5 minutes on my machine. (Irony: it's has more lines than the C# version) Here is the `-p` profile of the Haskell program: http://hpaste.org/49934 The Question: Are there obvious mistakes I am making? (Note: I am fully aware that brute-forcing it is not the correct solution to this problem. I am mainly interested in making the Haskell version perform comparatively to the C# version. Right now it is at least 5x slower so obviously I am missing something obvious) (Note 2: It does not seem to be space leaking. The program runs with constant memory (about 2MB) on my computer) (Note 3: I am compiling with `ghc -O2 WordNumber.hs) Chris

7 12

Snap Riak Extension v0.1
by Edward Tate 09 Aug '11

09 Aug '11

Hi, I released this library a while ago but didn't tell anyone, thought I would let people know. Would be cool to get feedback, suggestions etc. https://github.com/et4te/snap-extension-riak/ PS: There are no recent commits since I'm going to be overhauling the architecture once Snap 6 comes out with 'Snaplets'.

1 0

Problems building lambdabot on osx
by Adam Turoff 09 Aug '11

09 Aug '11

I've tried off and on the last couple of days to build Lambdabot on Mac OS X (before and after the upgrade from 10.6 to 10.7) and I keep running into linker errors with the 64-bit Haskell Platform (ghc 7.0.3). First, there's the issue with linking against libiconv, which is solved this way: cabal install --extra-lib-dirs=/usr/lib That leaves a whole mess of link errors against libHSreadline: Linking dist/build/lambdabot/lambdabot ... ld: warning: could not create compact unwind for _ffi_call_unix64: does not use RBP or RSP based frame Undefined symbols for architecture x86_64: "_rl_insert_completions", referenced from: _readlinezm1zi0zi1zi0_SystemziConsoleziReadline_zdwa5_info in libHSreadline-1.0.1.0.a(Readline.o) "_rl_possible_completions", referenced from: _readlinezm1zi0zi1zi0_SystemziConsoleziReadline_zdwa7_info in libHSreadlin (full error report at http://hpaste.org/50036 ) I did manage to install readline through macports: $ port installed readline The following ports are currently installed: readline @6.2.000_0 (active) $ file /opt/local/lib/libreadline.dylib /opt/local/lib/libreadline.dylib: Mach-O 64-bit dynamically linked shared library x86_64 and I did manage to get readline installed properly by specifying the include/lib dirs from macports: cabal install readline --configure-option=--with-readline-libraries=/opt/local/lib --configure-option=--with-readline-includes=/opt/local/include and readline does work in ghci: $ ghci GHCi, version 7.0.3: http://www.haskell.org/ghc/ :? for help Prelude> :m + System.Console.Readline Prelude System.Console.Readline> readline "testing> " testing> exit exit Just "exit" Prelude System.Console.Readline> The only issue, which has me stumped, is that lambdabot can't seem to find the readline dependency. Adding the --with-readline options when trying to build lambdabot has no effect. Neither does adding --extra-lib-dirs=/opt/local/lib to cabal install. Anyone have a clue where to start to work around this? Would switching to ghc HEAD help here? Thanks, -- Adam

5 4

Second CFP: PADL'12 - Practical Aspects of Declarative Languages 2012
by Claudio Russo 09 Aug '11

09 Aug '11

[Apologies if you receive multiple copies.] Call for Papers =============== 14th International Symposium on Practical Aspects of Declarative Languages (PADL 2012) http://research.microsoft.com/~crusso/padl12 Philadelphia, Pennsylvania, USA, January 23-24, 2012 Co-located with ACM POPL'12 Abstract/Paper submission deadline: September 10th/17th, 2011 Conference Description ====================== Declarative languages build on sound theoretical bases to provide attractive frameworks for application development. These languages have been successfully applied to many different real-world situations, ranging from data base management to active networks to software engineering to decision support systems. New developments in theory and implementation have opened up new application areas. At the same time, applications of declarative languages to novel problems raise numerous interesting research issues. Well-known questions include designing for scalability, language extensions for application deployment, and programming environments. Thus, applications drive the progress in the theory and implementation of declarative systems, and benefit from this progress as well. PADL is a forum for researchers and practitioners to present original work emphasizing novel applications and implementation techniques for all forms of declarative concepts, including, functional, logic, constraints, etc. Topics of interest include, but are not limited to: * Innovative applications of declarative languages * Declarative domain-specific languages and applications * Practical applications of theoretical results * New language developments and their impact on applications * Declarative languages and Software Engineering * Evaluation of implementation techniques on practical applications * Practical experiences and industrial applications * Novel uses of declarative languages in the classroom * Practical extensions such as constraint-based, probabilistic, and reactive languages. PADL'12 welcomes new ideas and approaches pertaining to applications and implementation of declarative languages. In this occasion PADL is co-located, as traditionally, with ACM POPL, which will be held immediately following PADL, January 25-27. The symposium will be held in Philadelphia, Pennsylvania, USA. Important Dates and Submission Guidelines ========================================= Abstract Submission: September 10, 2011 Paper Submission: September 17, 2011 Notification: October 22, 2011 Camera-ready: November 5, 2011 Symposium: January 23-24, 2012 Authors should submit an electronic copy of the full paper in PDF using the Springer LNCS format. The submission will be done through EasyChair conference system. If electronic submission is impossible, please contact the program chairs for information on how to submit hard copies. All submissions must be original work written in English. Submissions must be unpublished and not submitted for publication elsewhere. Work that already appeared in unpublished or informally published workshops proceedings may be submitted. PADL'12 will accept both technical and application papers: * Technical papers must describe original, previously unpublished research results. Technical papers must not exceed 15 pages in Springer LNCS format. * Application papers are a mechanism to present important practical applications of declarative languages that occur in industry or in areas of research other than Computer Science. Application papers will be published in the Springer-Verlag conference proceedings, and will be presented in a separate session. Application papers are expected to describe complex and/or real-world applications that rely on an innovative use of declarative languages. Application descriptions, engineering solutions and real-world experiences (both positive and negative) are solicited. The limit for application papers is 6 pages in Springer LNCS format. Program Committee ================= Marcello Balduccini, Intelligent Systems Department, Kodak Research Labs Edwin Brady, University of St Andrews, Scotland Henning Christiansen, Roskilde University, Denmark Agostino Dovier, University of Udine, Italy Matthew Flatt, University of Utah, USA Gopal Gupta, University of Texas at Dallas, USA John Hughes, Chalmers University of Technology, Sweden; Quviq AB Gabriele Keller, University of New South Wales, Australia Lunjin Lu, Oakland University, USA Marc Pouzet, École normale supérieure, France Ricardo Rocha, University of Porto, Portugal Andreas Rossberg, Google Germany GmbH, Germany Claudio Russo, Microsoft Research Cambridge, UK (co-chair) Kostis Sagonas, Uppsala Univeristy, Sweden Satnam Singh, Microsoft Research Cambridge, UK Zoltan Somogyi, University of Melbourne, Australia Eijiro Sumii, Tohoku University, Japan Terrance Swift, Universidade Nova de Lisboa, Portugal; Johns Hopkins University, USA Andrew Tolmach, Portland State University, USA Jan Wielemaker, University of Amsterdam, The Netherlands Roland Yap, National University of Singapore, Republic of Singapore Kwangkeun Yi, Seoul National University, Korea Neng-Fa Zhou, Brooklyn College, City University of New York, USA (co-chair) Contacts ======== For additional information about papers and submissions, please contact the Program Chairs: Claudio Russo Microsoft Research Cambridge,UK Email: crusso <AT> microsoft <DOT> com Neng-Fa Zhou Brooklyn College, The City University of New York, USA Email: zhou <AT> sci <DOT> brooklyn <DOT> cuny <DOT> edu With the Cooperation of ======================= The Association for Logic Programming (ALP) ACM SIGPLAN Microsoft Research, Cambridge ===================================

1 0

PhD Position available at Strathclyde
by Conor McBride 09 Aug '11

09 Aug '11

[My colleague, Patricia Johann, advertises the following...] PhD Position in Category Theory and Functional Programming Department of Computer and Information Sciences University of Strathclyde, Scotland Applications are invited for one PhD position within the Mathematically Structured Programming group at the University of Strathclyde. The group comprises Prof. Neil Ghani, Dr. Patricia Johann, Dr. Conor McBride, Dr. Peter Hancock, Dr. Robert Atkey, and six PhD students. The PhD project centres around applications of categorical methods to functional programming languages. The project is under the direction of Patricia Johann. The successful applicant will have either a first-class degree or an MSc in Mathematics or Computing Science or a related subject with a strong Mathematics or Computing Science component. Ideally, they will also have a strong, documented interest in doing research. Strong mathematical background and problem-solving skills are essential; good programming skills are a plus. Prior knowledge of category theory and/ or functional programming is an advantage, but is not required. The PhD position is for 3 years; it starts in January 2012. The position is a fully-funded post for a UK or EU student, and includes both coverage of fees and an EPSRC-level stipend for each of the three years. More information about the department is available at http://www.strath.ac.uk/cis The University of Strathclyde (http://www.strath.ac.uk) is located in the heart of Glasgow, which Lonely Planet Travel Guides hail as "one of Britain's largest, liveliest and most interesting cities" (seehttp://www.lonelyplanet.com/worldguide/scotland/glasgow/) . Southern Scotland provides a particularly stimulating environment for researchers in theoretical computer science, with active groups in this area at Heriot-Watt University, the University of Edinburgh, the University of Glasgow, the University of St. Andrews, and the University of Strathclyde. Requests for further information and other informal enquiries can be sent to: Patricia Johann patricia at cis.strath.ac.uk Those interested in the position are asked to send e-mail to the address given above in the next short while.

1 0

Question Formlets, file upload
by "Dr. Heinrich Hördegen" 09 Aug '11

09 Aug '11

Dear all, I am using the library Text.XHtml.Strict.Formlets to build a validating form. I use the function "file" to get a file upload widget. The encoding is set to multipart. I want to check, if the user entered something or left the widget empty. However, when entering nothing, instead of an empty string, I always get a string like "/tmp/12101" which corresponds to an empty file. It would be nice, if I could check for the empty string to see, weather the user entered something or not into the upload widget. I appreciate any hints to achive this and wish you a good day, Heinrich -- -- hoerdegen(a)funktional.info www.funktional.info --

1 0

Declarative configuration languages?
by Richard O'Keefe 09 Aug '11

09 Aug '11

A colleague just asked me I'm trying to kick off some work into middleware for configuration of large-scale, distributed systems. Have you come across any elegant, declarative configuration languages used for this sort of job? I've found a couple of papers, but I've never _used_ any of the systems. Any recommendations?

2 1

Couldn't match expected type `Integer' against inferred type `Int'
by Paul Reiners 09 Aug '11

09 Aug '11

Why am I getting this error: > Couldn't match expected type `Integer' against inferred type `Int' > In the expression: foldl step 0 xs > In the definition of `asInt_foldAux': > asInt_foldAux xs > = foldl step 0 xs > where > step acc '.' = error "cannot handle decimal numbers" > step acc x = acc * 10 + digitToInt x for this code? > import Data.Char (digitToInt) > > asInt_fold :: String -> Integer > asInt_fold ('-':xs) = -(asInt_foldAux xs) > asInt_fold xs = asInt_foldAux xs > > asInt_foldAux :: String -> Integer > asInt_foldAux xs = foldl step 0 xs > where step acc '.' = error "cannot handle decimal numbers" > step acc x = acc * 10 + digitToInt x Note that I'm using Int, rather than Integer, to avoid silent overflow errors.

2 3