- Haskell-Cafe - Haskell.org

Approaches to dependent types (DT)
by pat browne 11 Jan '10

11 Jan '10

Hi, I am trying to understand the concept of dependent types as described in Haskell literature (Hallgren 2001),(Hinze,Jeuring et al. 2006). I am particularly interested in understanding two flavours of dependency mentioned by Hinze et al: 1) Types depending on values called dependent types 2) Types depending on types called parametric and type-indexed types I think that ascending levels of abstraction are important here: values - types - classes (Hallgren 2001). Here is a Haskell example of the use of DT: class Named object name | object -> name where name :: object -> name instance (Eq name, Named object name) => Eq object where object1 == object2 = (name object1) == (name object2) I think that the intended semantics are: 1) Objects have names and can be compared for equality using these names. 2) Two objects are considered equal (identical) if they have the same name. 3) The type of a name depends on the type of the object, which gets expressed as a type dependency (object -> name). I am not sure about the last semantic it might be interpreted as "the named object depends on..". This may indicate a flaw in my understanding of DT. I am aware that dependent types can be used to express constraints on the size of lists and other collections. My understanding of Haskell's functional dependency is that object -> name indicates that fixing the type object should fix the type name (equivalently we could say that type name depends on type object). The class definition seems to show a *type-to-type* dependency (object to name), while the instance definition shows how a name value is used to define equality for objects which could be interpreted as a *value-to-type* dependency (name to object) in the opposite direction to that of the class. My questions are: Question 1: Is my understanding correct? Question 2: What flavour of DT is this does this example exhibit? Best regards, Pat Hallgren, T. (2001). Fun with Functional Dependencies. In the Proceedings of the Joint CS/CE Winter Meeting, Varberg, Sweden, January 2001. Hinze, R., J. Jeuring, et al. (2006). Comparing Approaches to Generic Programming in Haskell. Datatype-generic programming: international spring school, SSDGP 2006.

6 7

mtl and transformers
by Günther Schmidt 11 Jan '10

11 Jan '10

