July 2010 - Haskell-Cafe

Re: [Haskell-cafe] music-related problem
by Michael Mossey 05 Jul '10

05 Jul '10

erik flister wrote: > I am dealing with ties because I am converting a MusicXML document > into a more natural form for my purposes. The initial form of the > document will have tied notes (as it comes that way from MusicXML), > and I want to convert that into a form that makes it possible to > ignore ties and see notes as having a single duration. > > > but can't you just say that the first note of a tie has the indicated > start time and a duration which is the sum of the tied notes? i don't > know musicXML, but i'm not seeing why that would be hard... That's what I want to do. I'm asking about a good way to write the algorithm that traverses the notes and reconstructs the document with the correct duration in each note. Actually, I don't want to lose information about the original form of the document, so I have separate fields for the duration of the graphical single note, and the duration of the tied chain. Actually, it is better to speak of the end time than the duration, because what units do you put duration in? Beats? The time signature could be changing measure to measure. MusicXML "position"? The meaning of "one position" changes measure to measure and can be different in different parts. It can get confusing. So I use this concept of "location": data Loc = Loc Int Rational -- measure number and beat within the measure I.e. measure 1, beat 2 measure 7, beat 3 1/2 I use Rational so there is no worry about precision of Floats. Thanks, Mike

2 4

Undecidable Instances [Was: Is my code too complicated?]
by oleg＠okmij.org 05 Jul '10

05 Jul '10

Ertugrul Soeylemez wrote: > Essentially UndecidableInstances turns the type system into a > Turing-complete programming language. One direct consequence is that > type checking may not terminate Actually, the type checking (specifically, instance resolution) always terminates, due to the recursion depth limit. When the type checker hit the limit, one can't generally say either it is because the program is ill-typed or the program is well-typed but needs a bigger limit. In practice, it is usually quite easy to tell the difference. The trace emitted by GHC helps. I'd like to emphasize however that UndecidableInstances is only a sufficient condition of a decidable type checking -- but by no means necessary. There are many good, type-decidable programs that are not accepted without UndecidableInstances. One of the simplest examples is shown in http://okmij.org/ftp/Haskell/types.html#undecidable-inst-defense The situation with UndecidableInstances seems similar to the primitive recursion criterion: all primitive recursion functions surely terminate; non-primitive recursion functions generally don't. That is not the reason to disregard the latter: There are many classes of non-primitive recursive functions that are total. To see that, one has to use more complex criteria. The added complexity is not worthwhile as far as GHC is concerned (The tradeoff is different in Agda, where the added complexity of more powerful termination checkers may be worthwhile).

1 0

Mining Twitter data in Haskell and Clojure
by braver 05 Jul '10

05 Jul '10

I'm computing a communication graph from Twitter data and then scan it daily to allocate social capital to nodes behaving in a good karmic manner. The graph is culled from 100 million tweets and has about 3 million nodes. First I wrote the simulation of the 35 days of data in Clojure and then translated it into Haskell with great help from the glorious #haskell folks. I had to add -A5G -K5G to make it work. It does 10 days OK hovering at 57 GB of RAM; I include profiling of that in sc10days.prof. At first the Haskell executable goes faster than Clojure, not by an order of magnitude, but by 2-3 times per day simulated. (Clojure also fits well in its 32 GB JVM with compressed references.) However, Haskell gets stuck after a while, and for good. Clearly I'm not doing Haskell optimally here, and would appreciate optimization advice. Here's the code: http://github.com/alexy/husky The data and problem description is in http://github.com/alexy/husky/blob/master/Haskell-vs-Clojure-Twitter.md -- also referred from the main README.md. The main is in sc.hs, and the algorithm is in SocRun.hs. The original Clojure is in socrun.clj. This is a continuation of active Twitter research and the results will be published, and I'd really like to make Haskell work at this scale and beyond! The seq's sprinkled already did no good. I ran under ghc 6.10 with -O2 with or without - fvia-C, with no difference in stallling, and am working to bring 6.12 to bear now. Cheers, Alexy

15 41

Re: [Haskell-cafe] music-related problem
by Michael Mossey 04 Jul '10

04 Jul '10

Henning Thielemann wrote: > > On Sun, 4 Jul 2010, Michael Mossey wrote: > >> Henning Thielemann wrote: >>> >>> On Sun, 4 Jul 2010, Michael Mossey wrote: >>> >>>> I can solve a simpler problem which is >>>> >>>> computeSoundedEnd :: Item -> [Item] -> Loc >>>> computeSoundedEnd firstNote notes = compSndEnd (pitch firstNote) notes >> >>> You will certainly not be able to make use of foldl or foldr, but you >>> may use a manual recursion instead. Just like >>> >>> computeAllEnds :: [Item] -> [Item] >> >> What makes it harder than this is that the original document is not a >> single list of Item's--they are broken into measures. > > That is, you want a function of type > > computeAllEnds :: [Measure] -> [Measure] > > ? Right, although it occurs to me that it might be superior to represent the document as [Item] and give Item a measure-number attribute. There are also other measure attributes, so in that case the doc would look like: data Doc = Doc [MeasureInfo] [Item]

