- Haskell-Cafe - Haskell.org

Inverting a Monad
by Bas van Dijk 09 Feb '08

09 Feb '08

Hello, Is there a way to 'invert' an arbitrary Monad? By 'inverting' I mean to turn success into failure and failure into success. Here are some specific inversions of the Maybe and List Monad: invM :: Maybe a -> Maybe () invM Nothing = Just () invM (Just _) = Nothing invL :: [] a -> [] () invL [] = [()] invL (_:_) = [] How can I define this for an arbitrary Monad m? More specifically, I would like to define: inv :: (Monad m, M.MonadPlus m, ???) => m a -> m () inv m = if m fails then return () if m succeeds then fail The following obviously doesn't work: inv m = (m >> mzero) `mplus` return () because it will always return (). There's also a 'inversion' for natural numbers: invN :: Int -> Int invN 0 = 1 invN n = 0 but how can I define that without pattern matching, so only using arithmetic operations, +, -, *, ^, ...? The reason I ask this is that I'm writing a parser combinator library to understand parser a bit better. And I would like to define the combinator: notFollowedBy :: P t m a -> P t m () 'notFollowedBy p' fails when p succeeds and returns () when p fails. I will share the code when it's a bit more polished. Thanks, Bas

8 16

Internships at GHC HQ
by Simon Peyton-Jones 09 Feb '08

09 Feb '08

Would you be interested in working at Microsoft Research for three months? If so, you might want to think about applying for an internship. Simon and I are looking for interns, starting in summer 2008. Lots of background info here: http://hackage.haskell.org/trac/ghc/wiki/Internships including a bunch of possible projects, although you may also have ideas of your own. But the bottom line is - apply by end Feb 2008 for this round - tell one of us that you have done so (None of this is restricted to Haskell stuff. You can apply to work at any Microsoft Research lab, on any topic. But there are a lot of applicants, so you are more likely to be successful if you are fairly specific about who at MSR you'd like to work with and why, and contact that person to say that you've applied.) Simon

5 4

parsec3 pre-release [attempt 2]
by Derek Elkins 09 Feb '08

09 Feb '08

[Now with 100% more correct darcs get URLs.] I'm currently getting Paolo Martini's Google Summer of Code project, an updated version of Parsec, into a releasable state, and I will be maintaining it for at least a while. Paolo's major additions are: * The Parser monad has been generalized into a Parser monad transformer * The parsers have been generalized to work over a stream of any type, in particular, with bytestrings. I have made a few minor additions as well: * There is Haddock documentation for almost all functions * The Parser monad now has Applicative/Alternative instances Currently, I am looking for people to give it a go reporting any bugs in the library or documentation, troubles building it, or changes/features they would like. I'm also interested in performance information. Most old Parsec code should be relatively easy but not trivial to port. There is a darcs repository on code.haskell.org. If nothing comes up, I'll put a package on Hackage in about a week or so. To get the code: darcs get http://code.haskell.org/parsec3 To build it, the standard cabal commands should work: http://haskell.org/haskellwiki/Cabal/How_to_install_a_Cabal_package Alternatively, you can use the cabal-install application: http://hackage.haskell.org/trac/hackage/wiki/CabalInstall The documentation can be generated also via the normal cabal routine, or via cabal-install. The Text.Parsec modules should be preferred to the Text.ParserCombinators.Parsec modules.

5 11

ANN: Finance-Quote-Yahoo 0.5.0
by brad clawsie 09 Feb '08

09 Feb '08

a new version of Finance-Quote-Yahoo has been uploaded to hackage that breaks an api of the previous version for getting bulk historical quote information. specifically, notice this updated type signature: getHistoricalQuote :: QuoteSymbol -> Day -> Day -> QuoteFrequency -> IO (Maybe [HistoricalQuote]) the QuoteFrequency can be one of Daily, Weekly, Monthly or Dividend old code using this function will break, which is why i am notifying the list explicitly of this upload. since the versioning is still 0.* and the library is listed as experimental, users should expect changes until a 1.* version is released. brad

1 0

Slightly Offtopic in Part
by PR Stanley 09 Feb '08

09 Feb '08

Hi folks The disjunction elimination rule: I've been trying to make sense of it and I think I have had some success; however, it's far from adequate. I wonder, is there a way of demonstrating it in Haskell? A code frag with a jargon-free explanation would be mucho appreciated. Cheers, Paul

5 5

question concerning ANSI "void *"
by Galchin Vasili 08 Feb '08

08 Feb '08

Hello, Ok .. I am writing a Haskell function that will call down into the ANSI C library .. blah :: .... -> Ptr Word8 ....-> .... The underlying C function that "blah" is calling has a "void *" so I am using "Ptr Word 8" to model the "void *". I propose to have the callers of function "blah" to populate a data structure something like "Ptr Buz" where "data Buz = { ........} and then do a "recast :: Ptr Word 8 -> Ptr Buz" when invoking function "blah". Does this seem reasonable? Is there a better way? Thanks, Vasili

