June 2010 - Haskell-Cafe

MonadCatchIO and bracket.
by Carl Howells 28 Jun '10

28 Jun '10

While working this weekend on the Snap web framework, I ran into a problem. Snap implements MonadCatchIO, so I thought I could just use bracket to handle resource acquisition/release in a safe manner. Imagine my surprise when bracket simply failed to run the release action sometimes. I quickly determined the times when it doesn't run are when Snap's monadic short-circuiting is used. I dug into the source of bracket (in the transformers branch, though the mtl branch has the same behavior in these cases, with slightly different code), and the reason why quickly became obvious: -- | Generalized version of 'E.bracket' bracket :: MonadCatchIO m => m a -> (a -> m b) -> (a -> m c) -> m c bracket before after thing = block $ do a <- before r <- unblock (thing a) `onException` after a _ <- after a return r When monadic short-circuiting applies, the "_ <- after a" line gets completely ignored. In discussions with #haskell on this topic, it quickly became clear that for any monad transformer that can affect control flow, the definition of bracket in MonadCatchIO doesn't keep the guarantee provided by bracket in Control.Exception, which is that the "after" action will be run exactly once. Because of that, I think bracket needs to be a class function. Furthermore, I think it needs to be a new class, ie class MonadCatchIO m => MonadBracketIO m where bracket :: m a -> (a -> m b) -> (a -> m c) -> m c This would allow its definition in cases where it makes sense (Snap or MaybeT IO), but it could be left out in cases where it doesn't make sense, like ListT IO, even though MonadCatchIO makes sense there. Carl Howells

4 3

Physical equality
by José Romildo Malaquias 28 Jun '10

28 Jun '10

Is there in Haskell a non monadic function of type a -> a -> Bool which test for physical equality of two values? It would return True if only if both values are the same object in memory. For instance: value1 = "good" value2 = "good" eq value1 value2 => False value1 = "good" value2 = value1 eq value1 value2 => True Romildo

5 4

Space leak with unsafePerformIO
by Henning Thielemann 28 Jun '10

28 Jun '10

Attached is a program with a space leak that I do not understand. I have coded a simple 'map' function, once using unsafePerformIO and once without. UnsafePerformIO has a space leak in some circumstances. In the main program I demonstrate cases with and without space leak. Without space leak the program writes a file to the disk until it is full. Any idea? The original problem is a function that is compiled by LLVM and shall be applied to a list in a mapAccumL manner.

2 3

Construction of short vectors
by Alexey Khudyakov 28 Jun '10

28 Jun '10

Hello, cafe I have question about vector package. Currently I'm playing with data types which are isomorphic to vectors of fixed length. Think about vector in N-dimensional space, list of parameters to function R^n → R, set of measurements with uncertainties, etc. They have different semantics but exactly the same representation and it's often advantageous to think about them as N-dimensional vectors. Then constructor like one below arise naturally. And I don't know how to write them properly. It's possible to use fromList but then list could be allocated which is obviously wasteful. > vector2 :: Double -> Double -> Vec2D > vector2 x y = ... > -- Vec2D is some wrapper around Vector data type Another question is there any specific problems with short vectors? They could be just 2 elements long. I mean performance problems

5 8

Why this doesn't type checked
by Victor Nazarov 28 Jun '10

28 Jun '10

