June 2010 - Haskell-Cafe

Re: Rewriting a famous library and using the same name: pros and consf
by John Lato 09 Jun '10

09 Jun '10

> From: Stephen Tetley <stephen.tetley(a)gmail.com> > > Hello all > > While new libraries develop at pace, their documentation rarely does; > so I'd have to disagree with John's claim that re-naming libraries > makes development by new users harder. I'd argue that having tutorials > not work for later revisions is more confusing than having various > packages doing the same thing. I'd also contend that beginners are > better off lagging behind the cutting edge and using Parsec 2, > QuickCheck 1, Haskore-vintage, as the earlier version all have > comprehensive documentation - Parsec 2 and Haskore have extensive > manual/tutorials, QuickCheck 1 was small enough that the original > QuickCheck paper covered its use. Lagging behind the cutting edge is one thing, but learning possibly-deprecated or soon-to-be-obsolete interfaces is another. I would contend that in each case the intention is for the earlier version to be superseded because of significant (hopefully user-driven) benefits provided by the new design. Now beginners are in the very frustrating situation of having invested time with a codebase that they learn is obsolete. Depending on the significance of the changes, some amount of that knowledge can be carried forward, but it's a disheartening position to be in and I would expect a few could give up entirely at that point. I think that's worse than floundering around with no documentation at all. Of course a better solution is for maintainers to update their manuals! > > An advantage of separate names (both for the package name and module > name-space) is that its easier to have both packages installed at the > same time - the old one to work with while learning the package, the > new one if other installed packages depend on it. This can still be > done with package-hiding but its less straight-forward. With proper .cabal files and dependency bounds this isn't an issue. If you're working in ghci I think it's the same amount of work either way, at least with my workflow.

4 3

Proposal to solve Haskell's MPTC dilemma
by Carlos Camarao 09 Jun '10

09 Jun '10