3 7

Fwd: [pdxfunc] pdxfunc meeting: Monday, February 11, 7pm, CubeSpace (Portland, OR)
by Justin Bailey 08 Feb '08

08 Feb '08

---------- Forwarded message ---------- From: Igal Koshevoy <igal(a)pragmaticraft.com> Date: Feb 8, 2008 12:01 PM Subject: [pdxfunc] pdxfunc meeting: Monday, February 11, 7pm, CubeSpace To: Igal Koshevoy <igal(a)pragmaticraft.com> Join us at the next meeting of pdxfunc, the Portland Functional Programming Study Group. We'll have presentations, demos and discussions. We welcome programmers interested in all functional languages and our meetings have content for coders of all skill levels. If interested, please also subscribe to our mailing list at http://groups.google.com/group/pdxfunc PRESENTATIONS (1) Kevin Scaldeferri: Effortless Concurrent Programming with Erlang Abstract: Erlang is a dynamic functional programming language designed for concurrent programming. After a quick introduction to the syntax and primitives, we'll dive into some code to see example of how you can easily write programs that take advantage of multiple CPUs, and that even scale effortlessly to clusters of machines. (You are highly encouraged to download and install Erlang from http://erlang.org/download.html before the meeting.) Speaker: Kevin Scaldeferri has spent the last 6 years building high-volume, high-reliability systems at Yahoo. His interests include programming languages, the interaction between online and real-life communities, and techniques for making the development process more reliable, more successful, and more fun. (2) Tim Chevalier: Towards a GraphicsMagick Binding for Haskell Abstract: I will discuss my work in progress on implementing a Haskell Foreign Function Interface (FFI) binding for the C-based GraphicsMagick image manipulation library. I will introduce portions of the FFI through examples, as well as tools for simplifying FFI use. I will also explain how I have begun to use Haskell's type system to develop a simplified yet equally powerful interface (as compared to the C version) to the GraphicsMagick library. Given the ongoing nature of my work, I will conclude by soliciting comments on what *you* would like to see in a Haskell image manipulation library. Speaker: Tim Chevalier is a PhD student at Portland State University, where he thinks about alternative back-ends for Haskell and languages like it. He has been programming in Haskell for seven years, the first six of which he spent trying to understand monads.

1 0

:i and :t give different types
by Chad Scherrer 08 Feb '08

08 Feb '08

Hello haskell-cafe, In ghci, I tried to get info for Data.Stream.Stream: $ ghci GHCi, version 6.8.2: http://www.haskell.org/ghc/ :? for help Loading package base ... linking ... done. Prelude> :m Data.Stream Prelude Data.Stream> :i Stream data Stream a where Stream :: forall a s. (Data.Stream.Unlifted s) => !s -> Step a s -> !s -> Stream a -- Defined in Data.Stream instance Functor Stream -- Defined in Data.Stream This didn't seem right to me, so I asked tried this: Prelude Data.Stream> :t Stream Stream :: (Data.Stream.Unlifted s) => (s -> Step a s) -> s -> Stream a What's going on here? forall a s. (Data.Stream.Unlifted s) => !s -> Step a s -> !s -> Stream a and (Data.Stream.Unlifted s) => (s -> Step a s) -> s -> Stream a are completely different, right? And really, neither one makes much sense to me. I would have expected forall s. (Data.Stream.Unlifted s) => (s -> Step a s) -> s -> Stream a -- Chad

5 7

User groups meeting all over the world
by Don Stewart 08 Feb '08

08 Feb '08

The community might be interested to know that there are (at least) 7 Haskell/FP user groups meeting across the world in the next two weeks! FringeDC Washington DC/USA February 9 PDXFunc Portland/USA February 11 Fun in the afternoon London/UK February 12 BayFP San Francisco/USA February 13 Saint-Petersburg Haskell User Group Saint-Petersburg/Russia. February 16 NYFP Network New York/USA February 19 NWFPIG: Seattle FP Group Seattle/USA February 20 The Austin (Texas) group met a couple of weeks ago. This is a great development -- a year ago I don't think we had *any* groups meeting regularly. Consider dropping in to one, if there's a meetting near you, or starting your own group! All groups we know about are listed here: http://www.haskell.org/haskellwiki/User_groups -- Don

5 4

Re: [Haskell-cafe] Mutable arrays
by John Lato 08 Feb '08

08 Feb '08

Ok, I've done some testing on different array accessing strategies, and at this point I believe that, as Stefan previously suggested, using an Oleg-inspired fold for access offers the best performance. My first non-unsafe idea was to try: > import Data.Array.MArray > import Data.Array.IO > import Data.Int (Int32) > import Data.List (foldl') > > -- |Create an array. Change the type signature to experiment with different array types. > makeAry :: IO (IOUArray Integer Float) > makeAry = newListArray (1,1000000) [1..] > getElemsLazy :: (MArray a e m, Ix i) => a i e -> m [e] > getElemsLazy myAry = getBounds myAry >>= > mapM (readArray myAry) . range this works on a 1 million element Int32 array (IOArray or IOUArray): > myElems <-getElemsLazy myAry > let myMax = foldl' max 0 myElems But with a 10-million element array, I get a stack overflow. I next tried the foldA functions Stefan posted, but had some problems with them. I think that the array elements need to be instances of Bounded and Fractional, and I don't know of a suitable type. Anyway, his code is a little too compact for me to understand without further study, so I moved on. Next I created my own fold operators. These are fairly directly copied from an email Oleg posted to the haskell mailing list: > leftFoldA' myArray self iteratee seed = do > elem <- readArray myArray $ fst seed > case iteratee seed elem of > Left seed -> return seed > Right seed -> self iteratee seed > > leftFoldA :: (MArray a e m, Ix a1) => a a1 e -> ((a1, b) -> e -> Either t (a1, b)) -> a1, b) -> m t > leftFoldA array iteratee seed = > let g = (leftFoldA' array) g in > g iteratee seed > > leftFoldModA' myArray self iteratee seed = do > elem <- readArray myArray $ fst seed > result <- iteratee seed elem > case result of > Left seed -> return seed > Right seed -> self iteratee seed > > leftFoldMA :: (MArray a e m, Ix a1) => a a1 e -> ((a1, b) -> e -> m (Either t (a1, b))) -> a1, b) -> m t > leftFoldMA array iteratee seed = > let g = (leftFoldModA' array) g in > g iteratee seed the two functions to use are leftFoldA and leftFoldMA. The difference, show in the type signature, is that the iteratee in leftFoldA is pure while the iteratee in leftFoldMA operates in the monad. So if you're going to modify the array, for example, you need to use the leftFoldMA version. These folds let me define: > findMax myAry = do > (lowB, highB) <- getBounds myAry > let maxReader (ix, acc) c = > let > ix' = ix + 1 > acc' = max c acc > in acc' `seq` (if ix' > highB then Left else Right) (ix', acc') > (_, myMax) <- leftFoldA myAry maxReader (lowB, 0) > return myMax > > normalizeArray myAry = do > myMax <- findMax myAry > (lowB, highB) <- getBounds myAry > let normMod = 1/myMax > let normalizer (ix, _) c = do > let ix' = ix + 1 > curVal <- readArray myAry ix > writeArray myAry ix (curVal * normMod) > return $ (if ix' > highB then Left else Right) (ix', ()) > leftFoldMA myAry normalizer (lowB, ()) > > -- |show all elements from lowB to highB > -- this only works with IO arrays, since the readArray and print happen in the same monad. > -- you could possibly make it work with ST arrays if you use a monad transformer, but you'd have > -- to change leftFoldMA as well. > showElems myAry lowB highB = do > let showFunc (ix, _) c = do > let ix' = ix + 1 > readArray myAry ix >>= print > return $ (if ix' > highB then Left else Right) (ix', ()) > leftFoldMA myAry showFunc (lowB, ()) There are probably better ways to define the folds, but I hope these are pretty easy to follow. If I was doing a lot of different operations, I'd probably define functions like > makeIteratee highB func = (\(ix, acc) c -> > let > ix' = ix + 1 > acc' = func c acc > in acc' `seq` (if ix' > highB then Left else Right) (ix', acc')) so that findMax becomes: > findMax2 myAry = do > (lowB, highB) <- getBounds myAry > (_, myMax) <- leftFoldA myAry (makeIteratee highB max) (lowB, 0) > return myMax instead of having to define a bunch of iteratees in let clauses. Now, running the program > main :: IO () > main = do > myAry <- makeAry > (lowB, highB) <- getBounds myAry > normalizeArray myAry > showElems myAry 1 10 > showElems myAry 999990 1000000 > return () takes about 5 seconds, with no optimizations. It takes less than a second with -O2. Much better. It does take longer with boxed arrays, but that's to be expected. No unsafe functions, either. The only sketchy bit is using seq in the iteratees (e.g. maxReader in findMax) to force the accumulator. I say sketchy not because it's unsafe or unreliable, but it would be nice if it was unnecessary. Notes: I used GHC 6.8.1 on WinXP, 3.2GHZ P4, 1.5GB RAM. All of my original tests were done without any optimizations, which is why I didn't include timing information for the earlier stuff. The getElemsLazy function is fast, but the stack overflow is annoying. Using the leftFold functions is both faster and avoids the space leak. I was also using the Data.List.Stream and Control.Monad.Stream versions of foldl' and mapM, although I don't think those made much difference. Anyway, this was a good exercise for me. I learned a lot, especially about the power of left-fold enumerators. Cheers, John

2 2