1 0

GHC AT inference bug?
by Kevin Quick 04 Jul '10

04 Jul '10

I started with the following: {-# LANGUAGE TypeFamilies #-} class DoC a where type A2 a op :: a -> A2 a data Con x = InCon (x (Con x)) type FCon x = x (Con x) foldDoC :: Functor f => (f a -> a) -> Con f -> a foldDoC f (InCon t) = f (fmap (foldDoC f) t) doCon :: (DoC (FCon x)) => Con x -> A2 (FCon x) doCon (InCon x) = op x fCon :: (Functor x, DoC (FCon x)) => Con x -> A2 (FCon x) fCon = foldDoC op I then changed the rank of op, but forgot to update the foldDoC accordingly---see below. Attempting to compile this causes GHC to run forever using 100% cpu. The corrected definition of foldDoC works fine. Should the GHC (6.12.1) behavior in the face of my foolishness be reported as a bug or is this a legitimate infinite recursion of type deduction? {-# LANGUAGE TypeFamilies #-} class DoC a where type A2 a type A3 a op :: a -> A2 a -> A3 a data Con x = InCon (x (Con x)) type FCon x = x (Con x) -- should have been changed to this, which works -- foldDoC :: Functor f => (f a -> a) -> A2 (FCon f) -> Con f -> a -- foldDoC f i (InCon t) = f (fmap (foldDoC f i) t) -- this original version causes GHC to hang foldDoC :: Functor f => (f a -> a) -> Con f -> a foldDoC f (InCon t) = f (fmap (foldDoC f) t) doCon :: (DoC (FCon x)) => Con x -> A2 (FCon x) -> A3 (FCon x) doCon (InCon x) = op x -- note that if this is commented out then there's no hang: presumably because GHC doesn't have to perform type deduction for foldDoC. fCon :: (Functor x, DoC (FCon x)) => Con x -> A2 (FCon x) -> A3 (FCon x) fCon = foldDoC op -- -KQ

1 0

Type classes
by Andrew Coppin 04 Jul '10

04 Jul '10

Yesterday I read the Typeclassopedia [again]. In the course of doing this, I discovered that several types have class instances that do something useful. (Indeed, some of these instances do things that I've written custom functions to do.) The trouble is, when you read the documentation, it might say something like data Foo instance Monoid Foo This tells me that Foo is an instance of Monoid. It utterly fails to tell me what the heck the Monoid instance actually *does*. Now, sometimes it's quite obvious. (E.g., just about the only binary operation on lists is (++).) But sometimes it's not less obvious, and sometimes it's so utterly mystifying that just about the only way to find the answer is to either read the source code or run example code and try to deduce some kind of pattern in the answers. In summary, I think we need to devise a way of better-documenting class instances. Sometimes important functionallity can only be accessed using a class, and if it isn't too obvious what a particular class instance does, you can miss that functionallity and end up implementing it again by hand. (Or worse, thinking it's just impossible.) And there's also little quirks like the way Eq usually means value-equality, but for mutable structures it's usually defined as reference-equality. And then of course there are non-standard user-defined classes and their instances...

5 13

One problem with Cabal-install and dependencies
by Michael Lazarev 04 Jul '10

04 Jul '10

Hi, everybody! I think there's either an error in cabal-install, or I don't have an idea on haskell packages. I tried to install one particular library that depends on containers-0.2.0.1 and got the following error: Data/IntMap.hs:182:7: Could not find module `Data.Data': It is a member of the hidden package `base'. Perhaps you need to add `base' to the build-depends in your .cabal file. Use -v to see a list of the files searched for. Then I tried to install containers-0.2.0.1 separately, andin the process of the struggle I found that issuing the following command in containers-0.2.0.1 directory: ~/.cabal/bin/cabal install --constraint="base >= 4" -v ... prints this: Resolving dependencies... selecting containers-0.2.0.1 (hackage) selecting array-0.3.0.1 (installed or hackage) and discarding array-0.1.0.0, 0.2.0.0 and 0.3.0.0 selecting base-3.0.3.2 (installed) and 4.2.0.1 (installed) and discarding syb-0.1.0.0, 0.1.0.1, 0.1.0.2, 0.1.0.3, 0.2 and 0.2.1 selecting ffi-1.0 (installed) selecting ghc-prim-0.2.0.0 (installed) selecting integer-gmp-0.2.0.1 (installed) selecting rts-1.0 (installed) selecting syb-0.1.0.2 (installed) In order, the following would be installed: containers-0.2.0.1 (new version) Configuring containers-0.2.0.1... Dependency array ==0.3.0.1: using array-0.3.0.1 Dependency base ==3.0.3.2: using base-3.0.3.2 And proceeds to building the library: /usr/local/bin/ghc --make -package-name containers-0.2.0.1 -hide-all-packages -fbuilding-cabal-package -i -idist/build -i. -idist/build/autogen -Idist/build/autogen -Idist/build -Iinclude -optP-include -optPdist/build/autogen/cabal_macros.h -odir dist/build -hidir dist/build -stubdir dist/build -package-id array-0.3.0.1-fb28b07fd38a6011f4f73844e0d8281f -package-id base-3.0.3.2-260693a92016991a03206b5a55f6a411 -O -XDeriveDataTypeable -XMagicHash -XRank2Types -XCPP Data.Graph Data.IntMap Data.IntSet Data.Map Data.Sequence Data.Set Data.Tree where, as you see, it really uses base-3.0.3.2, and thus fails. So, my qusetion is, whether I'm doing something wrong, or there are really two errors: 1) cabal-install makes a wrong choice for dependency version 2) cabal-install does not respect the constraint, and proceeds to building the library without any warning

3 4

The Haskell module landscape
by Christopher Done 04 Jul '10

04 Jul '10

I was pondering how naming Haskell packages with a proper hierarchy is quite important, and wondered what the general hierarchy of the Hackage packages was like. So I grabbed the tarball of pakage descriptions[1] from Hackage and ran a little messy Haskell script[2] and got this list: http://gist.github.com/raw/463423/f8458d83b1a7cc26cdbf812747188993e50cd8a2/… Here's a snippet: hsdns: ADNS hsdns: ADNS.Base hsdns: ADNS.Endian hsdns: ADNS.Resolver cv-combinators: AI.CV.ImageProcessors HOpenCV: AI.CV.OpenCV.CV HOpenCV: AI.CV.OpenCV.CxCore HOpenCV: AI.CV.OpenCV.HighGui It's interesting to see how there are quite a few packages that could be easily put into the proper namesace, e.g. ADNS below should be in the Network hierarchy. It's also cool to see clusters of separate packages providing functionality for the same module, e.g. check out Control.Applicative! special-functors: Control.Applicative base: Control.Applicative applicative-extras: Control.Applicative.Backwards applicative-extras: Control.Applicative.Compose applicative-extras: Control.Applicative.Error InfixApplicative: Control.Applicative.Infix category-extras: Control.Applicative.Parameterized action-permutations: Control.Applicative.Permutation applicative-extras: Control.Applicative.State yjtools: Control.Applicative.Tools unicode-symbols: Control.Applicative.Unicode base-unicode-symbols: Control.Applicative.Unicode Control.Concurrent also has a lot going on inside it. There are quite a lot of packages under Network, too. One idea: Hackage could have an additional page which displays this, fully linked up to the packages in question, with an MSDN-style complete collapsible/expandable module hierarchy menu on the left and documentation on the right. I'm not saying that's the right way to do it, but it certainly makes for fun browsing for Haskell's entire open source codebase. (It would also encourage library writers to put their libraries in a useful namespace.) [1]: http://hackage.haskell.org/packages/archive/00-index.tar.gz [2]: http://gist.github.com/463472

1 0

Haskell and Standard ML modules
by José Romildo Malaquias 04 Jul '10

04 Jul '10

Hello. I am writing a Haskell program based on some guidelines written for Standard ML (The Tiger compiler from the "Modern Compiler Implementation in ML" book). The author uses modules for abstracting things like specifities of the taraget machine. For intance, there is a general Frame signature that abstracts the frame representation which depends on the target machine. For each target machine there is a structure compliant to that signature. For instante MipsFrame, PentiumFrame and SparcFrames would be structures implementing the Frame signature. Many parts of the program just see the Frame signature. Is there any guidelines on how to achieve somethying similar to this in Haskell? Regards, Romildo

2 2

Rank2Types and pattern matching
by Yves Parès 04 Jul '10

04 Jul '10

Hello everybody, I'm trying to implement the type protection used by ST to prevent a monad from returning a certain type. There's my code: import Control.Monad.Identity newtype SomeMonad s a = SomeMonad { unSome :: Identity a } deriving (Monad) newtype SomeType s = SomeType Int runSomeMonad :: (forall s. SomeMonad s a) -> a runSomeMonad (SomeMonad x) = runIdentity x And when compiled, I got this error: phantom.hs:10:14: Couldn't match expected type `forall s. PwetMonad s a' against inferred type `PwetMonad s a1' In the pattern: PwetMonad x In the definition of `runPwetMonad': runPwetMonad (PwetMonad x) = runIdentity x But when I change line 10 to: runSomeMonad x = runIdentity . unSome $ x then it works, so obviously, the trouble is about pattern matching. What was I doing wrong?

5 8