December 2004 - Haskell-Cafe

ghc has problems with 'zipWith' ?
by Derek Elkins 10 Dec '04

10 Dec '04

> Is it possible and senseful for a compiler to extract common > sub-expressions? Naively I think that for a given tree of an > expression it is efficiently possible to find all common sub-trees. > Referential transparency would assure that equal expressions have the > same value, so they can be replaced by the same object. E.g. the > example above could be automatically transformed to: > > ms as = > let tmp0 = zipWith (+) (zipWith (*) as tmp1) (0:tmp1) > tmp1 = 1:tmp0 > in tmp0 It's possible and will preserve semantics, but isn't always an optimization. http://www.haskell.org/pipermail/haskell-cafe/2003-December/005574.html

2 1

Parse text difficulty
by Derek Elkins 09 Dec '04

09 Dec '04

> Robert Dockins <robdockins at fastmail.fm> writes: > > > > And I thought that most programmers used "zipWith", which has to > > > be prefix. > > > [1..5] `zipWith (+)` [7..] > > You don't have a computer at your end of the internet? :-) > > Prelude> [1..5] `zipWith (+)` [7..] > <interactive>:1: parse error on input `(' > Prelude> let zwp = zipWith (+) in [1..5] `zwp` [7..] > [8,10,12,14,16] A way to accomplish the above is given on http://www.haskell.org/hawiki/InfixExpression Also for those who haven't looked too hard at the wiki (or at all), http://www.haskell.org/hawiki/CommonHaskellIdioms is probably the most densely packed page of information on it and makes a great starting point for finding answers on the wiki. The above link is on it, and also the perennial questions about making functions strict is on it under section "Efficiency" "ForcingEagerEvaluation" (where you'll find things like DeepSeq), and some documentation on Control.Monad.* modules under MonadTemplateLibrary. So, just in general, it's a useful and interesting page, and many posts to haskell(-cafe) can be avoided just by perusing it.

1 0

RE: [Haskell-cafe] Non-technical Haskell question
by azrael＠demonlords.net 09 Dec '04

09 Dec '04

> -------- Original Message -------- > Subject: Re: [Haskell-cafe] Non-technical Haskell question > From: "Keith Wansbrough" <Keith.Wansbrough(a)cl.cam.ac.uk> > Date: Mon, December 06, 2004 9:00 am > To: "Georg Martius" <mai99dgf(a)studserv.uni-leipzig.de> > Cc: "Jason Bailey" <azrael(a)demonlords.net>, "Jules Bean" > <jules(a)jellybean.co.uk>, Haskell-Cafe(a)haskell.org > > > > When I compile it I get three files, an actual runnable binary (at only > > > 5M in size), a .o file and a .hi file. I'm sure these additional files > > > are usefull in someway and as soon as I come across the right piece of > > > documentation everything should make sense. But as a person new to the > > > language I'm just left wondering why. > > gcc of course leaves .o files lying around, so this is no different than C. > > javac often creates tens or hundreds of .class files, some with > strange names like MyClass$1.class, MyClass$2.class, and so on (yes, I > know what they are for), and doesn't even generate a native binary. The original observation was that the compiler seems archaic. When asked, I gave some general comments. What I should have just said was that it was to much like a C compiler. Which, no matter how neat you think it is, is archaic. When I use javac every file that is created is necessary for the application to run. This can't be said of the ghc compiler. Having an excuse that this is way the C compiler does it or that this is the way its always been done is to poor of a reason to even argue against. If a file isn't needed then it shouldn't be left there. > I don't think the output of ghc is any more surprising than these; I'm > surprised it bothers you. > Does this bother me? Not in particular, its just an indication that this is an old design. > The static vs dynamic linking question has been discussed many times. > The summary is: GHC is a highly-optimising compiler, and the binary > interface _necessarily_ changes with every minor revision (even > patchlevel revision) of the compiler and each library. So you can't > sensibly share libraries between apps. Anyway, disc is cheap. > I design and build business applications. I'm very good at this. Part of being very good at something like that is acknowledging that that there are some areas where I can't be as good.. such as compilers. The reason I say this is that if your telling me that no one here can figure out how to make it work then I will take your word for it. I'm certainly not in a position to argue :) The whole disc is cheap argument is a cop out. Certainly for a single application this is true. But your inherently limiting yourself. This means no one would consider haskell for embedded devices, or an OS, and it would even impact to a certain degree the decision to use it for a commericial product. You can see how this is reflected today in the fact that you can find almost no binary programs available for download. Programs and applications are out there but almost exclusivly as source code and yes a few of the website even mention that the binary size is the reason why they aren't making it available. (bandwith costs time and money) However this is just a view of a rank and file programmer who's new to haskell. Some of my concerns and issues are probably not valid just because I am not familiar with the language as a whole. However if there is a desire to make Haskell more accessible to the majority of programmers then the first impressions that I, and those like me have is important. Jason > HTH. > > --KW 8-)

20 21