Hi, when I cabal-installed the iteratee package, the transformers package was also installed as a dependency. Now when I run applications that import Control.Monad.Transformers I get this: Could not find module `Control.Monad.Trans': it was found in multiple packages: transformers-0.1.4.0 mtl-1.1.0.2 What's the work around for situations like this? Günther

6 8

Haskell Weekly News: Issue 145 - January 10, 2010
by jfredett＠gmail.com 10 Jan '10

10 Jan '10

--------------------------------------------------------------------------- Haskell Weekly News http://sequence.complete.org/hwn/20100110 Issue 145 - January 10, 2010 --------------------------------------------------------------------------- Welcome to issue 145 of HWN, a newsletter covering developments in the [1]Haskell community. Welcome back Haskellers to the HWN! After a short hiatus we return with a megaedition covering the last three weeks of Haskell news and discussion. Needless to say, lots of new package and event announcements, as well as some really great discussions (the discussion about 'lawless' uninstances of Functors was particularly interesting) over the holiday break. Hopefully everyone had a safe and happy holiday season, and is back now steadily working off the winter-weight (in accordance with resolutions or no) by tapping steadily at the keyboard, producing wonderful new packages for me to place in this, your Haskell Weekly News! Announcements Last CfP for TGC 2010: EXTENDED deadline Jan. 20 2010. Emilio Tuosto [2]announced an extension to the TGC'10 call for papers. SourceGraph-0.6.0.0 and Graphalyze-0.9.0.0. Ivan Lazar Miljenovic [3]announced new releases of the SourceGraph and Graphalyze packages. Streaming Component Combinators 0.4. Mario Blazevic [4]announced version 0.4 of Streaming Component Combinators (SCC). safer-file-handles-0.1. Bas van Dijk [5]announced a new member of the 'monadic regions' family -- safer-file-handles. This package provides safety features on top of System.IO for handling file handles and operations. HOR 2010 1st CALL FOR ABSTRACTS. Frederic Blanqui [6]1f4e gmane.comp.lang.haskell.general/17710 announced the first call for abstracts for the Fifth International Workshop on Higher-Order Rewriting. vty-4.2.1.0. Corey O'Connor [7]announced a new version of the vty package. stm-io-hooks-0.6.0. Peter Robinson [8]announced a new version of stm-io-hooks. This version includes major interface changes, including the elimation of the 'onRetry' combinator. hecc-0.2. Marcel Fourne [9]announced the second release of his elliptic curve cryptography package, hecc. This release includes a license change to the BSD3 license, speed improvements, and new algorithms for point multiplication, as well as other changes. ghc-6.12.1 binary package for OpenSolaris. Michael Lee [10]announced a binary package availability of ghc-6.12 for OpenSolaris. Final Call for Participation: TLDI'10. Andrew Kennedy [11]announced the final call for participation in TLDI'10, the Workshop on Types in Language Design and Implementation. Haskell Web News: Looking back on 2009. Don Stewart [12]announced The Haskell Web News, a monthly summary of the hottest news about the Haskell programming language. hakyll-0.4. Jasper Van der Jeugt [13]announced the release of hakyll, a static site generator library. system-uuid-1.2.0. Jason Dusek [14]announced a new release of system-uuid. New versions of ALL the monadic regions packages. Bas van Dijk [15]announced a new version of all of the monadic regions packages, explanation of what this means is best left to the original post, linked previously. tuntap-0.0.1. John Van Enk [16]announced a new package, extracted from his in-progress VPN project. This package provides access to the TUN/TAP device in Linux. CPython / libpython bindings. John Millikin [17]announced a package providing bindings to the C API for CPython/libpython. Discussion Typed Configuration Files. Sebastian Fischer [18]asked about whether there was an analogue to CmdArgs for config files. Review request for my permutations implementation. CK Kashyap [19]asked for a review of his implementation of a function for finding permutations -- in addition to a review he asked for earlier for code involving monads. The result is a nice pair of threads with introductory material about idiomatic, efficient Haskell code. lawless instances of Functor. Paul Brauner [20]asked about 'lawless' instances (Editor's Note: more so -- 'uninstances', since by definition, it cannot be a functor without satisfying the laws, even if it an instance can be written) of the `Functor` class. This is in an effort to better understand how Functors work in Haskell and in the wider theory. Blog noise [21]Haskell news from the [22]blogosphere. Blog posts from people new to the Haskell community are marked with >>>, be sure to welcome them! * Neil Mitchell: [23]Using .ghci files to run projects. * Tom Moertel: [24]A formal language for recipes: brain dump. * Mark Jason Dominus: [25]A monad for probability and provenance. * Alex Mason: [26]A small follow up. * Russell O'Connor: [27]Constructive Classical Completeness. * Galois, Inc: [28]GHC Nominated for Programming Language Award. * Neil Brown: [29]CHP vs CML, Forking and Picky Receivers. * Conal Elliott: [30]Is Haskell a purely functional language?. * Conal Elliott: [31]Can functional programming be liberated from the von Neumann paradigm?. * Real-World Haskell: [32]Real World Haskell in Japaneseâå®æŠã§åŠã¶é¢æ°åèšèªããã°ã©ãã³ã°. * Conal Elliott: [33]Garbage collecting the semantics of FRP. * Alex Mason: [34]Why I love Cereal. * Mark Jason Dominus: [35]A short bibliography of probability monads. * Conal Elliott: [36]Communication, curiosity, and personal style. * Epilogue for Epigram: [37]Bidirectional Basics. * Neil Mitchell: [38]Explaining Haskell IO without Monads. * Conal Elliott: [39]Is program proving viable and useful?. * Conal Elliott: [40]Why program with continuous time?. Quotes of the Week * fasta: Haskell is like an efficient version of Python and is used for the same things. * koeien37: there are the languages that everybody complains about, and the languages that nobody use * Pseudonym: Olegs can be warded off by adding a note claiming that it's impossible to implement in the type system. * elly: I leave for five minutes and godel numbering of endofunctors is invokved as a potential proof that the universe is simulated. Thanks, #haskell :P * kmc: a monad is like an invisible train filled with jello traveling backwards in time * conal: "Obviously" is one of those words that is most useful when it is least true * Jafet: Javascript is pretty much a DSL for making your web browser take up more CPU * copumpkin: limpac: in this channel we're all automata with no feelings, except for the occasional feeling of hate. * dmhouse: I'm not sure it's working correctly but it sure is fast... * Cale: We need a bunch of "Will it monad?" video clips, with "It monads!" at the end of each. * merijn: I run on HST (Hacker Standard Time) which is essentially current time zone -3 * ray: [about an anti-FP blog post] i came up with some contrived example, announced that it's impossible, and therefore FP sucks * hiredman: I used to think "dons" was a title, like people who were recognized as being really good at haskell were called dons About the Haskell Weekly News New editions are posted to [41]the Haskell mailing list as well as to [42]the Haskell Sequence and [43]Planet Haskell. [44]RSS is also available, and headlines appear on [45]haskell.org. To help create new editions of this newsletter, please see the information on [46]how to contribute. Send stories to jfredett . at . gmail . dot . com. The darcs repository is available at darcs get [47]http://patch-tag.com/r/jfredett/HWN2/pullrepo HWN2 . References 1. http://haskell.org/ 2. http://article.gmane.org/gmane.comp.lang.haskell.general/17716 3. http://article.gmane.org/gmane.comp.lang.haskell.general/17714 4. http://article.gmane.org/gmane.comp.lang.haskell.general/17713 5. http://article.gmane.org/gmane.comp.lang.haskell.general/17711 6. http://article.gmane.org/ 7. http://article.gmane.org/gmane.comp.lang.haskell.general/17705 8. http://article.gmane.org/gmane.comp.lang.haskell.general/17704 9. http://article.gmane.org/gmane.comp.lang.haskell.general/17701 10. http://article.gmane.org/gmane.comp.lang.haskell.general/17700 11. http://article.gmane.org/gmane.comp.lang.haskell.general/17699 12. http://article.gmane.org/gmane.comp.lang.haskell.general/17698 13. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68864 14. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68857 15. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68827 16. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68807 17. http://article.gmane.org/gmane.comp.lang.haskell.cafe/68388 18. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/68865 19. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/68811 20. http://thread.gmane.org/gmane.comp.lang.haskell.cafe/68711 21. http://planet.haskell.org/ 22. http://haskell.org/haskellwiki/Blog_articles 23. http://neilmitchell.blogspot.com/2010/01/using-ghci-files-to-run-projects.h… 24. http://blog.moertel.com/articles/2010/01/08/a-formal-language-for-recipes-b… 25. http://blog.plover.com/prog/haskell/probmonad.html 26. http://random.axman6.com/blog/?p=139 27. http://r6.ca/blog/20100107T035902Z.html 28. http://www.galois.com/blog/2010/01/06/ghc-nominated-for-programming-languag… 29. http://chplib.wordpress.com/2010/01/06/chp-vs-cml-forking-and-picky-receive… 30. http://conal.net/blog/posts/is-haskell-a-purely-functional-language/ 31. http://conal.net/blog/posts/can-functional-programming-be-liberated-from-th… 32. http://www.realworldhaskell.org/blog/2010/01/05/real-world-haskell%e2%80%94… 33. http://conal.net/blog/posts/garbage-collecting-the-semantics-of-frp/ 34. http://random.axman6.com/blog/?p=124 35. http://blog.plover.com/prog/haskell/probmonad-refs.html 36. http://conal.net/blog/posts/communication-curiosity-and-personal-style/ 37. http://www.e-pig.org/epilogue/?p=283 38. http://neilmitchell.blogspot.com/2010/01/haskell-io-without-monads.html 39. http://conal.net/blog/posts/is-program-proving-viable-and-useful/ 40. http://conal.net/blog/posts/why-program-with-continuous-time/ 41. http://www.haskell.org/mailman/listinfo/haskell 42. http://sequence.complete.org/ 43. http://planet.haskell.org/ 44. http://sequence.complete.org/node/feed 45. http://haskell.org/ 46. http://haskell.org/haskellwiki/HWN 47. http://patch-tag.com/r/jfredett/HWN2/pullrepo%20HWN2

1 0

ANNOUNCE: SourceGraph-0.6.0.0 and Graphalyze-0.9.0.0
by Ivan Lazar Miljenovic 10 Jan '10

10 Jan '10

I'm pleased to announce the latest releases of SourceGraph [1] and Graphalyze [2]. [1]: http://hackage.haskell.org/package/SourceGraph [2]: http://hackage.haskell.org/package/Graphalyze SourceGraph is a program that performs static code analysis on Haskell projects on the by applying graph theoretic techniques to the project's call graph. Graphalyze is a library for analysing discrete data using graph theory, and as such performs the heavy lifting for SourceGraph. Sample analysis reports generated by SourceGraph are available at http://code.haskell.org/~ivanm/Sample_SourceGraph/SampleReports.html . I will also be demoing SourceGraph at PEPM [3] in Madrid on 19 January. [3]: http://www.program-transformation.org/PEPM10/ Changes since the previous version include: * Now supports "implicitly exported" entities (as requested by Curt Sampson). This includes instantiated class methods from other modules and functions, etc. that start with an underscore (see http://www.haskell.org/ghc/docs/latest/html/users_guide/options-sanity.html for more information). * All inaccessible entities are now reported, not just those that were root nodes in the call graph. * Edges are now colour-coded based upon whether they are part of a clique, cycle or a chain. * Level-based analyses: visualise how deep an entity is from those exported entities. * A re-done TODO that lists in detail what is planned for SourceGraph. * Lots of under-the-hood changes that don't sound as interesting as the above :-( -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

2 4

Hackage down
by Neil Mitchell 10 Jan '10

10 Jan '10

Hi Hackage is down: http://downforeveryoneorjustme.com/hackage.haskell.org Thanks, Neil

1 0

unexpected behavior from filterM doesFileExist =<< getDirectoryContents
by Thomas Hartman 10 Jan '10

10 Jan '10

Can somebody explain this? > getDirectoryContents inD ["..","#sanity.txt#",".","sanity.txt","etc.txt","patchTagDir.txt","jail.txt","notjail.txt","alldata.txt","allobjs.txt","namesNSizes.txt"] > filterM doesFileExist =<< getDirectoryContents inD > ["sanity.txt"]

2 2

HackageDB Question
by Gregory Crosswhite 09 Jan '10

09 Jan '10

How does HackageDB generate the documentation for uploaded packages? Specifically, if I am using my own build system rather than Cabal, then what do I need to do (e.g., what interface do I need to supply) for HackageDB to correctly generate the documentation? I've glanced through the source code posted at http://darcs.haskell.org/hackage-scripts/, but I am having trouble finding the code which generates the documentation. Thanks! Greg

2 1

Space Efficiency When Sorting a List of Many Lists
by Peter Green 09 Jan '10

09 Jan '10

Heinrich, thanks for some great help and food for thought! (More on performance of your solution below) > Thanks for describing the background of this problem in detail! I was > mainly asking because I'm always looking for interesting Haskell > topics > that can be turned into a tutorial of sorts, and this problem makes a > great example. Another interesting problem is starting from a file of single wagers and trying to compress them (i.e. inverse of 'explosion'. I believe this problem is analogous to Set Cover and therefore NP-Complete. Heuristics are the order of the day here. (OT, but might also make an interesting multi-part tutorial question/ topic: A simpler (fairly unrelated problem) is doing exact k-means clustering of a list of n items (i.e. single dimension data) via the k- segmentations of a (sorted by values one is clustering on) list of n items. The number of k-segmentations of an n-list is (n-1) Choose (k-1). One generates all the k-segmentations and each set of k- segments constitutes a candidate clustering solution. One selects the candidate solution which minimises the 'goodness of fit criterion' used in k-means clustering (easily found in the literature). Needless to say, this is only feasible for smallish n and for values of k closer to the LHS and RHS of Pascal's triangle. K-means clustering in more than one dimension is NP-Complete.) > Concerning optimization, the background also reveals some additional > informations, namely > > * The single wager combinations are short lists > * and each list element is small, i.e. `elem` [1..20] > * No duplicate single wagers > * You are free to choose another ordering than lexicographic > >> I need to explode these compressed wagers back to single combinations >> because, I need to (eventually) do set comparisons on collections of >> single combinations. i.e. given File A and File B of compressed >> wagers, >> I need to be able to answer questions like: >> >> (1) How many single combinations are common to File A and File B >> (2) How many single combinations in File A are missing from File B >> .. >> .. >> etc. i.e a few of the common set comparison operations. >> >> And the dumbest, quickest and dirtiest and most idiot-proof way of >> doing >> this as a baseline approach before I start using maps, tries, >> etc... is >> to explode Files A and B into lex sorted single combinations order >> and >> then use diff -y with judicious grepping for '>' and <'' > > Looks good to me, sorted lists are a fine data structure for set > operations. > >> I'm probably going to go with an external sort for starters to keep >> memory usage down. For most use-cases, I can get away with my current >> in-memory sort - just have to beware edge cases. > > Using an out-of-the box external sort library is probably the path of > least resistance, provided the library works as it should. Seems to be some issue with the external-sort package. As it currently exists, it blows up on my [[Int]] data and exhibits more memory usage than vanilla sort! I'm keen to look into fixing this as might be one small way I can give back, but still taking baby steps with Haskell. > However, your problem has a very special structure; you can interleave > explode and sort and turn the algorithm into one that is partially > on-line, which will save you a lot of memory. I've tried to show how > to > do this in my previous post; the resulting code will look something > like > this > > {-# LANGUAGE NoMonomorphismRestriction #-} > import qualified Data.Map > import Control.Arrow (second) > > newtype Map a b = Map { unMap :: [(a,b)] } deriving (Eq, Show) > > instance Functor (Map a) where > fmap f = Map . (map . second) f . unMap > > hylo :: (Map a b -> b) -> (c -> Map a c) -> (c -> b) > hylo f g = f . fmap (hylo f g) . g > > type Row a = [a] > > headsOut :: Map a [Row a] -> [Row a] > headsOut (Map []) = [[]] > headsOut m = [x:row | (x,rows) <- unMap m, row <- rows] > > explode1 :: [Row [a]] -> Map a [Row [a]] > explode1 rows = Map [(x,[row]) | (xs:row) <- rows, x <- xs] > > sort1 :: Ord a => Map a [b] -> Map a [b] > sort1 = Map . Data.Map.toList . Data.Map.fromListWith (++) . unMap > > sortExplode = hylo headsOut (sort1 . explode1) > > example = [[[8,12],[11],[7,13],[10]], [[1,2,3],[1,9],[3,6],[4]]] > test = sortExplode example > > main = interact (unlines . toCSV . sortExplode . fromCSV . lines) > > In other words, sortExplode will "stream" the sorted single wagers > on > demand, unlike the monolithic sort . explode which has to produce > all > single wagers before sorting them. Thank you *very* much for this code! I will try to get my head around it. I understand the broad outline you posted elsewhere, but will take me a while to fully grasp the above as I'm only up to ~p200 in Real World Haskell :). As for performance of your code above on my file of compressed wagers which expands to 3.7M single wagers: (My original version posted here and using vanilla sort) 541 MB total memory in use (5 MB lost due to fragmentation) INIT time 0.00s ( 0.01s elapsed) MUT time 13.98s ( 15.82s elapsed) GC time 8.69s ( 9.64s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 22.67s ( 25.47s elapsed) (Your much improved version) 10 MB total memory in use (1 MB lost due to fragmentation) INIT time 0.00s ( 0.00s elapsed) MUT time 7.61s ( 9.38s elapsed) GC time 3.48s ( 3.58s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 11.08s ( 12.95s elapsed) Very impressive and thanks again! >> However, later on, I'm keen to do everything with set theoretic >> operations and avoid writing large files of single combinations to >> disk. > > Note that there's also the possibility of not expanding the compressed > wagers at all, and perform set operations directly. For instance, it > is > straightforward to intersect two such sets of size n in O(n^2) time. > Since n ~ 5000 , n^2 is about the same ballpark as the exploded single > wager combinations. Not sure I quite understand you here. In my mind, set elements *are* single combinations. It is possible for two quite different-looking files of compressed wagers to contain exactly the same single wager elements. So I'm not sure how to compare without some notion of explosion to single combinations. >> So, I guess the things I'd like to get a feel for are: >> >> (1) Is it realistic to expect to do in-memory set comparisons on sets >> with ~1M elements where each element is a (however-encoded) list of >> (say) 6 integers? I mean realistic in terms of execution time and >> space >> usage, of course. >> >> (2) What would be a good space-efficient encoding for these single >> combinations? I know that there will never be more than 8 integers >> in a >> combination, and none of these values will be < 1 or > 20. So >> perhaps I >> should map them to ByteString library Word8 strings? Presumably >> sorting >> a big list of ByteStrings is going to be faster than sorting a big >> list >> of lists of int? > > The overhead for lists and sets are quite high, it's not uncommon > for 1M > elements to occupy 10M-100M of memory. > > Not to mention that your elements are, in fact, small lists, > introducing > another factor of 10-100. But this can indeed be ameliorated > considerably by representing your elements in a packed format like > ByteStrings or a Word64. I haven't tried packing ByteStrings yet in this context, but *did* get some improvement in external-sort performance when using ByteStrings instead of [[Int]]. Presumably because it somewhat ameliorated the effects of a bug in external-sort where blocks are fully compared rather than just the heads of blocks. I'll be interested to play around with your version more and see if it benefits much from ByteString. It's already very good now in terms of space usage, but perhaps can speed up the I/O (output dominates, of course). I'll be learning from your post for a long time. So thanks again!

2 1

Upgrading Arch Linux Haskell Packages
by Cetin Sert 09 Jan '10

09 Jan '10

Hi, Is there a way to manually upgrade Haskell packages in the aur repository of Arch Linux which were previously contributed automatically by arch-haskell? Or is there a batch upgrade planned for the near future? What is the mailing list for arch Best Regards, Cetin

3 3

Re: [Haskell-cafe] Infix instance headers
by Bas van Dijk 08 Jan '10

08 Jan '10

OK thanks, Bas On Wed, Dec 23, 2009 at 10:50 AM, Simon Peyton-Jones <simonpj(a)microsoft.com> wrote: > Ah I see. It's an oversight. Thank you for pointing that out. > > I'll fix it, but it'll be in the HEAD not 6.12. > > Simon > > | -----Original Message----- > | From: Bas van Dijk [mailto:v.dijk.bas@gmail.com] > | Sent: 22 December 2009 10:52 > | To: Simon Peyton-Jones > | Subject: Re: [Haskell-cafe] Infix instance headers > | > | On Tue, Dec 22, 2009 at 9:53 AM, Simon Peyton-Jones > | <simonpj(a)microsoft.com> wrote: > | > works for me. what version of GHC are you using? > | > | ghc-6.12.1 > | > | Sorry, maybe I wasn't totally clear. The example I posted works but if > | you write the class name in the instance header as infix I get a > | "Malformed instance header" error. > | > | So the following doesn't work: > | > | class (Monad pr, Monad cr) => pr `ParentOf` cr > | > | instance Monad r => r `ParentOf` r > | > | instance ( Monad cr > | , cr `TypeCast2` RegionT resource s pcr > | , pr `ParentOf` pcr > | ) > | => pr `ParentOf` cr > | > | regards, > | > | Bas > >

1 1