June 2011 - Haskell-Cafe

Alex Lexer Performance Issues
by Tristan Ravitch 26 Jun '11

26 Jun '11

Hi Cafe, In one of my projects I have a lexer that seems to be taking an inordinate amount of time and space. The lexer is generated by Alex using the lazy ByteString (with position information) template. I compiled and ran with profiling enabled and I get a report like this: ------------------------------------------------------------------------------- Tue Jun 21 16:56 2011 Time and Allocation Profiling Report (Final) ViewCallGraph +RTS -p -RTS gnutls.bc total time = 51.80 secs (2590 ticks @ 20 ms) total alloc = 9,482,333,244 bytes (excludes profiling overheads) COST CENTRE MODULE %time %alloc alexScanTokens Data.LLVM.Private.Lexer 24.1 4.5 alex_scan_tkn Data.LLVM.Private.Lexer 21.2 32.7 tokenAs Data.LLVM.Private.Parser.Primitive 6.7 2.9 alexGetChar Data.LLVM.Private.Lexer 6.5 22.7 ------------------------------------------------------------------------------- The entries below these four are marginal. The third entry is from my code and isn't a big deal (yet), but the other three seem to indicate that the lexer is responsible for about 50% of my runtime and memory allocation. For reference, this particular input is about 18M of text, though the ratios are just as bad for smaller inputs. My uneducated suspicion is that Alex is constructing separate ByteStrings that it passes to each of my token constructors, and that this is responsible for a large part of this allocation. Most of my token constructors just ignore this ByteString - assuming there really is an allocation for each token, is there any way to avoid it? I was looking at alexScanTokens, alex_scan_tkn, and alexGetChar but didn't see any obvious ways to improve them. Alternatively, does any one have lexing performance tips that might help? Thanks

4 4

Data.Enumerator.List.concatMap is to Data.Iteratee.?
by David Place 26 Jun '11

26 Jun '11

Hi: I've been studying iteratee IO. Is there a function in the iteratee package that is analogous to Data.Enumerator.List.concatMap? ____________________ David Place Owner, Panpipes Ho! LLC http://panpipesho.com d(a)vidplace.com

1 0

Can't use libraries in haskell
by Александр 26 Jun '11

26 Jun '11

Hello, I'm new in haskell. I want to use xml library (http://hackage.haskell.org/package/xml) in my project. I downloaded it.then try to build and install: runhaskell Setup.hs configure runhaskell Setup.hs build runhaskell Setup.hs install All ok. There are no errors. When i try import modules from this lib to my project, for example: import Text.XML.Light.Cursor I get error: /home/shk/dev/src/XMPP.hs:8:8: Could not find module `Text.XML.Light.Cursor': Use -v to see a list of the files searched for. Failed, modules loaded: none. if i try: > cabal install xml Resolving dependencies... No packages to be installed. All the requested packages are already installed. If you want to reinstall anyway then use the --reinstall flag. What's wrong? How can i install and use library in haskell? Thank you.

3 3

Re: [Haskell-cafe] commutative monoid?
by wren ng thornton 26 Jun '11

26 Jun '11