I've allways found code like > -- maxBound (undefined :: Int) a bit strange as any usage of undefined is. Being Ruby on Rails developer I've personally found that one of the main Rails motos is being as readable as possible. Code must be as close to english as possible. Embeded DSLs like rspec are made mostly to made specs as close to english as possible. Having this in my mind I've decided that this code should be rewritten without undefined being mentioned. But I need some type signature and it should mention Int type. So I've got an idea about what I've called "fantom type functions". So wee need type families for it to work. > {-# LANGUAGE TypeFamilies #-} > module Main where > > import Data.Word I want the code I've mentioned to be rewrited as something like > -- maxBound :: MaxBoundOf Int As it is much more readable: "I want maxBound with the type of MaxBound Of Int". So here is the implementation of class Sizeable that implements sizeof operation. Which is type-indexed like maxBound is. sizeof returns number of bytes that occupy type when serialized to some binary stream. > class Sizeable sizeable > where type Sizeof sizeable > sizeof :: Sizeof sizeable We should like to make a default type but GHC still doesn't support it. > -- type Sizeof sizeable = Int Instances for all basic types > instance Sizeable Int > where sizeof = 4 Even without defaults we get type safety in these instances > type Sizeof Int = Int > instance Sizeable Word8 > where sizeof = 1 > type Sizeof Word8 = Int > > instance Sizeable Word16 > where sizeof = 2 > type Sizeof Word16 = Int > > instance Sizeable Word32 > where sizeof = 4 > type Sizeof Word32 = Int > > instance Sizeable Word64 > where sizeof = 8 > type Sizeof Word64 = Int The annoyance is the need to instantiate Sizeof type family every time. It will disappear once associated types' defaults will be implemented in GHC. What we get with this instances is following code. > main = > do print (sizeof :: Sizeof Word16) Let's try it. $ runhaskell this.lhs this.lhs:78:14: Couldn't match expected type `Int' against inferred type `Sizeof sizeable' NB: `Sizeof' is a type function, and may not be injective In the first argument of `print', namely `(sizeof :: Sizeof Word16)' In the expression: print (sizeof :: Sizeof Word16) In the expression: do { print (sizeof :: Sizeof Word16) } What can I do with this code to make it type-check? -- Victor Nazarov

5 5

building a patched ghc
by braver 28 Jun '10

28 Jun '10

How do I get the latest 6.12 source and cherry-pick selected patches from the trunk, e.g. Simon's GC fixes? The wiki says that you get the head with darcs get --lazy http://darcs.haskell.org/ghc and the 6.12 with darcs get --lazy http://darcs.haskell.org/ghc-6.12/ghc Since the trunk is big enough, I wonder if 6.12 a subset of it and can be obtained from it? The tags are not informative. If I get the branch, how will I be able to get the patches from the head, once they're separate repos? -- Alexy

2 2

The mother of all functors/monads/categories
by Max Bolingbroke 27 Jun '10

27 Jun '10

