December 2009 - Haskell-Cafe

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

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

Re: ANNOUNCE: Clutterhs 0.1
by Gour 08 Jan '10

08 Jan '10

On Sat, 28 Nov 2009 23:18:00 -0500 >>>>>> "Matt" == Matt Arsenault <arsenm2(a)rpi.edu> wrote: Hi Matt, Matt> This is a very early announcement for an initial release of Matt> bindings for Clutter 1.0, now on Matt> Hackage,http://hackage.haskell.org/package/clutterhs Thanks a lot for this project. I'm just thinking about using Haskell on Moblin OS. ;) Matt> It uses c2hs, and depends on gtk2hs from darcs for the Matt> glib/gobject bindings. Overall, its usage should be similar to Matt> gtk2hs. This is very cool. Matt> This is my first Haskell project, and suggestions on the API, bug Matt> reports, etc. are appreciated. What do you think about binding Moblin's nbtk (now it's called mx) ? Otoh, are you aware of: http://github.com/elliottt/clutter & http://github.com/yav/clutter Sincerely, Gour -- Gour | Hlapicina, Croatia | GPG key: F96FF5F6 ----------------------------------------------------------------

4 7

pcre-light install fails with undefined reference to _impure_ptr
by Patrick Caldon 07 Jan '10

07 Jan '10

Not seen this one before. I'm trying to install pcre-light with WinXP 64, Cygwin 1.7.1, Cabal 0.8.0, and ghc 6.12.1. Trying to reinstall "base" with cabal fails as well with an internal error (see below), but I'm assuming that's quasi-intentional/unsupported feature or something. Any ideas? My ultimate goal is to install ghc-core to help track down some performance problems I'm having. Thanks, Patrick. patc@rose ~/rp4/loansim $ cabal install pcre-light --extra-lib-dirs=C:\\cygwin\\lib --extra-include-dirs=C:\\cygwin\\usr\\include --reinstall Resolving dependencies... Configuring pcre-light-0.3.1... Preprocessing library pcre-light-0.3.1... In file included from C:/cygwin/usr/include/pcre.h:90, from Text\Regex\PCRE\Light\Base.hsc:103: C:/cygwin/usr/include/stdlib.h:104: warning: `warning' attribute directive ignored C:/cygwin/usr/include/stdlib.h:109: warning: `warning' attribute directive ignored dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o:Base_hsc_make.c:(.text+0x47): undefined reference to `_impure_ptr' dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o:Base_hsc_make.c:(.text+0x7b): undefined reference to `_impure_ptr' dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o:Base_hsc_make.c:(.text+0x93): undefined reference to `_impure_ptr' dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o:Base_hsc_make.c:(.text+0xc7): undefined reference to `_impure_ptr' dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o:Base_hsc_make.c:(.text+0xf3): undefined reference to `_impure_ptr' dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o:Base_hsc_make.c:(.text+0x127): more undefined references to `_impure_ptr' follow collect2: ld returned 1 exit status linking dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o failed command was: C:\ghc\ghc-6.12.1\mingw\bin\gcc.exe -LC:\cygwin\lib -lpcre -LC:\ghc\ghc-6.12.1\bytestring-0.9.1.5 -LC:\ghc\ghc-6.12.1\base-3.0.3.2 -LC:\ghc\ghc-6.12.1\syb-0.1.0.2 -LC:\ghc\ghc-6.12.1\base-4.2.0.0 -lwsock32 -luser32 -lshell32 -LC:\ghc\ghc-6.12.1\integer-gmp-0.2.0.0 -LC:\ghc\ghc-6.12.1\ghc-prim-0.2.0.0 -LC:\ghc\ghc-6.12.1 -LC:\ghc\ghc-6.12.1/gcc-lib -lm -lwsock32 -LC:\ghc\ghc-6.12.1 dist\build\Text\Regex\PCRE\Light\Base_hsc_make.o -o dist\build\Text\Regex\PCRE\Light\Base_hsc_make.exe cabal.exe: Error: some packages failed to install: pcre-light-0.3.1 failed during the building phase. The exception was: exit: ExitFailure 1 patc@rose ~/rp4/loansim $ cabal --version cabal-install version 0.8.0 using version 1.8.0.2 of the Cabal library patc@rose ~/rp4/loansim $ ghc --version The Glorious Glasgow Haskell Compilation System, version 6.12.1 patc@rose ~/rp4/loansim $ cabal install base --reinstall -p Resolving dependencies... cabal.exe: internal error: impossible patc@rose ~/rp4/loansim $

