June 2008 - Haskell-Cafe

Re: [Haskell] ANN: random-access-list-0.1
by Isaac Dupree 13 Jun '08

13 Jun '08

Stephan Friedrichs wrote: > Hello, > > I've implemented Chris Okasaki's random-access list[1] which provides > typical list operations (cons, head, tail) in O(1) and yet offers > indexed random-access in O(log n). It's uploaded on hackage[2]. > > It's still an early version which I'll extend, but especially at this > eary stage I'd appreciate your feedback concerning what's still missing > / to be fixed / to be improved. Great to see it, it deserved implementing, IIRC! I don't remember enough about it.. (and don't have Okasaki anywhere handy). Can it be lazy or infinitely long? (Data.Sequence can't, but it's fast on both ends and has fast concatenation.) Anyway, document that. If it can't be lazy/infinite, does it have any advantage over using Data.Sequence?(constant factor of speed?, possible operations?, something I'm forgetting?) Is "RandomAccessList" the best name for something that's not O(1), just O(log n)? Or just that "RandomAccessList" is just much longer than "[]"? don't use those unorthodox infix function names.. `cons` is hardly worse than .:. , `append` or `mappend` than .+. , and .!. than, hmm.. . Export a ++ and ! (!! ?) if you're really dedicated. But I'd prefer an `at` that's the same partial indexing operation, rather than the name .!. (I think this "at" was a new name being put somewhere else? partly because "!" is trying to be gradually used only to refer to strictness?) "extractHead" is an ugly name for a nevertheless standardish-meaning function... what is it usually called? uncons? headTail? (Data.Sequence, which is meant to be left-right symmetric, calls it "viewr"... except your version doesn't have the Maybe, it's partial instead, fails on empty lists) For "index", don't use Monad, use Maybe (I think that's what the recent libraries(a)haskell.org discussion concluded, in the context of switching Data.Map back to Maybe). Also, Data.List has genericLength etc, to support. Isn't "index" (like Data.List.genericIndex) supposed to be a name for a partial operation, not one that returns a Maybe? Shouldn't "size" be named "length" (or exported as both names, since e.g. Data.Map.size, .List.length) (why is it O(1) not O(log n)? Is it possible for these RandomAccessLists to be longer than maxBound::Int?)? for e.g. toList, is the O(n) cost spread over traversing/demanding the items of the generated list, or all up-front, or somewhere in between? Why is zip slow with unbalanced lists? Obviously, it could be implemented O(min(m,n)*(log m + log n)) just indexing each one, which would be faster for really unbalanced-size lists... Obviously, I don't understand the implementation. BTW, looking at the file, data RandomAccessList a = RandomAccessList {-# UNPACK #-} !Int ![(Int, CBTree a)] Marking a list strict like that doesn't have much effect because it only makes the first (:) or [] strict. Did you mean for an element-strict or spine-strict(which would necessarily be non-infinite) list? -Isaac > > Regards, > Stephan > > [1] Chris Okasaki: "Purely Functional Data Structures" > [2] > http://hackage.haskell.org/cgi-bin/hackage-scripts/package/random-access-li… > > >

7 10

Cabal-Install Fails To Compile
by Aditya Siram 13 Jun '08

13 Jun '08

Hi all, I downloaded cabal-install and the cabal-1.4 branch from darcs. The following error occurs when building: > runhaskell Setup.hs build Building cabal-install-0.4.9... [19 of 27] Compiling Hackage.SrcDist ( Hackage/SrcDist.hs, dist/build/cabal/cabal-tmp/Hackage/SrcDist.o ) Hackage/SrcDist.hs:58:59: Couldn't match expected type `Char' against inferred type `Distribution.Simple.PreProcess.PPSuffixHandler' Expected type: FilePath Inferred type: [Distribution.Simple.PreProcess.PPSuffixHandler] In the fifth argument of `prepareSnapshotTree', namely `knownSuffixHandlers' In the second argument of `(>>=)', namely `prepareSnapshotTree verbosity pkg mb_lbi tmpDir knownSuffixHandlers' According to ghc-pkg compiling and installing the cabal-1.4 branch added cabal-1.3.12. Is this the problem? -Deech _________________________________________________________________ It’s easy to add contacts from Facebook and other social sites through Windows Live™ Messenger. Learn how. https://www.invite2messenger.net/im/?source=TXT_EML_WLH_LearnHow

3 3

Re: [Haskell] ANN: random-access-list-0.1
by Isaac Dupree 13 Jun '08

13 Jun '08

Stephan Friedrichs wrote: > Isaac Dupree wrote: >> [...] >> >> Great to see it, it deserved implementing, IIRC! I don't remember >> enough about it.. (and don't have Okasaki anywhere handy). Can it be >> lazy or infinitely long? > > No, it has to be finite as it's actually a list of complete binary trees > whose size depend on the skew binary representation of the list's size. > I'll document this. okay then >> [...] >> >> Is "RandomAccessList" the best name for something that's not O(1), >> just O(log n)? Or just that "RandomAccessList" is just much longer >> than "[]"? > > Well Chris Okasaki called them "Skew Binary Random-Access Lists", which > is even longer :) :) hmm.. IndexableList? (just a thought, not sure whether I like it any better) >> >> don't use those unorthodox infix function names.. `cons` is hardly >> worse than .:. , `append` or `mappend` than .+. , and .!. than, hmm.. >> . Export a ++ and ! (!! ?) if you're really dedicated. But I'd prefer >> an `at` that's the same partial indexing operation, rather than the >> name .!. (I think this "at" was a new name being put somewhere else? >> partly because "!" is trying to be gradually used only to refer to >> strictness?) > > Good point! > >> >> "extractHead" is an ugly name for a nevertheless standardish-meaning >> function... what is it usually called? uncons? headTail? >> (Data.Sequence, which is meant to be left-right symmetric, calls it >> "viewr"... except your version doesn't have the Maybe, it's partial >> instead, fails on empty lists) > > Yes, I wasn't happy with that one either. The view-concept of > Data.Sequence is a good idea. yeah, it's a good idea, although I'm not sure how much I like the particular syntax of how it's done in Data.Sequence (the view-types' constructor names, mostly) >> >> For "index", don't use Monad, use Maybe (I think that's what the >> recent libraries(a)haskell.org discussion concluded, in the context of >> switching Data.Map back to Maybe). > > I was just copying the idea from Data.Map and it's usually a good thing > to have functions as general as possible, or why is it not? To summarize: Monad isn't the proper abstraction for failable/Maybe. Maybe is an algebraic data type that *exactly* represents the spirit of what you're trying to do: e.g. Conor McBride said: "Maybe is the most general abstraction. Requiring (>>=), or even (<*>) seems excessive. What we need is "any f with zero and return", so why not pick the canonical, initial, inductively defined such thing?" In this case the typeclass adds no generality to the function's behaviour (Maybe can be trivially converted to any other type, with a combinator even). And the confusion that results, when the function is almost always used at type Maybe anyway. If you want to read the whole discussion... if you haven't been subscribed to libraries(a)haskell.org , it's archived: http://thread.gmane.org/gmane.comp.lang.haskell.libraries/9082 >> Also, Data.List has genericLength etc, to > > At the moment, I'm using the Int type for size and indexing only for one > reason: I haven't found a proper way to generalize it. I'd really like > to use the Ix class, but it doesn't provide enough functionality, it > only works on fixed-size intervals (i. e. for arrays, which don't change > their size, but a list does). Maybe someone has an idea of how to > realize lists with a variable starting index and size? fair enough. If your implementation only supports sizes up to that of Int (which is reasonable for a strict finite type... whereas something like ([1..2^34] `genericIndex` (2^33)) can probably complete in a small amount of memory and only a moderate amount of time on a modern machine, even a 32-bit one, due to laziness and garbage collection) >> support. Isn't "index" (like Data.List.genericIndex) supposed to be a >> name for a partial operation, not one that returns a Maybe? Shouldn't >> "size" be named "length" (or exported as both names, since e.g. >> Data.Map.size, .List.length) (why is it O(1) not O(log n)? Is it >> possible for these RandomAccessLists to be longer than maxBound::Int?)? > > The size function is in O(1) because I cache it, otherwise it would be > > size (RandomAccessList xs) = sum (map fst xs) > > which is O(log n). I consider the caching useful, as most applications > will check 0 <= i < size quite often. sounds good > >> >> for e.g. toList, is the O(n) cost spread over traversing/demanding the >> items of the generated list, or all up-front, or somewhere in between? >> >> Why is zip slow with unbalanced lists? Obviously, it could be >> implemented O(min(m,n)*(log m + log n)) just indexing each one, which >> would be faster for really unbalanced-size lists... Obviously, I don't > > If two lists have exactly the same size, all the complete binary trees > holding the data have the same size as well. This can be zipped directly > and is a bit (~5% in my tests) faster. okay, that sounds like a fair optimization, since zipping same-size lists is a nice thing to do anyway. But the asymptotic speed ideally should still be O(min(m,n)), if possible? >> understand the implementation. BTW, looking at the file, >> data RandomAccessList a >> = RandomAccessList {-# UNPACK #-} !Int ![(Int, CBTree a)] >> Marking a list strict like that doesn't have much effect because it >> only makes the first (:) or [] strict. Did you mean for an >> element-strict or spine-strict(which would necessarily be >> non-infinite) list? > > Oh, you're right, I just meant to mark the Int strict. It obviously was > too late yesterday! > > Thanks for this feedback! > //Stephan >

4 5

Announce: Fortress talk in New York City
by Jeff Polakow 13 Jun '08

13 Jun '08

Hello, There will be a talk on Fortress ( a new OO/Functional language from Sun) on Wednesday June 25 at 6:30pm in Manhattan. Abstract: The Java Programming Language revolutionized programming with two simple concepts: "Write once run anywhere", and Garbage Collection. This led to a big step up in programmer productivity. Project Fortress does it again. This time we give you multiprocessor performance without having to code threads, locks, or load balancing. Can you say "Implicit Parallelism" and "Transactional Memory"? We also give you a growable language (small fixed core), strong static typing (more errors caught at compile time), and mathematical notation. This talk will focus on the strengths of Fortress as a programming language, as well as a deep dive into implementation issues. More information is available at http://lisp.meetup.com/59 -Jeff --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

5 4

Difficulty installing hscurses
by Dominic Espinosa 13 Jun '08

13 Jun '08

Hello, I'm trying to install hscurses on debian-testing. I have ghc6 installed, which I've written some toy programs with, but I haven't tried to install any Hackage packages until now. hscurses depends on old-time and old-locale (those names make me raise my eyebrows a bit). In turn, old-time seems to depend on old-locale. So, I tried installing old-locale first. In installed fine. Now I'm trying to install old-time: $ runhaskell Setup.hs configure Warning: defaultUserHooks in Setup script is deprecated. Configuring old-time-1.0.0.0... Warning: The 'build-type' is 'Configure' but there is no 'configure' script. (given these warnings, I don't really expect the next command to succeed, but what the hell:) $ runhaskell Setup.hs build Preprocessing library old-time-1.0.0.0... Building old-time-1.0.0.0... System/Time.hsc:118:7: Could not find module `System.Locale': it was found in multiple packages: old-locale-1.0.0.0 base No idea what to do here. Is old-time conflicting with whatever "time" package superseded it, or what? I'm new to Haskell, and understanding the guts of its packaging system is a bit beyond me right now. Sorry if this is a FAQ or something, but I tried some Google searches and found nothing useful. Any help or tips appreciated.

2 1

-fvia-C error
by Anatoly Yakovenko 12 Jun '08

12 Jun '08

any idea what could be causing this error when i add the -fvia-C option /tmp/ghc32300_0/ghc32300_0.hc:6:23: error: SFMT_wrap.h: No such file or directory make: *** [release] Error 1 I am also passing these options: -O2 -fexcess-precision -funbox-strict-fields -fglasgow-exts -fbang-patterns -lcblas Thanks, Anatoly

4 5

Problems with Validate from HaXML
by Samuel Silva 12 Jun '08

12 Jun '08

Hello I'm working with large DTDs from http://www.recordare.com/dtds/, particulary partwise.dtd and timewise.dtd. I check these DTDs with some tools, like Altova XML Spy and Microsoft Visual Studio, and DTDs are valid. However Validate tool from HaXML doesn't validate same DTDs. Result from Validate is: $ Validate partwise.dtd Validate: In a sequence: in content spec of ELEMENT decl: note When looking for a non-empty sequence with separators: Expected % but found | in file note.mod at line 51 col 45 used by file partwise.dtd at line 120 col 1 when looking for a content particle when looking for a content particle Problematic definition is in "note.mod" file, presented below: <!ELEMENT note (((grace, %full-note;, (tie, tie?)?) | (cue, %full-note;, duration) | (%full-note;, duration, (tie, tie?)?)), instrument?, %editorial-voice;, type?, dot*, accidental?, time-modification?, stem?, notehead?, staff?, beam*, notations*, lyric*)> I'm trying using DtdToHaskell tool from HaXML to build parser from MusicXML to Haskell types. There are other ways to build XML parser using HaXML? I'm already using HaXML, with HaXML combinators, to write MusicXML. Thanks. -- Don't hug that, Hugs ME! Samuel Silva

2 1

Simple list processing
by Andrew Coppin 12 Jun '08

12 Jun '08

OK, so this is a fairly basic question about list processing. Several times now, I have found myself wanting to process a list to produce a new list. However, the way later elements are processed depends on what the earlier elements are - in other words, this isn't a simple "map". What is the best way to handle this? According to the theory, anything that consumes a list and produces a value is some kind of fold. [Assuming it traverses the list in a sensible order!] So it looks like you could implement this as a fold. But should that be a LEFT-fold or a RIGHT-fold? (I always get confused between the two!) Actually, anything that takes a value and processes it repeatedly to produce a list is technically an unfold. [Again assuming a sensible processing order.] So it looks like this function could also be an UNfold. As in, you take a list as input, and keep unfolding until that list becomes empty. So it looks like this can be implemented as a fold or an unfold. But neither way looks especially easy. Both of these patterns seem to be more general than necessary; I only want to take 1 element of input and produce 1 element of output, but keeping track of a running state. I guess I could use some sort of state monad and make the whole thing monadic - but that again is overkill for what I'm trying to do. Any hints here?

6 5

appending an element to a list
by Adrian Neumann 11 Jun '08

11 Jun '08

Hello, I was wondering how expensive appending something to a list really is. Say I write I'd say "longList ++ [5]" stays unevaluated until I consumed the whole list and then appending should go in O(1). Similarly when concatenating two lists. Is that true, or am I missing something? Adrian

10 15

ANN: ieee-0.2
by Patrick Perry 11 Jun '08

11 Jun '08

ieee is a library that provides approximate comparison of floating point numbers based, NaN-aware minimum and maximum, and a type class for approximate comparisons. This version fixes a bug in the comparison implementation for Maybe. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ieee

1 0