Re: Haskell and qualified identifiers
by Duncan Coutts 08 Dec '04

08 Dec '04

On Wed, 2004-12-08 at 17:04 +0100, Henning Thielemann wrote: > On Wed, 8 Dec 2004, Duncan Coutts wrote: > > > There are actually several options here, you can import modules only > > qualified, then every value from that module needs to be qualified. Some > > modules are designed to be used this way, see for example Data.HashTable > > http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.HashTable.h… > > (and people are encouraged to write new modules in this style). > > Good to know that there others who conform to this style. But ... why is > the name of HashTable still HashTable.HashTable? Wouldn't be HashTable.T, > HashTable.Type or something like that the better choice? I see your point. I use HashTable like so: import Data.HashTable (HashTable) import qualified Data.HashTable as HashTable That way you can use HashTable unqualified as the name of the type, and then all the other operations are qualified like HashTable.new, HashTable.lookup etc This is like the C++/Java OOP naming convention. The class name is the type and it also qualifies all of the operations. This style is quite readable I find without requiring java.system.io.very.long.qualified.names.all.over.the.place. :-) Duncan

2 1

RE: [Haskell-cafe] namespacing?
by Jason Bailey 08 Dec '04

08 Dec '04

I'm appreciating the feedback. I discovered where I was going wrong. The library I was using allowed me to import a module, which in turn allowed me to use functions from other modules. So even though I could use func directly I couldn't use B.func because I hadn't explicitly imported B. I find that interesting. I would have thought that if I hadn't explicitly imported a module I would either be forced to use the qualified name, not use the function at all, or at the very least be allowed to qualify the name. thanks Jason > -------- Original Message -------- > Subject: Re: [Haskell-cafe] namespacing? > From: "Duncan Coutts" <duncan.coutts(a)worc.ox.ac.uk> > Date: Wed, December 08, 2004 10:12 am > To: azrael(a)demonlords.net > Cc: haskell-cafe(a)haskell.org > > On Wed, 2004-12-08 at 07:58 -0700, azrael(a)demonlords.net wrote: > > I've got a general new person type question. > > > > I understand that I can hide a function in a module that I am importing > > if it conflicts with another identical function name. > > > > But if the situation arises that I would like to use two identically > > named functions from two different modules is there anyway for me to > > specify that I want to use the function from module A rather then the > > function from module B. > > module C where > > import A > import qualified A (foo) > > import B > import qualified B (foo) > > > ... A.foo ... > > ... B.foo ... > > > There are actually several options here, you can import modules only > qualified, then every value from that module needs to be qualified. Some > modules are designed to be used this way, see for example Data.HashTable > http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data.HashTable.h… > (and people are encouraged to write new modules in this style). > > If it's just one or two values that clash then the example above is > good, ie import the whole thing unqualified and just qualify the one or > two names that clash. > > You can even give short names to modules you import, eg: > > import qualified System.Gnome.GConf as Config > > now I can say Config.get rather than System.Gnome.GConf.get > > Hope this helps. > > Duncan

1 0

namespacing?
by azrael＠demonlords.net 08 Dec '04

08 Dec '04

I've got a general new person type question. I understand that I can hide a function in a module that I am importing if it conflicts with another identical function name. But if the situation arises that I would like to use two identically named functions from two different modules is there anyway for me to specify that I want to use the function from module A rather then the function from module B. thanks Jason

4 3

RE: [Haskell-cafe] More on dynlinking
by Simon Marlow 08 Dec '04

08 Dec '04

Your suggestion amounts to giving the programmer more control over the ABI compared to the current extreme options: (a) -O0, ABI == API (b) -O[12], ABI == entire implementation + ABI of dependencies in addition, the ABI includes the version of GHC that compiled the code. Providing an option somewhere between (a) and (b) seems reaonsable. Making the details work out is pretty tricky: for example, you can't inline the definition of an unexposed function into an exposed function. Indeed, the inlining of an exposed function can't depend even on the type of a hidden function. Cheers, Simon On 07 December 2004 14:24, Robert Dockins wrote: > What if (go with me here) we invent a new aggregate unit of haskell > code, and we call it a library, and we design libraries with the > express intent of allowing dynamic linking. We would desire: > > 1) True dynamic linking for reduced memory (and disk) footprint and > drop-in replacement > > 2) ABI versioning (because its a mess otherwise) > > 3) Acceptable performance penalties, by still allowing inlining of > some code > > I propose something along these lines. Libraries are composed of some > number of modules. A module is either an "interior" or "boundry" > module; the library author somehow distinguishes the boundry modules. > The library is compiled as normal and the object files are packeged > together. The .hi files of _boundry_ modules are combined into a > single library-wide interface file, which is then packaged together > with the library code. The interface file would contain a) the > definition of any functions _declared_ in a boundry modules b) > datatypes and classes _exported_ from boundry modules c) the types > (but not definitions) of > any functions re-exported through a boundry module d) instances for > classes which are either imported from elsewhere or exported from a > boundry module e) a version number (eg, with major, minor and build > numbers). The library-wide interface file, and the sybmol names of > closures for the exported functions then constitute the ABI. > > Future changes to or deletions of elements in the interface represent > an incompatable change, whereas additions would be compatable. > Libraries > can then have their version numbers incremented when incompatable > changes are made. > > > This method then allows the library author to decide where to trade > off possible optimizations for implementation hiding (by deciding > what to > put in boundry modules). Things ripe for inlining and unlikley to > change, like monad definitions, could go in the boundry modules, > whereas more volitle heavyweight code could stay in the interior. To > get > behavior similar to the current package behavior, just declare all > modules boundry modules, but still reap some of the reduced footprint > advantages. > > OK, those are my thoughts, flame away, :) > > Robert Dockins > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