3 5

Problem with cabal install zlib
by Ozgur Akgun 07 Jan '10

07 Jan '10

Hi, When I run cabal install zlib or cabal upgrade zlib I get the following error: Resolving dependencies... Configuring zlib-0.5.2.0... Preprocessing library zlib-0.5.2.0... Only one output file may be specified cabal: Error: some packages failed to install: zlib-0.5.2.0 failed during the building phase. The exception was: exit: ExitFailure 1 I have zlib-0.5.0.0 installed now. The OS is Snow Leopard. I couldn't find anything related to this error, that's why I'm asking community's opinion. Best, -- Ozgur Akgun

6 15

Value classes
by Mads Lindstrøm 06 Jan '10

06 Jan '10

Hi A function inc5 inc5 :: Float -> Float inc5 x = x + 5 can only be a member of a type class A, if we make all functions from Float -> Float members of type class A. Thus, I assume, that _type_ class is named type class, as membership is decided by types. However, it makes no sense to say that all functions from Float -> Float are invertible or continuous. We would want to specifically say that inc5 is continuous, not all Float -> Float functions. Thus, we could have another abstraction, lets call it _value_ class, where we could say that an individual value (function) could be member. We could say something like: class Invertible (f :: a -> a) where invert :: f -> (a -> a) instance Invertible inc5 where invert _ = \x -> x - 5 In many cases this would be too specific. We would like to say, that applying the first argument to `+` returns an invertible function. Something like: instance Invertible (`+` x) where invert (x +) = \y -> y - x We would properly also like to say, that composing two invertible functions results in another invertible function. I guess there are many more examples. This idea, of value classes, do not feel all that novel. Somebody has properly thought about it before, but gave it a different name. If anybody has links to some papers it would be much appreciated. If anybody has some thoughts of the desirability of value class it would also be much appreciated. /Mads Lindstrøm

3 2

Re: [darcs-users] Iteratees, streams, and mmap
by Jason Dagit 05 Jan '10

05 Jan '10