On 6/25/11 1:34 AM, Evan Laforge wrote: > So there's a range of possible Monoid instances for each type, More for some types than for others. For Maybe there are three: * always take the first/left value; * always take the last/right value; * or, use a semigroup operation defined on the values. The first two options are provided by the First and Last newtypes, and the third option is provided by the instance for Maybe itself (except that it spuriously requires a Monoid instance instead of just a semigroup). For integers there are at least four obvious ones (min, max, addition, multiplication), and numerous less obvious ones. For real numbers we can also add the logarithmic and exponential versions. Etc. > maybe they were chosen by historical happenstance rather than some > kind of "principle monoid" (is there such a thing?). Is there a name > for the thing that's like a monoid, but the operator is commutative > too? "Commutative monoid" :) > That would narrow down the implementation choices, e.g. Data.Map > would have to combine the values. So it seems like if your operation > is commutative, you can put it in "c-monoid" and not rely so much on > the happenstance of the instances, since they are more constrained. They're more constrained, but still not enough to make things unique. All four of the obvious ones I mentioned for integers are commutative. You could keep constraining things further. But how constrained do you want to be? In some sense, there will always be room for multiple interpretations. Occasionally things magic their way into being unique, but usually not. Much of the last century of physics has been spent debating between different interpretations of some extremely constrained systems. So far as I'm aware, there's still no consensus about which interpretation is "right". > And of course you are then free to reorder things, which is a nice bit > of flexibility. Indeed, commutativity is a wonderful property to take advantage of when you can. > So is there a typeclass for that? There might be one hidden in one of the attempts at redesigning the numeric hierarchy (e.g., Numeric Prelude), but there's not a canonical typeclass for them. Unfortunately it's not really a good match for the typeclass system since it doesn't introduce any new operations, it only introduces laws--- which aren't verified nor enforced. Though, if you happen to know the property does hold, then you're free to take advantage of it. (E.g., for the Maybe instance which uses a semigroup operation, if the semigroup op is commutative then so is the monoid op.) -- Live well, ~wren

3 4

Re: [Haskell-cafe] Iteratee IO examples
by wren ng thornton 25 Jun '11

25 Jun '11

