- Haskell-Cafe - Haskell.org

Optimizing array operation?
by Xiao-Yong Jin 05 Mar '09

05 Mar '09

Dear list, I decided to extract some common code I use in my data analysis code and end up with some interesting pattern. > -- | Confined array operation. The type Arr here is actually used as > -- a C-like array with index runs from 0 to n-1. > type Arr = Array Int > > -- | Element fetching function, no bounds checking. Works with array > -- with index [0..n-1] > (!>) :: Arr e -> Int -> e > (!>) = unsafeAt > {-# INLINE (!>) #-} > > -- | Length of the array. > arrLength :: Arr e -> Int > arrLength = numElements > {-# INLINE arrLength #-} > > -- | Sequentially loop over all elements in an array. > loopArrM :: (Monad m) => > (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrM = loopArrMp (\ _ -> True) > {-# INLINE loopArrM #-} > > -- | Same as loopArrM but only to those with index satisfies predicate. > loopArrMp :: (Monad m) => > (Int -> Bool) -- ^ predicate > -> (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrMp p f arr = loopArrMG 0 end p f arr > where > end = arrLength arr > {-# INLINE loopArrMp #-} > > -- | Same as loopArrM but only to indices within a range. > loopArrMr :: (Monad m) => > Int -- ^ start index > -> Int -- ^ end index > -> (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrMr start end = loopArrMG start end (\ _ -> True) > {-# INLINE loopArrMr #-} > > -- | Generic loopArrM for indices with in a range [start, end-1] and > -- satisfy predicate. > loopArrMG :: (Monad m) => > Int -- ^ start index > -> Int -- ^ end index > -> (Int -> Bool) -- ^ predicate > -> (e -> m a) -- ^ function to apply to elements > -> Arr e -- ^ the array > -> m () > loopArrMG start end p f arr = go start > where > go !j | j == end = return () > | p j = f (arr !> j) >> go (j + 1) > | otherwise = go (j + 1) > {-# INLINE loopArrMG #-} It is quite frequently to loop over Arr with various conditions, so I wrote loopArrMG to do it. I know a list comprehension would just do the trick, but the extra time and heap allocation is not what I want. My question here is that whether there is a better data structure available to accomplish such task? If not, is there a better way to write the above code? Thanks, Xiao-Yong -- c/* __o/* <\ * (__ */\ <

1 0

(no subject)
by R J 05 Mar '09

05 Mar '09

Could someone provide an elegant solution to Bird problem 4.2.13? Here are the problem and my inelegant solution: Problem ------- Since concatenation seems such a basic operation on lists, we can try to construct a data type that captures concatenation as a primitive. For example, data (CatList a) = CatNil | Wrap a | Cat (CatList a) (CatList a) The intention is that CatNil represents [], Wrap x represents [x], and Cat x y represents x ++ y. However, since "++" is associative, the expressions "Cat xs (Cat ys zs)" and "Cat (Cat xs ys) zs" should be regarded as equal. Define appropriate instances of "Eq" and "Ord" for "CatList". Inelegant Solution ------------------ The following solution works: instance (Eq a) => Eq (CatList a) where CatNil == CatNil = True CatNil == Wrap z = False CatNil == Cat z w = ( z == CatNil && w == CatNil ) Wrap x == CatNil = False Wrap x == Wrap z = x == z Wrap x == Cat z w = ( Wrap x == z && w == CatNil ) || ( Wrap x == w && z == CatNil ) Cat x y == CatNil = x == CatNil && y == CatNil Cat x y == Wrap z = ( x == Wrap z && y == CatNil ) || ( x == CatNil && y == Wrap z ) Cat x y == Cat z w = unwrap (Cat x y) == unwrap (Cat z w) unwrap :: CatList a -> [a] unwrap CatNil = [] unwrap (Wrap x) = [x] unwrap (Cat x y) = unwrap x ++ unwrap y instance (Eq a, Ord a) => Ord (CatList a) where x < y = unwrap x < unwrap y This solution correctly recognizes the equality of the following, including nested lists(represented, for example, by Wrap (Wrap 1), which corresponds to [[1]]): Wrap 1 == Cat (Wrap 1) CatNil Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) == Cat (Wrap 1) (Cat (Wrap 2) (Wrap 3)) Wrap (Wrap 1) == Wrap (Cat (Wrap 1) CatNil) Although this solution works, it's a hack, because unwrap converts CatLists to lists. The question clearly seeks a pure solution that does not rely on Haskell's built-in lists. What's the pure solution that uses cases and recursion on CatList, not Haskell's built-in lists, to capture the equality of nested CatLists? _________________________________________________________________ Windows Live™: Life without walls. http://windowslive.com/explore?ocid=TXT_TAGLM_WL_allup_1a_explore_032009