This message presents, informally, a proposal to solve Haskell's MPTC (multi-parameter type class) dilemma. If this informal proposal turns out to be acceptable, we (I am a volunteer) can proceed and make a concrete proposal. The proposal has been published in the SBLP'2009 proceedings and is available at www.dcc.ufmg.br/~camarao/CT/solution-to-MPTC-dilemma.pdf The well-known dilemma (hackage.haskell.org/trac/haskell-prime/wiki/MultiParamTypeClassesDilemma) is that it is generally accepted that MPTCs are very useful, but their introduction is thought to require the introduction also of FDs (Functional Dependencies) or another mechanism like ATs (Associated Types) and FDs are tricky and ATs, somewhat in a similar situation, have been defined more recently and there is less experience with its use. In www.haskell.org/ghc/dist/current/docs/html/users_guide/type-class-extension… there exists a solution to the termination problem related to the introduction of MPTCs in Haskell. In our proposal, neither FDs nor any other mechanism like ATs are needed in order to introduce MPTCs in Haskell; the only change we have to make is in the ambiguity rule. This is explained below. The termination problem is essentially ortogonal and can be dealt with, with minor changes, as described in the solution presented in the above mentioned (type-class-extensions) web page. Let us review the ambiguity rule used in Haskell-98 and after that the ambiguity rule used in GHC. Haskell-98 ambiguity rule (which is adequate for Haskell-98's single parameter type classes) is: a type C => T is ambiguous iff there is a type variable v that occurs in the "context" (constraint set) C but not in the simple (unconstrained) type T. For example: forall a.(Show a, Read a)=>String is ambiguous, because "a" occurs in the constraints (Show a,Read a) but not in the simple type (String). In the context of MPTCs, this rule alone is not enough. Consider, for example (Example 1): class F a b where f:: a->b class O a where o:: a and k = f o:: (C a b,O a) => b Type forall a b. (C a b,O a) => b can be considered to be not ambiguos, since overloading resolution can be defined so that instantiation of "b" can "determine" that "a" should also be instantiated (as FD b|->a does), thus resolving the overloading. GHC, since at least version 6.8, makes significant progress towards a definition of ambiguity in the context of MPTCs; GHC 6.10.3 Users Guide says (section 7.8.1.1): "GHC imposes the following restrictions on the constraints in a type signature. Consider the type: forall tv1..tvn (c1, ...,cn) => type. ... Each universally quantified type variable tvi must be reachable from type. A type variable a is reachable if it appears in the same constraint as either a type variable free in the type, or another reachable type variable. For example, type variable "a" in constraint (O a) in the example above is reachable, because it appears in (C a b) (the same constraint as type variable "b", which occurs in the simple type). Our proposal is: consider unreachability not as indication of ambiguity but as a condition to trigger overloading resolution (in a similar way that FDs trigger overloading resolution): when there is at least one unreachable variable and overloading is found not to be resolved, then we have ambiguity. Overloading is resolved iff there is a unique substitution that can be used to specialize the constraint set to one, available in the current context, such that the specialized constraint does not contain unreachable type variables. (A formal definition, with full details, is in the cited SBLP'09 paper.) Consider, in Example 1, that we have a single instance of F and O, say: instance F Bool Bool where f = not instance O Bool where o = True and consider also that "k" is used as in e.g.: kb = not k According to our proposal, kb is well-typed. Its type is Bool. This occurs because (F a b, O a)=>Bool can be simplified to Bool, since there exists a single substitution that unifies the constraints with instances (F Bool Bool) and (O Bool) available in the current context, namely S = (a|->Bool,b|->Bool). As another example (Example 2), consider: {-# NoMonomorphismRestriction, MultiParameterTypeClasses #-} data Matrix = ... data Vector = ... class Mult a b c where (*):: a ! b ! c instance Mult Matrix Vector Matrix where (*) = ... instance Mult Matrix Vector Vector where (*) = ... m1:: Matrix = ... m2:: Vector = ... m3:: Vector = ... m = (m1 * m2) * m3 GHC gives the following type to m: m :: forall a, b. (Mult Matrix Vector a, Mult a Vector b) => b However, "m" cannot be used effectively in a program compiled with GHC: if we annotate m::Matrix, a type error is reported. This occurs because the type inferred for "m" includes constraints (Mult Matrix Vector a, Mult a Vector Matrix) and, with b|->Matrix, type variable "a" appears only in the constraint set, and this type is considered ambiguous. Similarly, if "m" is annotated with type Vector, the type is also considered ambiguous. There is no means of specializing type variable "a" occurring in the type of "m" to Matrix. And no FD may be used in order to achieve such specialization, because we do not have here a FD: "a" and "b" do not determine "c" in class Mult: for (a,b = Matrix,Vector), we can have "c" equal to either Matrix or Vector. According to our proposal, type m:: forall a. (Mult Matrix Vector a, Mult a Vector Matrix)) => Matrix is not ambiguous, in the context of the class and instance declarations of Example 2 (since "a" can be instantiated to Matrix), whereas type m:: forall a.(Mult Matrix Vector a, Mult a Vector Matrix)) => Vector is ambiguous in this context. We would like to encourage compiler front-end developers to change Haskell's ambiguity rule, and test with as many examples as desired, including recurring examples that appear in Haskell mailing lists involving MPTCs, FDs etc. We would like to hear and discuss your doubts, opinions, comments, criticisms etc. Cheers, Carlos

10 20

Tricks with GMap -- question about conflicts w/ indexed type families
by oleg＠okmij.org 08 Jun '10

08 Jun '10

Ryan Newton wrote: > What I would next *like* to do is something like the following: > > import qualified Data.IntMap as DI > instance FitInWord t => GMapKey t where > data GMap t v = GMapInt (DI.IntMap v) deriving Show > > The problem is that there's already a more general instance of GMapKey > that handles pairs by representing them as nested GMaps: > > instance (GMapKey a, GMapKey b) => GMapKey (a, b) where > data GMap (a, b) v = GMapPair (GMap a (GMap b v)) > .... > > Ideally, I want both of these to coexist (and to prioritize the more > specific one). With normal type classes, OverlappingInstances can > handle this, but with type families I get an error like the > following: First of all, if we forget about data families, OverlappingInstances still won't give us the desired behavior. GHC chooses overlapping instances based only on the instance head type, disregarding all constraints. Therefore, when asked to choose an instance for GMapKey (Int16,Int16), GHC would choose the second instance as it is more specific: the type (a,b) is more specific that the type t. Again, the constraints such as FitInWord are not used when choosing instances. This issue is discussed in detail at Choosing a type-class instance based on the context http://okmij.org/ftp/Haskell/types.html#class-based-overloading and on the Wiki Page http://haskell.org/haskellwiki/GHC/AdvancedOverlap These pages explain how can we make class constraints bear on the instance selection. But we still have the second problem: data families do not permit overlapping declarations. At first blush, it appears impossible to define GMapKey for specific pairs and default to the generic GMap instance for general pairs. Fortunately, a solution exists, shown below. The idea is to define an auxiliary type class (without data families). Such a type class permits overlapping instances and so makes possible the desired behavior of specific instances with the generic default. {-# LANGUAGE FlexibleInstances, FlexibleContexts #-} {-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-} {-# LANGUAGE TypeFamilies #-} {-# LANGUAGE UndecidableInstances #-} {-# LANGUAGE OverlappingInstances #-} module GM where import Data.Int import Data.Word import Data.Bits import qualified Data.IntMap as IM -- ===== Begin a simplified GMap package -- A simplified class GMapKey class GMapKey t where data GMap t :: * -> * empty :: GMap t v lookup :: t -> GMap t v -> Maybe v instance GMapKey Int16 where data GMap Int16 v = GMI16 (IM.IntMap v) empty = GMI16 $ IM.empty lookup k (GMI16 m) = IM.lookup (fromIntegral k) m instance GMapKey Int32 where data GMap Int32 v = GMI32 (IM.IntMap v) empty = GMI32 $ IM.empty lookup k (GMI32 m) = IM.lookup (fromIntegral k) m -- Generic instance for pairs instance (GMapKey a, GMapKey b) => GMapKey (a, b) where data GMap (a, b) v = GMapPair (GMap a (GMap b v)) empty = GMapPair $ empty lookup k (GMapPair m) = error "Invoking the generic instance for pairs" -- ===== End the simplified GMap package -- The following is an optimization, which should appear in a different -- module. The optimization should not disturb the original GMap code. -- The following optimization is Ryan Newton's code -- A class for values that fit within one word class FitInWord v where toWord :: v -> Word fromWord :: Word -> v instance FitInWord (Int16,Int16) where toWord (a,b) = shiftL (fromIntegral a) 16 + (fromIntegral b) fromWord n = (fromIntegral$ shiftR n 16, fromIntegral$ n .&. 0xFFFF) -- Now we wish to define optimized instances of GMapKey for -- pairs of items that fit within a word. -- The following answers Ryan Newton's question -- Define our own product type, to avoid overlapping instances with the -- general GMapKey for pairs -- It's a newtype: it has no run-time overhead newtype OptimalPair a b = OptimalPair (a,b) instance FitInWord (a,b) => GMapKey (OptimalPair a b) where data GMap (OptimalPair a b) v = GMapInt (IM.IntMap v) deriving Show empty = GMapInt IM.empty lookup (OptimalPair k) (GMapInt m) = IM.lookup (fromIntegral$ toWord k) m -- Auxiliary class to choose the appropriate pair class ChoosePairRepr a b pr | a b -> pr where choose_pair :: (a,b) -> pr choosen_pair :: pr -> (a,b) instance ChoosePairRepr Int16 Int16 (OptimalPair Int16 Int16) where choose_pair = OptimalPair choosen_pair (OptimalPair p) = p -- Repeat the above for all other optimal pairs: -- (Int8, Int16), (Int16, Int8), etc. -- Template Haskell is very good to generate all such boiler-plate instances -- Choose a generic pair for all other pairs of values instance pr ~ (a,b) => ChoosePairRepr a b pr where choose_pair = id choosen_pair = id -- tests -- A specific instance is chosen test1 = let m = empty in GM.lookup (choose_pair (1::Int16,2::Int16)) m -- Nothing -- A general pair instance is chosen test2 = let m = empty in GM.lookup (choose_pair (1::Int32,2::Int16)) m -- *** Exception: Invoking the generic instance for pairs

1 0

Fwd: [Haskell-cafe] Rewriting a famous library and using the same name: pros and cons
by Jake McArthur 08 Jun '10

08 Jun '10

Sorry, I hit Reply instead of Reply To All. ---------- Forwarded message ---------- From: Jake McArthur <jake.mcarthur(a)gmail.com> Date: Tue, Jun 8, 2010 at 6:16 PM Subject: Re: [Haskell-cafe] Rewriting a famous library and using the same name: pros and cons To: Don Stewart <dons(a)galois.com> Making a new name for an existing package subverts the intended meaning of major revision numbers. Libraries that break as a result of a major revision should have had more specific dependencies, and tutorials that go out of date should also have specified the version number of the package for which they were intended. It's a package maintainer's responsibility to respect version number conventions. I don't believe it is a package maintainer's responsibility to account for blatant misuse of it. - Jake

1 0

Re: [Haskell] Re: [Haskell-cafe] Please check your dependencies on fgl
by Ivan Lazar Miljenovic 08 Jun '10

08 Jun '10

Ian Lynagh <igloo(a)earth.li> writes: > On Mon, Jun 07, 2010 at 11:50:44AM -0700, Donald Bruce Stewart wrote: > >> A complete rewrite with a new maintainer: fgl-awesome > > In 10 years time, we don't want to have > fgl > fgl-awesome > fgl-great > fgl-joe > which all do the same thing, and have an unclear relationship to each > other. Definitely (though hopefully we wouldn't pick names like "fgl-awesome" anyway...). > I think the important question is: Once the new FGL is finished, will > there be a good reason (other than backwards compatibility) for people > to use the current FGL? > > If yes, then different names should be used. Otherwise, no matter how > different the API is, keeping the same name is the right thing to do. And this is why we're going to request the community's input on our API design: to try and avoid the situation where there's a specific reason to keep using the old one. As it stands, the only real advantage that I can think of is that the new version uses extensions, the old version doesn't (and hence is more compatible). > So if there is consensus that the new design is a better fgl, I think it > ought to keep the name. Which is what we're trying to build (the consensus, that is). Don has started a wiki page with the arguments here, and I've already added my 2c: http://haskell.org/haskellwiki/Libraries/WhenToRewriteOrRename -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