ghc has problems with 'zipWith' ?
by Daniel Fischer 08 Dec '04

08 Dec '04

Hi, I have recently come across the curious phenomenon that ghci is sometimes much slower than hugs. The occasion that gave rise to it was in connection with continued fractions, where, having a continued fraction with quotients a(n), n >= 0, you get the numerators of the convergents by the recursion formula p(n) = a(n)*p(n-1) + p(n-2) starting with p(-2) = 0 and p(-1) = 1 (same recursion formula for the denominators, starting with q(-2) = 1 and q(-1) = 0). Now I implemented this algorithm first using 'zipWith': ms :: [Integer] -> [Integer] ms as = zipWith (+) (zipWith (*) as (1:ms as)) (0:1:ms as) only to find it awfully slow, ms (replicate 27 2) for example took over 10 seconds, feeding a large list to 'ms' is inadvisable. Then I wrote a fast version of that algorithm, namely ps :: [Integer] -> [Integer] ps as = pStep 0 1 as where pStep :: Integer -> Integer -> [Integer] -> [Integer] pStep _ _ [] = [] pStep x y (a:as) = z:pStep y z as where z = a*y+x This works fine, so I wanted to find out what went wrong in the first version. In hugs, the 'zipWith'-version takes fewer reductions and both versions take more or less the same time, much less than 'ms' in ghci, more than 'ps' in ghci. The performance of 'ms' in ghci is significantly improved by a 'let' (or 'where') expression: pms :: [Integer] -> [Integer] pms as = let mas = pms as in zipWith (+) (zipWith (*) as (1:mas)) (0:1:mas) (no difference in hugs), however this is still much slower than 'ps', last (pms (replicate 1000 1)) takes about 2.75 secs, last (ps (replicate 1000 1)) about 0.01, even last (ps (replicate 10000 1)) took only 0.34 secs. Since usually ghci is MUCH faster than hugs, I am baffled by this behaviour. Does anybody know why this is so? And, apart from avoiding 'zipWith', what can be done to remedy the situation? Greetings, Daniel Fischer P.S.: ghci doesn't take 'zipWith' too well in other circumstances either, referring to the example of Fibonacci numbers in the book of Simon Thompson, the 'fastFib' function on page 76 runs faster in ghci than 'fibs' on page 431, in hugs, 'fibs!!n' takes fewer reductions (no big difference though).

3 3

numerical subtyping
by Derek Elkins 08 Dec '04

08 Dec '04

> Is there a standard Haskell trick for checking run-time assignment to > data types? I'd like a data type of Probability that ensures its > Double argument is between 0 and 1. > > Jim A fairly common technique to achieve this is smart constructors (apparently also called factory functions). http://www.haskell.org/hawiki/FactoryFunction You simply enforce the invariant on construction. For your example, it would look like, newtype Probability = Probability Double probability p | 0.0 <= p && p <= 1.0 = Probability p unProbability (Probability p) = p Simply don't export Probability's constructor and it will be impossible to create a Probability with a value outside of [0,1]. However, you may want to export the constructor, or alternatively, export a function with a name like unsafeProbability (= Probability) for situations where you can statically decide that the invariant will hold if the superfluous checking costs too much, which doesn't seem particularly likely in this case. Providing a function of type Double -> Maybe Probability is also likely a good idea.

3 2

Re: [Haskell-cafe] ghc has problems with 'zipWith' ?
by Tom Pledger 08 Dec '04

08 Dec '04

Daniel Fischer wrote: >Hi, >I have recently come across the curious phenomenon that ghci is sometimes much >slower than hugs. > [...] >ms as = zipWith (+) (zipWith (*) as (1:ms as)) (0:1:ms as) > Hugs has(**) a specific optimisation for the case where the left hand side of the declaration occurs as a subexpression in the right hand side. You can get a similar benefit under ghci if you share the common subexpression by hand: ms' as = let bs = ms' as in zipWith (+) (zipWith (*) as (1:bs)) (0:1:bs) (**) I haven't actually seen the code in question, and am repeating something which was on one of the mailing lists a few years ago. So please don't treat this as authoritative! Regards, Tom

1 0