I'm wondering if someone can cast some light on a pattern I've come across, which I'm calling the "mother of all X" pattern after Dan Piponi's blog post (http://blog.sigfpe.com/2008/12/mother-of-all-monads.html) Edward Kmett has also explored these ideas here: http://www.mail-archive.com/haskell-cafe@haskell.org/msg57738.html Preliminaries === Q: What is the "mother of all X", where X is some type class? A: It is a data type D such that: 1. There exist total functions: > lift :: X d => d a -> D a > lower :: X d => D a -> d a 2. And you can write a valid instance: > instance X D With *no superclass constraints*. 3. (We may also add the constraint that D is somehow the "smallest such" data type, but I don't know in exactly what sense I mean this). So the "mother of all X" is a data type that somehow encodes all of the functions that the X type class gives you. An example is in order! Example 1: Yoneda is the mother of all Functors === The code in this example and the next one is shamelessly stolen from the category-extras package (thanks Edward!). Here is the data type: > -- flip fmap :: forall a. f a -> (forall b. (a -> b) -> f b) > newtype Yoneda f a = Yoneda { runYoneda :: forall b. (a -> b) -> f b } And the injections. As it turns out, we don't need the Functor constraint on the lowerYoneda call: > liftYoneda :: Functor f => f a -> Yoneda f a > liftYoneda f = Yoneda (flip fmap f) > > lowerYoneda :: Yoneda f a -> f a > lowerYoneda f = runYoneda f id Finally, we can write the Functor instance. Notice that we don't need to make use of the Functor instance for f: all of the methods of Functor f have been somehow encoded into the Yoneda data type! > instance Functor (Yoneda f) where > fmap f m = Yoneda (\k -> runYoneda m (k . f)) Note that we can also write an instance (Y f => Y (Yoneda f)) for any Functor subclass Y. But (Yoneda f) is not the mother of all Y, because we will need the Y f constraint to do so. Here is an example: > instance Applicative f => Applicative (Yoneda f) where > pure = liftYoneda . pure > mf <*> mx = liftYoneda (lowerYoneda mf <*> lowerYoneda mx) Why is (Yoneda f) interesting? Because if I take some expression whose type is quantified over any superclass of Functor, and we want to run it with Functor instantiated to some F, if we instead run it with Functor instantiated to (Yoneda f) and then use lowerYoneda, we will automatically get guaranteed fmap fusion. Example 2: Codensity is the mother of all Monads === Data type: > -- (>>=) :: forall a. m a -> (forall b. (a -> m b) -> m b) > newtype Codensity m a = Codensity { runCodensity :: forall b. (a -> m b) -> m b } Isomorphism. We need Monad constraints on both ends now: > liftCodensity :: Monad m => m a -> Codensity m a > liftCodensity m = Codensity ((>>=) m) > > lowerCodensity :: Monad m => Codensity m a -> m a > lowerCodensity m = runCodensity m return Instances: > instance Functor (Codensity f) where > fmap f m = Codensity (\k -> runCodensity m (k . f)) > > instance Applicative (Codensity f) where > pure x = Codensity (\k -> k x) > mf <*> mx = Codensity (\k -> runCodensity mf (\f -> runCodensity mx (\x -> k (f x)))) > > instance Monad (Codensity f) where > return = pure > m >>= k = Codensity (\c -> runCodensity m (\a -> runCodensity (k a) c)) Again, using (Codensity m) where you used m before can yield a performance improvement, notably in the case of free monads. See http://haskell.org/haskellwiki/Performance/Monads or http://wwwtcs.inf.tu-dresden.de/~voigt/mpc08.pdf. Example 3: Wotsit is the mother of all Categories === I don't actually know what the right name for this data type is, I just invented it and it seems to work: > -- (>>>) :: forall a b. t a b -> (forall c. t b c -> t a c) > newtype Wotsit t a b = Wotsit { runWotsit :: forall c. t b c -> t a c } Isomorphism: > liftWotsit :: Category t => t a b -> Wotsit t a b > liftWotsit t = Wotsit ((>>>) t) > > lowerWotsit :: Category t => Wotsit t a b -> t a b > lowerWotsit t = runWotsit t id And finally the instance: > instance Category (Wotsit t) where > id = Wotsit id > t1 . t2 = Wotsit (runWotsit t2 . runWotsit t1) This is *strongly* reminiscent of normalisation-by-evaluation for monoids (reassociation realised by assocativity of function application), which is not surprising because Category is just a monoid. There is probably some connection between NBE and Yoneda (e.g. "Normalization and the Yoneda embedding", but I can't get access to this paper electronically). Conclusion === So I have a lot of questions about this stuff: 1. Is there a way to mechanically derive the "mother of all X" from the signature of X? Are these all instances of a single categorical framework? 2. Is there a mother of all idioms? By analogy with the previous three examples, I tried this: > -- (<**>) :: forall a. i a -> (forall b. i (a -> b) -> i b) > newtype Thingy i a = Thingy { runThingy :: forall b. i (a -> b) -> i b } But I can't see how to write either pure or <*> with that data type. This version seems to work slightly better: > newtype Thingy i a = Thingy { runThingy :: forall b. Yoneda i (a -> b) -> i b } Because you can write pure (pure x = Thingy (\k -> lowerYoneda (fmap ($ x) k))). But <*> still eludes me! 3. Since (Codensity m) enforces >>= associativity, perhaps it can be used to define correct-by-construction monads in the style of operational or MonadPrompt? Any insight offered would be much appreciated :-) Cheers, Max

8 17

ANN: bitspeak 0.0.1
by Maurício CA 27 Jun '10

27 Jun '10

Hi, all, bitspeak is a small proof of concept application that allows writing text using only two commands (yes/no, 1/2, top/down etc.). It is intended to show how people with disabilities similar to Stephen Hawking's (i.e., good cognitive hability, but very few movements) can write text. http://hackage.haskell.org/package/bitspeak http://bitbucket.org/mauricio/bitspeak/wiki/Home Best, Maurício

15 19

A little jewel on sigfpe's blog
by Günther Schmidt 27 Jun '10

27 Jun '10

Hello, I just discovered this little jewel on Dan Piponi's blog. http://blog.sigfpe.com/2010/03/partial-ordering-of-some-category.html I'm just posting the link so that it doesn't get overlooked, would be a real shame. Günther

1 0

Core packages and locale support
by Roman Cheplyaka 27 Jun '10

27 Jun '10

While ghc 6.12 finally has proper locale support, core packages (such as unix) still use withCString and therefore work incorrectly when argument (e.g. file path) is not ASCII. Is someone already working on this? If it's just a matter of time and manpower I can help but I need some guidance from authority. -- Roman I. Cheplyaka :: http://ro-che.info/ "Don't let school get in the way of your education." - Mark Twain

7 36