1 0

Problems with threading?
by Louis Wasserman 08 Jun '10

08 Jun '10

While working on the Shootout, I noticed the following benchmarks: http://shootout.alioth.debian.org/u64/program.php?test=chameneosredux&lang=… <http://shootout.alioth.debian.org/u64/program.php?test=chameneosredux&lang=…> http://shootout.alioth.debian.org/u64q/program.php?test=chameneosredux&lang… The same program becomes almost 4 times slower when compiled with --threaded and run with +RTS -N5 -- even though the multi-core benchmark really only ever uses one processor. Other languages seem to have found a way of arranging these threads in a way such that parallelism actually happens, but as it stands, compiling this benchmark without --threaded actually makes Haskell competitive against the genuinely parallel alternatives in other languages...which is unusual by itself. I wanted to throw this out for people to discuss, because I'd like to see it improved. As it stands, I'm going to submit a version which asks not to be compiled with --threaded (and has a few other improvements). <http://shootout.alioth.debian.org/u64q/program.php?test=chameneosredux&lang…> Louis Wasserman wasserman.louis(a)gmail.com http://profiles.google.com/wasserman.louis

4 4

Re: [Haskell-cafe] is there a way to prove the equivalence of these two implementations of (Prelude) break function?
by Alexander Solla 08 Jun '10