2 1

Optimization by cafe
by ChrisK 04 Mar '09

04 Mar '09

I have a performance glitch in regex-tdfa related to GHC-6.10.1 (on a PPC G4 with -O2). I have okay code that runs in 0.2 seconds. I simplify this code to run faster and it takes 4.0 seconds (it allocates something in the loop, I think) I turn on -prof for the simpler code and it runs in 0.25 seconds. I can't profile my way out of it, due to above paradox. Has anyone else seen this sort of paradox? The simpler code's loop is just a bunch of pattern matching and lookups, multi: > matchTest :: Regex -> S.ByteString -> Bool > matchTest !r !input = ... > > multi (Simple' {dt_win=w,dt_trans=CharMap t, dt_other=o}) !off = > if IMap.null w > then if off > endOff > then False > else case IMap.findWithDefault o (fromEnum (input `S.unsafeIndex` off)) t of > Transition {trans_many=DFA {d_dt=dt'}} -> > multi dt' (succ off) > else True All the above regex search does is look for a match. It is a tester, returning Bool. The "w" is checked for winning, if it wins it returns True. If not winning, the offset is checked against the end (cached in endOff). If the end has been reach it returns False. Otherwise it looks up the Word8 at offset "off" in "input" , looks up this Word8 as an Int in the t::IntMap Transition , defaulting to Transition "o" The next DT is followed with the (succ off), note that !off is strict. I cannot think of how to reduce the code any further. It should not be doing any allocation. The Regex is being compiled once, cached, and run 10^6 times against a short piece of text. I know it can run fast because I have huge module running in ST.Strict that does all kinds of extra computation and runs in 0.2 seconds. It should be possible to cut this down and win. So I also applied my delete key to most of the code in the complicated ST.Strict module, keeping the runST. The end result was not unlike the above code, and ran in 4.0 seconds instead of 0.2 seconds. I have looked hard at the core output. I am at a loss. So I have turned to haskell-cafe for insight and moral support. -- Chris

1 0

environment variables for runghc?
by Erik de Castro Lopo 04 Mar '09

04 Mar '09

Hi all, Is there some environment variable I can set so that runghc can be told to always use -Wall? Cheers, Erik -- ----------------------------------------------------------------- Erik de Castro Lopo ----------------------------------------------------------------- "... a discussion of C++'s strengths and flaws always sounds like an argument about whether one should face north or east when one is sacrificing one's goat to the rain god." -- Thant Tessman

3 4

Re: Left fold enumerator - a real pearl overlooked?
by John Lato 04 Mar '09

04 Mar '09

Hello Günther, I think the largest reason Haskellers don't use left-fold enumerators is that there isn't a ready-to-use package on Hackage. Oleg's code is extremely well commented and easy to follow, but it's not cabalized. In addition to Takusen, Johan Tibbe's hyena application server uses enumerators for IO: http://github.com/tibbe/hyena/tree/master There is a darcs repo of a cabalized iteratee package available at http://inmachina.net/~jwlato/haskell/iteratee/ This is essentially Oleg's code, slightly modified and reorganized. If anyone is interested in using left-fold enumerators for IO, please give it a look and let me know what you think. I'd like to put this on hackage in about a week or so, if possible. I would especially appreciate build reports. There are a few iteratee/enumerator design questions that remain, which Oleg and others would like to explore more fully. The results of that research will likely find there way into this library. Sincerely, John Lato > Hi all, > > in the last few months I was looking for haskell database library, > eventually settling for HDBC (thanks John btw). > > Takusen also caught my eye although I even failed installing it. > > Nevertheless a particular property of takusen, left-fold-enumerator, > also sparked my interest and I tried to follow it up. > > I had the impression this is something of relevance but something that > is not mentioned or made use of often. There are actually only a few > references on the net and most of those by one person only, Oleg. > > There was one post from John Goerzen about Haskell HTTP libraries in > which he hinted using left-fold enumerators. > > Anyway what I'm saying is that the whole topic is somewhat off the radar > of the larger haskell community, how come, or am I merely overestimating > its relevance and usefulness? > > Günther