Hi Heinrich, On Sat, Dec 12, 2009 at 2:42 AM, Heinrich Apfelmus < apfelmus(a)quantentunnel.de> wrote: > Jason Dagit wrote: > > My next experiment will be to find ways to express "take this operation > and > > apply it to a stream without letting the stream leak". One implication is > > that gzReadFilePS should not be used outside of a core set of modules > which > > have been auideted to be resource concious. Another implication is that > we > > need to be really careful about wether or not we allow returning of > > sequences of patches. Possibly, we need several foldl-like functions > that > > open the stream internally. For example, to process the pending maybe we > > should have: > > withPending :: (a -> Patch -> a) -> IO a > > > > And withPending would start the streaming and make sure that the stream > > cannot be visible as a data dependency outside of withPending. > > Just a small comment on a potential flaw in this scheme and the > observation that even the rank-2 type trick from the ST s monad > wouldn't help. > I would say it does help, but it doesn't make it perfect. > > > Namely, withPending does not guarantee that the stream does not leak, > it only makes it more natural/convenient to formulate one's code so that > it doesn't leak. In particular, using (:) as argument pretty much > defeats the whole purpose: > Right. And the iteratee library points out that your iteratees have to be well-behaved (I think there they say "bounded"). I'm well aware of this issue and thanks for pointing it out for others who are reading along. > > withPending (flip (:)) > > Fortunately, the type system can ensure that the patches don't leak. > > withPending :: (forall s. a -> Patch s -> a) -> IO a > > Now, a may not mention s and the type checker will reject flip (:) > as argument. See also > > Oleg Kiselyov, Chung-chieh Shan. > Lightweight Monadic Regions. > http://www.cs.rutgers.edu/~ccshan/capability/region-io.pdf<http://www.cs.rutgers.edu/%7Eccshan/capability/region-io.pdf> > > for an elaboration of this technique. > I'm still on the fence as to whether this style of writing it will add value greater than the complexity it brings. I am certainly considering it :) The darcs source does other things that are also fairly complex. > > > However, the line between leaking and not leaking is very thin here. As > soon as we are given for example a function > > name :: Patch s -> String > > that discards the s , its results can "leak", in the sense that we > could now build a list of names > > foo :: IO [String] > foo = withPending . flip $ (:) . name > > Even worse, any type a that doesn't have O(1) space usage will "leak" > > bar :: IO [()] > bar = withPending . flip $ const (() :) > > In other words, exporting only a foldl' -like interface does not really > prevent us from writing functions that have O(n) instead of O(1) space > usage. But trying to rectify that with the forall s trick is a doomed > idea, too. > I realize it's not perfect, but the problem we have now is that it's too easy to write things that have dismal space usage. If we can't force proper space usage, how can we make it more natural to have bounded space? Or at least a good approximation. It seems that: * foldl'-style helps * rank-n can help * no approach I've seen *forces* the behavior we want * existing code and bug reports demonstrate we need to improve the situation I'm open to suggestions on how to ensure the code has the space behavior I want. Lazy IO* and streams of patches is more compositional and natural to Haskell programmers, but it seems that it's too hard to ensure the code has reasonable space usage. At least where the darcs source is concerned. Therefore, I think the status quo demonstrates that in the darcs source it's worth experimenting with alternatives to lazy io and streams. In other words, the human effort to make the code behave how we want is currently too high and that's the issue I want to address. I don't know how we could make it impossible to have space leaks, although that would be interesting. (*) Note: Lazy IO itself is used in very few places in darcs these days because it has lead to serious bugs. These days me point is more about big streams getting retained. Finding where and why has proven difficult. Thanks, Jason

3 6

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

04 Jan '10