On 6/25/11 6:51 AM, John Lato wrote: > Honestly I'm quite dis-satisfied with the current state of code which > depends on iteratee/enumerator. It's nearly all written in a very low-level > style, i.e. directly writing 'liftI step', or 'case x of Yield -> ...'. > This is exactly what I would hope users could avoid, by using the functions > in e.g. Data.Iteratee.ListLike. > > I've recently added more functions to iteratee which greatly reduce the need > for this type of code. I don't know about enumerator, but I expect it isn't > rich enough since most user code I've seen is pretty low-level. I have a rather large suite of list-like functions for the old version of iteratee (used by a project I've been working on for a while). Once I get the time to convert the project to the newer iteratee, I'll send a patch with any you're still missing. (Though, admittedly, I'm not terribly keen on ListLike. The classes still seem too monolithic and ad-hoc. Though I'm not sure there's a way around that without something closer to ML's functor modules.) -- Live well, ~wren

2 1

Re: [Haskell-cafe] Map Monoid instance (was commutative monoid?)
by wren ng thornton 25 Jun '11

25 Jun '11

On 6/25/11 2:15 PM, Erik Hesselink wrote: > On Sat, Jun 25, 2011 at 19:07, Evan Laforge<qdunkan(a)gmail.com> wrote: >> On Sat, Jun 25, 2011 at 9:00 AM, Jens Blanck<jens.blanck(a)gmail.com> wrote: >>>>> So there's a range of possible Monoid instances for each type, >>>> >>>> More for some types than for others. For Maybe there are three: >>>> >>>> * always take the first/left value; >>>> * always take the last/right value; >>>> * or, use a semigroup operation defined on the values. > > Brent Yorgey recently blogged about a fourth instance [1] which also > uses the semigroup operation on the values, but treats Nothing as > failure, returning Nothing. > > Erik > > [1] https://byorgey.wordpress.com/2011/04/18/monoids-for-maybe/ Ah, yes. I forgot about that one. Though technically that one actually requires a monoid, not just a semigroup, since mempty = Just mempty. Which furthers the point that most types have an abundance of monoid instances. -- Live well, ~wren

1 0

Re: [Haskell-cafe] Map Monoid instance (was commutative monoid?)
by wren ng thornton 25 Jun '11

25 Jun '11

On 6/25/11 1:07 PM, Evan Laforge wrote: > In the > case of the overriding version, you have to decide on which side to > merge the new monoid, and on the lifted one the two choices become > four, since you then have to decide whether the unionWith argument > should be flipped or not. > [...] > So I think the Data.Map choice is reasonable for that reason. If it > were lifted, it would have to make a hard-coded decision about the > "side". If you have to write your own, that's under your control. You should pass them through in the same order, to maximize intuitability. Order swapping can be handled by the Dual newtype. -- Live well, ~wren

1 0

Re: [Haskell-cafe] Map Monoid instance (was commutative monoid?)
by wren ng thornton 25 Jun '11

25 Jun '11

On 6/25/11 12:00 PM, Jens Blanck wrote: >>> So there's a range of possible Monoid instances for each type, >> >> More for some types than for others. For Maybe there are three: >> >> * always take the first/left value; >> * always take the last/right value; >> * or, use a semigroup operation defined on the values. >> >> The first two options are provided by the First and Last newtypes, and the >> third option is provided by the instance for Maybe itself (except that it >> spuriously requires a Monoid instance instead of just a semigroup). > > But why does the Map instance of Monoid _not_ mimic the one chosen for > Maybe. I claim this causes unnecessary surprises for users (and lifting the > Monoid instance seems more useful, but that is harder to substantiate). For what it's worth, if people come to a decent enough consensus on which instance should be the default for Data.Map, then we should propose it on the libraries@ list. Of course we'll want to have Data.IntMap behave the same way, and consequently I'd update Data.Trie to follow suit. The various hashable and unordered containers will also probably want to follow suit. For Data.Trie, I only chose the version I did for conformity with IntMap. There's nothing especially interesting about the choice nor difficult about changing it (other than backwards compatibility issues). One issue that will come up, however, is that we'll want to generalize the First and Last newtypes so that they can be used consistently for all of different types which have these three Monoid instances. I'm not sure off hand where those newtypes are living these days, nor how much code it'd break to change them thus (and move them to base, if necessary). -- Live well, ~wren

1 0

commutative monoid?
by Evan Laforge 25 Jun '11

25 Jun '11

Not being especially mathematically inclined, every once and a while I get a little panicked when I notice that, e.g. Data.Map mappend is a plain left-biased union, and doesn't actually mappend the values of the map. Then I remember that monoids are associative, not commutative, and it's totally allowed to do that. Even if you mappend the values, the result is only as commutative as the monoid instance for the values. But clearly you can make that choice. For instance, Maybe's Monoid wants to mappend the elements. This is always a little disconcerting to me because the MonadPlus instance for Maybe doesn't do that. So there's a range of possible Monoid instances for each type, and maybe they were chosen by historical happenstance rather than some kind of "principle monoid" (is there such a thing?). Is there a name for the thing that's like a monoid, but the operator is commutative too? That would narrow down the implementation choices, e.g. Data.Map would have to combine the values. So it seems like if your operation is commutative, you can put it in "c-monoid" and not rely so much on the happenstance of the instances, since they are more constrained. And of course you are then free to reorder things, which is a nice bit of flexibility. So is there a typeclass for that? This article is about the mathematical concept. For the alien creatures in the Doctor Who adventure, see The Ark (Doctor Who). I guess I never saw that episode... but it sounds like they're closer to warm fuzzies than the slimy sleeping bag monster I imagined.

2 1

ANNOUNCE: Win32-junction-point-0.0.1
by Michael Steele 25 Jun '11

25 Jun '11

I'm pleased to announce the initial release of Win32-junction-point * hackage: http://hackage.haskell.org/package/Win32-junction-point * git repository: https://github.com/mikesteele81/Win32-junction-point This package provides the ability to manipulate NTFS junction points as supported by Windows 2000 and above. Junction points, along with NTFS hard links and NTFS symbolic links, are a type of symbolic link that can be made between folders existing on the same filesystem. Please read Microsoft KB205524 [1] for more information on junction points. Junction points have always been left undocumented in the Win32 SDK. The Windows 2000 Resource Kit came with a command-line utility named linkd.exe to work with them. Later, Mark Russinovich of SysInternals distributed a replacement utility named Junction [2] which accomplished the same thing. This source code is based on an article [3] and C++ library [4] written by Mike Nordell at codeproject.com. It is against Microsoft's recommendation to make use of undocumented API features. Use this library at your own risk. [1] http://support.microsoft.com/?kbid=205524 [2] http://technet.microsoft.com/en-us/sysinternals/bb896768 [3] http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=194 [4] http://www.codeproject.com/KB/winsdk/junctionpoints.aspx -- Michael Steele

1 0