08 Jun '10

On Jun 8, 2010, at 2:38 AM, Alberto G. Corona wrote: > This is`t a manifestation of the Curry-Howard isomorphism? Yes, basically. If we rephrase the isomorphism as "a proof is a program, the formula it proves is a type for the program" (as Wikipedia states it), we can see the connection. The "characterization" of prelBreak I gave is a "type" for prelBreak. The type is richer than we can express in the Haskell type system ("prelbreak accepts a proposition p and a list xs, and returns a pair whose first element is the largest prefix of xs for which no x satisfies p, and whose second element is the complement of the first, taken in xs."), but we can still reason about the richer type mathematically, and the Curry-Howard isomorphism applies to it.

1 0

Function to find a substring
by R J 08 Jun '10

08 Jun '10

What's an elegant definition of a Haskell function that takes two strings and returns "Nothing" in case the first string isn't a substring of the first, or "Just i", where i is the index number of the position within the first string where the second string begins? _________________________________________________________________ Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

7 6

is there a way to prove the equivalence of these two implementations of (Prelude) break function?
by Thomas Hartman 08 Jun '10

08 Jun '10

Here's two implementations of break, a snappy one from the prelude, and a slow stupid stateful one. They are quickchecked to be identical. Is there a way to prove they are identical mathematically? What are the techniques involved? Or to transform one to the other? import Control.Monad.State import Test.QuickCheck tThis = take 5 . show . mybreak (>4000000) $ [1..10^7] tPrel = take 5 . show . prelbreak (>4000000) $ [1..10^7] prelbreak p xs = (takeWhile (not . p) xs,dropWhile (not . p) xs) -- fast, more or less as implemented in prelude iiuc mybreak p xs = evalState (brk p) ([],xs) -- stateful, slow brk p = do (notsat,remaining) <- get case remaining of [] -> return (notsat,remaining) (r:rs) -> if p r then return (notsat,remaining) else do put (notsat++[r],rs) -- ++ is probaby a major reason brk p

6 6

Fwd: [Gtk2hs-users] Installation problem with cairo.
by Magicloud Magiclouds 08 Jun '10

08 Jun '10

Hi, I cannot subscribe to libraries maillist. So I forward this here. I cannot install gtk2hs-cairo by cabal using cairo 1.9.6 compiled myself. Cabal always said that the cairo library/devel files were missing. ---------- Forwarded message ---------- From: Axel Simon <Axel.Simon(a)in.tum.de> Date: Tue, Jun 8, 2010 at 7:15 PM Subject: Re: [Gtk2hs-users] Installation problem with cairo. To: Magicloud Magiclouds <magicloud.magiclouds(a)gmail.com> Cc: gtk2hs-users <gtk2hs-users(a)lists.sourceforge.net> Hi again, it's very difficult for me to say what is happening. Could you ask on the cabal mailing list to see if anybody there has an idea. Cheers, Axel On 08.06.2010, at 11:01, Magicloud Magiclouds wrote: > I've tried a little, the error was not thrown out in gtk2hssetup.hs. > And even I faked a version (1.8.10), it did not work. > > On Tue, Jun 8, 2010 at 3:47 PM, Axel Simon <Axel.Simon(a)in.tum.de> wrote: >> >> Hi, >> >> On Jun 8, 2010, at 9:21, Magicloud Magiclouds wrote: >> >>> Yes, seems like so. >>> Here is the output: >>> >>> # /usr/bin/pkg-config --modversion cairo-pdf >>> 1.9.6 >>> # /usr/bin/pkg-config --modversion cairo-ps >>> 1.9.6 >>> # /usr/bin/pkg-config --modversion cairo-svg >>> 1.9.6 >>> # /usr/bin/pkg-config --modversion cairo >>> 1.9.6 >>> >> >> Oh dear. >> >> Since cabal manages once to get the correct version and fails later on, I >> assume it's the magic Duncan added to out Gtk2HsSetup.hs file that requests >> the package version again. If you look for >> >> --FIXME: Cabal should tell us the selected pkg-config package versions in >> the >> -- LocalBuildInfo or equivalent. >> -- In the mean time, ask pkg-config again. >> >> in the cabal file and try to add some debugging output then maybe you can >> find out more. >> >> I suspect that either the LocalBuildInfo or the PackageDescription value is >> not the most up-to-date one but some default value that lack some path or >> some such. >> >> cheers, >> Axel >> >>> On Tue, Jun 8, 2010 at 2:56 PM, Axel Simon <Axel.Simon(a)in.tum.de> wrote: >>>> >>>> Hi, >>>> >>>> On Jun 8, 2010, at 8:54, Magicloud Magiclouds wrote: >>>> >>>>> /usr/bin/pkg-config --modversion cairo >>>>> setup: Missing dependency on a foreign library: >>>>> * Missing C library: cairo >>>>> This problem can usually be solved by installing the system package that >>>>> provides this library (you may need the "-dev" version). If the library >>>>> is >>>>> already installed but in a non-standard location then you can use the >>>>> flags >>>>> --extra-include-dirs= and --extra-lib-dirs= to specify where it is. >>>> >>>> well, what's the output of >>>> >>>>> /usr/bin/pkg-config --modversion cairo >>>> >>>> ? Maybe cabal fails to parse the version for some reason. >>>> >>>> Axel >>>> >>>> >>> >>> >>> >>> -- >>> 竹密岂妨流水过 >>> 山高哪阻野云飞 >> >> > > > > -- > 竹密岂妨流水过 > 山高哪阻野云飞 -- 竹密岂妨流水过山高哪阻野云飞

1 0