12 19

*almost* composition in writer monad
by Edsko de Vries 04 Mar '09

04 Mar '09

Hi, Does this function remind anybody of anything? It seems like I'm missing an obvious abstraction: composeWriter :: [a -> (a, b)] -> a -> (a, [b]) composeWriter [] a = (a, []) composeWriter (f:fs) a = let (a', b) = f a (final_a, bs) = composeWriter fs a' in (final_a, b:bs) It's almost but not quite composition for functions in the Writer monad; the difference is that every function has exactly one b result, rather than a list of them. Edsko

2 2

Stacking State on State.....
by Phil 04 Mar '09

04 Mar '09

Hi, I¹ve been teaching myself Monads recently with some success, but I¹ve hit a snag when I tried to look at transformers. I¹m not sure if the problem is my understanding of transformer use at a theoretical level or if I¹m just getting the syntax wrong. If I stick a (hopefully) fairly simple example below, I was wondering if people could comment: Bit of background I have no problem using the State Monad and find it very useful for holding the state or say a homemade random number generator. I written several little bits of code like this: VanDerCorput :: Int-> ( Double, Int ) VanDerCorput state = ( output, state+1 ) where output = reflect state getVanDC :: State Int Double getVanFC = State VanDerCorput This is just holding an incremental state and each time it is evaluated the next number in the Van Der Corput sequence in generated this is just a quasi random sequence the implementation details of the sequence are irrelevant safe to say that the sequence is generated from N=1,2,3,4.....Infinity. The above example is so trivial it can of course be implemented easily in purely functional code by threading the state as a parameter to a pure function and then mapping that function to an ³iterate (+1) 1² statement, but that is not the point of the exercise! The next step of the program is to wrap the above example up in another function which takes the Van Der Corput sequence as input and provides output depending on*it¹s own* state. I¹m passing it to a Box-Muller transform. Very quickly the Box-Muller transform requires TWO inputs from VanDerCourput to produce TWO outputs itself, however we only ever need one at a time, so the Box-Muller transform itself must hold state saying weather it has already saved the 2nd output from a previous call, and thus doesn¹t need to call Van Der Corput this time to produce output it just returns its own state. (P.S. If you know what I¹m doing from a maths point of view please ignore the fact using a 1D Van Der Corput with Box Muller is a very bad idea I know this; I¹m keeping the example simple and Haskell orientated!) In C-like imperative code you¹d could do something like the below not that this is massively elegant, but it shows the case-in-point: Boxmuller() { // The ³outer² states of Box Muller static bool myState = False; static double storedNormal = 0.; // Local copy of current state bool currentState = myState; // State always flips each run myState = not myState; // If we don¹t have a stored value from a previous run if currentState == False { // Generate two new Van Der Corputs this would increment a state in getNextVanDerCorput() twice producing different output each time double rand1 = getNextVanDerCorput(); double rand2 = getNextVanDerCorput(); // Store one result for the NEXT run of Boxmuller() storedNormal = SOME_TRANSFORM(rand2); // Return the other return SOME_TRANSFORM(rand1); } // We have a leftover value from a previous run get a local copy double currentNormal = storedNormal; // Reset the stored value to zero storedNormal = 0.; // Return the local copy of the stored value return currentNormal; } getNextVanDerCorput() { // Starting state state int n = 1; int currentState = n; // Incremented each time we call the function ++n; // Value computed on the internal state of this function return SOME_OTHER_TRANSFORM(currentState); } Right, hopefully that explains explicitly what I¹m trying to do apologies for dropping into C, it¹s easier to explain in code than in words. It struck me that this could be done using a plain and simple State Monad in Haskell carrying ALL states for both functions around in a tuple. This is pretty ugly tho, and I figure both BoxMuller and VanDerCorput should have their own internal states so they can be used as building blocks in other functionality too so one big ugly Monad is bad code design, even if it would work for this specific example. Let¹s not go there. The VanDerCorput building block is just the Monad at the start of this post. The problem is HOW DO I WRAP ANOTHER INDEPENDENT STATE AROUND THIS? After some googling it looked like the answer may be Monad Transformers. Specifically we could add a StateT transform for our Box Muller state to our VanDerCorput State Monad. Google didn¹t yield a direct answer here so I¹m not even sure if my thinking is correct, people describe the process of using a transform as wrapping one monad in another¹ or threading one monad into another¹. What we want to do is have some internal state controlled by an independent outer state - this sounds about right to me? So I started playing around with the code, and got the below to compile. test :: StateT (Bool,Double) (State Int) Double test = do (isStored,normal) <- get let (retNorm,storeNorm) = if isStored then (normal,0) else (n1,n2) where n1 = 2 n2 = 3 put (not isStored, storeNorm) return retNorm Now this is incomplete and may be even wrong! I¹ll Explain my thinking: (Bool,Double) is equivalent to myState and storedNormal in the C example The last Double is the return value of the BoxMuller Monad The (State Int) is supposed to represent the VanDerCorput monad but the compiler (GHC 6.10) will only let me specify one parameter with it so I¹ve put the state and left the return type to the gods!!.... As I said this isn¹t quite right any ideas how to specify the type? The next few lines get and test the BoxMuller state, this seems to work OK to me, the problem is when I try to look at the STATE OF THE INTERNAL monad. n1 and n2 should evaluate and increment the state of VanDerCorput monad but I can¹t get anything to compile here. 2 and 3 are just dummy values to make the thing compile so I could debug. My last gripe is how to actually call this from a pure function do I need to use both evalStateT and evalState I can¹t see how to initialize both the inner and outer state ? OK I think that¹s more than enough typing, apologies for the war&peace sized post. Any help muchly muchly appreciated, Many Thanks, Phil.

4 17

OpenVG: Linker errors with ghc --make, but not with ghci?
by Peter Verswyvelen 04 Mar '09

04 Mar '09

I followed the instructions on how to build OpenVG on Windows. It works fine when I run the examples using "GHCi -lopenvg32", but when compiling it with "GHC --make -lopenvg32" I get a bunch of linker errors, like C:\Program Files\Haskell\OpenVG-0.1\ghc-6.10.1/libHSOpenVG-0.1.a(Paths.o):fake:(.text+0x82): undefined reference to `vgInterpolatePath' C:\Program Files\Haskell\OpenVG-0.1\ghc-6.10.1/libHSOpenVG-0.1.a(Paths.o):fake:(.text+0x40d): undefined reference to `vgModifyPathCoords' etc However it does seem that the libopenvg32.a file contains all these undefined references, and it is in the gcc-lib directory of GHC. I'm a stuck. Any hints? Thanks, Peter

2 2

Data.Binary stack overflow with Data.Sequence String
by Gwern Branwen 04 Mar '09

04 Mar '09

So recently I've been having issues with Data.Binary & Data.Sequence; I serialize a 'Seq String' You can see the file here: http://code.haskell.org/yi/Yi/IReader.hs The relevant function seems to be: -- | Read in database from 'dbLocation' and then parse it into an 'ArticleDB'. readDB :: YiM ArticleDB readDB = io $ (dbLocation >>= r) `catch` (\_ -> return empty) where r x = fmap (decode . BL.fromChunks . return) $ B.readFile x -- We read in with strict bytestrings to guarantee the file is closed, -- and then we convert it to the lazy bytestring data.binary expects. -- This is inefficient, but alas... My current serialized file is about 9.4M. I originally thought that the issue might be the recent upgrade in Yi to binary 0.5, but I unpulled patches back to past that, and the problem still manifested. Whenever yi tries to read the articles.db file, it stack overflows. It actually stack-overflowed on even smaller files, but I managed to bump the size upwards, it seems, by the strict-Bytestring trick. Unfortunately, my personal file has since passed whatever that limit was. I've read carefully the previous threads on Data.Binary and Data.Map stack-overflows, but none of them seem to help; hacking some $!s or seqs into readDB seems to make no difference, and Seq is supposed to be a strict datastructure already! Doing things in GHCi has been tedious, and hasn't enlightened me much: sometimes things overflow and sometimes they don't. It's all very frustrating and I'm seriously considering going back to using the original read/show code unless anyone knows how to fix this - that approach may be many times slower, but I know it will work. -- gwern

2 1

Status of Haskell under OsX
by Cristiano Paris 04 Mar '09

04 Mar '09

Hi, I'm planning to purchase a MacBookPro so I'm wondering how well Haskell is supported under this platform. Thanks, Cristiano

10 16