I'm a Haskell neophyte, so may be missing something obvious in the problem outlined below. I'm fairly proficient in Python + have some limited experience in OCaml and F#, so know just enough to be be dangerous, but not nearly enough to really know what I'm doing here. OK, I have text files containing 'compressed lists' Compressed lists look like this: 8+12,11,7+13,10 1+2+3,1+9,3+6,4 . . Sublists are comma-delimited, and sublist elements are separated by '+' character. I parse these to look like so: [[[8,12],[11],[7,13],[10]], [[1,2,3],[1,9],[3,6],[4]], . . ] I need to explode these and produce a lex-sorted list of exploded lists: [[1,1,3,4],[1,1,6,4],[1,9,3,4],[1,9,6,4],[2,1,3,4],[2,1,6,4],[2,9,3,4], [2,9,6,4],[3,1,3,4],[3,1,6,4],[3,9,3,4],[3,9,6,4], [8,11,7,10],[8,11,13,10],[12,11,7,10],[12,11,13,10]] I then output this data as comma-delimited lists: 1,1,3,4 1,1,6,4 . . 12,11,13,10 I can do all this in my (no doubt fairly naive) program shown below. In real life, one of my test data files contains compressed lists which all contain 7 sublists. This data (correctly) explodes to a list containing ~3,700,000 exploded lists. All good as far as correctly transforming input to output goes. However, sorting the data uses a lot of memory: Partial output from ./explode +RTS -sstderr: 540 MB total memory in use (4 MB lost due to fragmentation) If I do not do any sorting on the exploded lists, i.e. modify the main function to be main = interact (unlines . toCSV . explode . fromCSV . lines) I then see this partial output from ./explode +RTS --stderr: 2 MB total memory in use (0 MB lost due to fragmentation) I can guess that there might be be less laziness and more instantiation when sorting is introduced, but my questions are: (1) Am I doing anything terribly stupid/naive here? (2) If so, what can I do to improve space efficiency? TIA! import Data.List (sort) import Data.List.Split (splitOn) -- Cartesian Product over a List of Lists -- cp [[1,2],[3],[4,5,6]] --> [[1,3,4],[1,3,5],[1,3,6],[2,3,4],[2,3,5], [2,3,6]] cp :: [[a]] -> [[a]] cp [] = [[]] cp (xs:xss) = [y:ys | y <- xs, ys <- cp xss] -- fromCSV ["8+12,11,7+13,10", "1+2+3,1+9,3+6,4"] --> -- [[[8,12],[11],[7,13],[10]],[[1,2,3],[1,9],[3,6],[4]]] fromCSV :: [String] -> [[[Int]]] fromCSV = map parseOneLine where parseOneLine = map parseGroup . splitOn "," where parseGroup = map read . splitOn "+" -- explode [[[1,2],[3],[4,5,6]], [[1, 2], [14,15], [16]]] --> [[1,3,4], [1,3,5], -- [1,3,6],[2,3,4],[2,3,5],[2,3,6],[1,14,16],[1,15,16],[2,14,16], [2,15,16]] explode :: [[[a]]] -> [[a]] explode = concatMap cp -- toCSV [[8,11,7,10,12],[8,11,7,10,12],[8,11,7,10,12]] --> -- ["8,11,7,10,12","8,11,7,10,12","8,11,7,10,12"] toCSV :: (Show a) => [[a]] -> [String] toCSV = map $ tail . init . show --toCSV = map (intercalate "," . map show) main = interact (unlines . toCSV . sort . explode . fromCSV . lines)

6 7

Use of the Try typeclass
by Edward Z. Yang 01 Jan '10

01 Jan '10

Hello all, I am currently playing with the new cadre of failure libraries, and I'm trying to figure out how to use the monadic version of Failure while also getting the Try typeclass, which appears to be the standardized mechanism for marshalling values from specific monads into the failure monad. Unfortunately, it only seems to be defined when I import Control.Failure, and this module is fairly incompatible with Control.Monad.Failure, as demonstrated by this GHCI transcript: ezyang@javelin:~/Documents/tmr$ ghci Prelude> :m +Control.Failure Prelude Control.Failure> :m +Control.Monad.Failure Prelude Control.Failure Control.Monad.Failure> :t failure <interactive>:1:0: Ambiguous occurrence `failure' It could refer to either `Control.Failure.failure', imported from Control.Failure or `Control.Monad.Failure.failure', imported from Control.Monad.Failure I'm using MTL, which might be the reason why there's all sorts of unhappiness. :-) Cheers, Edward

3 8

Haskell Hackathon in Boston January 29th-31st?
by Ravi Nanavati 01 Jan '10

01 Jan '10

After all of the fun I had at Hac Phi, I've been thinking for a while that it would be fun to organize a Boston hackathon (to have all of the hackathon fun without the long drive). After some recent chats with my MIT friends, it seems like the weekend just after IAP (January 29th-January 31st) might be a good one. I've created a page to start organizing this hackathon (which I'm calling HacBOS unless someone comes up with a catchier name) here: http://www.haskell.org/haskellwiki/HacBOS If you'd be interested in attending a Boston hackathon, please add yourself to the possible attendees list on that page. If the proposed weekend does NOT work for you, but you're still interested in attending a Boston hackathon please indicate what other weekends during MIT's IAP (January 4th-January 29th) might work for you. I'm looking forward to making HacBOS happen! Thanks, - Ravi Nanavati

2 1