- Haskell-Cafe - Haskell.org

Relating functors in Category Theory to Functor
by David Menendez 02 Jul '04

02 Jul '04

Until recently, I've had difficulty relating the concept of a "functor" from Category Theory to the class Functor in Haskell. I've figured out a relationship that seems to make sense, but I wanted to check with the list to make sure I'm not on the wrong track. In Category Theory, a functor F between categories C and D has two parts: (1) a mapping F[ob] from the objects of C to the objects of D (2) a mapping F[mor] from the morphisms of C to the morphisms of D For any morphism f: a -> b in C, there is a morphism F(f): F(a) -> F(b) in D. For two morphisms f and g in C, F(f . g) = F(f) . F(g) in D. We can interpret Haskell as a category with types as objects and functions as morphisms. For example, isDigit :: Char -> Bool. So, for some Functor f, the type constructor f corresponds to F[ob], and fmap to F[mor]. For any function g :: a -> b, fmap g :: f a -> f b, and fmap (g . h) = fmap g . fmap h. -- For two functors F, G: C -> D, there is a natural transformation tau from F to G, if for every object a in C, there is morphism tau[a]: F(a) -> G(a) in D. In Haskell, natural transformations are polymorphic functions, tau :: f a -> g a. For example, maybeToList :: Maybe a -> [a]. -- A monad is a functor, F: C -> C, plus two natural transformations mu: F^2 -> F and eta: I -> F (I being the identity functor for C). In Haskell, F[ob] becomes the type constructor, F[mor] becomes fmap (or liftM), mu becomes join :: f (f a) -> f a, and eta becomes return :: a -> f a. So, am I on the right track here? -- David Menendez <zednenem(a)psualum.com> <http://www.eyrie.org/~zednenem/>

5 6

readMVar and the devils
by Conor T McBride 02 Jul '04

02 Jul '04

Hi folks I'm having a play with Concurrent Haskell, and came across this in the library. readMVar :: MVar a -> IO a This is a combination of takeMVar and putMVar; ie. it takes the value from the MVar, puts it back, and also returns it. I was just wondering if I understand things correctly. Suppose myMVar is nonempty and I have one thread executing do x <- takeMVar myMVar -- (A) putMVar myMVar x -- (B) return x and another executing putMVar myMVar y -- (C) Questions (1) Is it possible that an evil scheduler will execute (A) then (C) and block on (B)? (2) Is it the case that if myMVar is nonempty and readMVar is chosen for execution, that readMVar myMVar takes the value from myMVar, guaranteed that the _same_ value will be put back immediately, and also returned? (3) If yes to both, what combination of takeMVar and putMVar manages to maintain the lock in between the two? I'm only asking, because I'm trying to cook up some kind of partial evaluator for programs which are being simultaneously edited by fiercely argumentative devils. Kind of `demonic laziness', where the computations decide when _they_ feel like running (eg sometime after the program turns up), rather than the `angelic laziness' we're used to. I'd like to use MVars in a write-once-read-many style, so that once someone fills in a bit of program, it stays put. I'd hate for another devil to sneak in a replacement program just in the twinkling of an eye between taking something out to read and putting it back to be read again. I guess I could use some kind of extra semaphore MVar to ensure that the reader has the lock on the program MVar, but that's more like hard work. Is readMVar what I want? Another more general question would be `is this an utterly stupid thing to do in practice?'. I mean, just consider an evaluator for some simple language (eg arithmetic expressions), implemented by forking a thread for every subcomputation, and using MVars to transmit the values. Is that diabolically slow compared to a normal evaluator? I guess I'll try it, but I was wondering if anyone had any useful experience to share? Cheers Conor

2 1

some newbie FFI questions
by John Kozak 01 Jul '04

01 Jul '04

I'm trying to experiment with image processing in haskell (with which I haven't much experience). I've written some FFI code to talk to the ImageMagick library which provokes a few questions (environment is ghc 6.2.1 on debian): 1. Speed: I'm reading in a 2000x1500 pixel image, and have defined a Pixel type like this: data Pixel a = Pixel !a !a !a deriving Show I use ImageMagick to load the image, then build an Array of Pixel Floats. Building the array takes 45 seconds on a 2.5Ghz P4 with code compiled -O2, which seems slow to me - are my expectations unrealistic? I've tried various UNPACK things which didn't make much difference. 2. How do I convert a CFloat into a Float? 3. I get the wrong answer ;-) I expect the C and haskell code below to produce the same pixel data, but they don't (the C code is right). C code: #include <stdio.h> #include <wand/magick_wand.h> int main(int argc,char *argv[]) { MagickWand *wand = NewMagickWand(); int width,height; float *pixels; int i,j; if (argc!=2) { fprintf(stderr,"bad args\n"); exit(100); } if (!MagickReadImage(wand,argv[1])) { fprintf(stderr,"can't read file\n"); exit(1); } height = MagickGetImageHeight(wand); width = MagickGetImageWidth(wand); printf("dimension: %dx%d\n",width,height); pixels = (float*) malloc(3*width*height*sizeof(float)); if (!MagickGetImagePixels(wand,0,0,width,height,"RGB",FloatPixel,(unsigned char*) pixels)) { fprintf(stderr,"can't get pixels\n"); exit(1); } printf("%f %f %f\n",pixels[0],pixels[1],pixels[2]); printf("%f %f %f\n",pixels[4],pixels[5],pixels[6]); printf("%f %f %f\n",pixels[7],pixels[8],pixels[9]); } haskell code: -- requires flags: -fffi -fglasgow-exts import Foreign import Foreign.C import MarshalArray import Char import List import Array import Bits data Pixel a = Pixel !a !a !a deriving Show data MagickWand -- opaque foreign import ccall "wand/magick_wand.h NewMagickWand" newMagickWand :: IO (Ptr MagickWand) foreign import ccall "wand/magick_wand.h DestroyMagickWand" destroyMagickWand :: (Ptr MagickWand) -> IO () foreign import ccall "wand/magick_wand.h MagickSetFilename" setFilename :: Ptr MagickWand -> CString -> IO () foreign import ccall "wand/magick_wand.h MagickReadImage" readImage :: Ptr MagickWand -> CString -> IO CInt foreign import ccall "wand/magick_wand.h MagickGetImageWidth" getWidth :: Ptr MagickWand -> CULong foreign import ccall "wand/magick_wand.h MagickGetImageHeight" getHeight :: Ptr MagickWand -> CULong foreign import ccall "wand/magick_wand.h MagickGetImagePixels" getPixels :: Ptr MagickWand -> CULong -> CULong -> CULong -> CULong -> CString -> CInt -> (Ptr a) -> IO CInt -- StorageType: enum Char=1,Short,Integer,Long,Float=5,Double type Frame a = Array (Int,Int) (Pixel a) getPixel :: ([a],Int) -> Pixel a getPixel (floats,i) = Pixel (floats!!(i*3)) (floats!!(i*3+1)) (floats!!(i*3+2)) getFrame :: (Storable a) => (Ptr a) -> Int -> Int -> IO (Frame a) getFrame arr h w = do putStr ("getFrame: "++(show (w,h))++"\n") floats <- peekArray (3*h*w) arr return (array ((1,1),(h,w)) [((i,j),getPixel (floats,((w*i)+j))) | i<-[1..h],j<-[1..w]]) loadFrameFloat :: FilePath -> IO (Frame CFloat) loadFrameFloat filename = do wand <- newMagickWand f <- (newCString filename) ok <- readImage wand f let w = (fromInteger.toInteger) (getWidth wand) h = (fromInteger.toInteger) (getHeight wand) in do arr <- mallocArray (w*h*3) :: (IO (Ptr CFloat)) rgb <- (newCString "RGB") ok1 <- getPixels wand 0 0 (getHeight wand) (getWidth wand) rgb 5 arr -- PixelFloat==5 frame <- getFrame arr h w free arr destroyMagickWand wand return frame thanks, John

4 3

My old chess player
by paolo veronelli 01 Jul '04

01 Jul '04

Ok Crypt Master give the hint to pronounce something ,because I feel a complete stupid in front of Functional Programming' though I'm a trained imperative one. I've read the nice paper www.cs.chalmers.se/~rjmh/Papers/whyfp.html and remember may years ago the hard job done to make my chess engine work ,but that was imperative C that's why it was hard ,isn't it? John Huges say the way for trees is data Albero position=Foglia position |Ramo position [Albero position] This is like Quantum-Mechanics for my head but it works ,I've tried. figliatore creatore (Foglia position) = Ramo position (map (figliatore creatore) (creatore (Foglia Position)) This I don't know how to try it but I'm faithfully blind........ Now I would like to make a change to fit my player,but the wall is too high. My function 'creatore' in fact would take a list of moves and a starting position as argument, not a nice ready position. My imperative engine stored leaves with a pointer to their mothers so that it was easy to track the list of moves. Now maybe I have to change Albero definition in data Albero move mother=Foglia move mother |Ramo move mother [Albero move mother] Is this the way? the road tracker is going to be pather (Foglia move mother)= if mother==() = () else = (pather madre ):madre This doesn't compile!! And I don't write the new 'figliatore' not to insult anyone Thanks For Comments Paolino Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/

1 0

Newbie questions
by Crypt Master 01 Jul '04

01 Jul '04

Hi I consider myself a pretty good imperative programmer, been at it for decades, and am tryibng my hand at Haskell now. Unfrituantly I am not "getting" it all that quickly despite having the multimedia haskell book. To start ghetting some hands on, I thought iI owuld do something which i have done many times before in imperatives, a basic Genetic Algorithm Library. Unfortunatly I am comming unstuck straight away and was hoping some of you kind folk could point in the direction of dry land :-) iIf your not familiar with GAs its not too important, simply a GA searches over the whole solution space randomly. Well not quiet, its a guided search, its guided by evolution ie by the fitness of each indicidual of a random initial population. Evolution is simulated by 3 basic operators, selection, cross over and mutation. selection is which indiviuals get to breed, cross over is how they breed, and mutation is just things intetresting. So after reading the multimedia book, Iimmediately thought of a defining the solution space as a infinite list. I was hoping then I could do things like take 5 gaSolutionSpace to get 5 iterations or generations. My first attempt tied to use lis syntax [], but it wouldnt compile and after seeing "numsFrom" ina tutorial I redefined it as such. Here is what I have so far: -- gaSolutionSpace :: [a] -> [a] -- gaSolutionSpace [] = gaSolutionSpace createRandomPopulation -- recursive base case gaSolutionSpace x = x : gaSolutionSpace (evolvepopulation x) evolvepopulation :: a -> a evolvepopulation p = mutate cross select p -- createRandomPopulation :: [Num a] createRandomPopulation = [1,23,4,5,6] cross p = p mutate p = p select p = p ---- The take operator doesnt work on this. from hugs: HAGA> take 5 gaSolutionSpace [1,2,3,4,5] ERROR - Type error in application *** Expression : take 5 gaSolutionSpace [1,2,3,4,5] *** Term : take *** Type : Int -> [e] -> [e] *** Does not match : a -> b -> c -> d I am not sure I follow this. I assume its cause I didnt use the list notation in definaing gaSolutionSpace. Any ideas on how to do that. ? What about using map. It occurs to me that you can define gaSolutionspace as a map of the evolvolepopuloation function acrossan infinite solution space, but I dont know how to makethis infinte list to map over ...? There ar 2 papaers on GAs in haskell, but they use monads. I realise for performance I will probably have to use them too, but for now I would liek to do it without mondas even if performance isnt optimal. Sorry again for the newbie questions, but any help is appreciated. Stephen _________________________________________________________________ Add photos to your e-mail with MSN 8. Get 2 months FREE*. http://join.msn.com/?page=features/featuredemail

1 0

RE: [Haskell-cafe] some newbie FFI questions
by Simon Marlow 01 Jul '04

01 Jul '04

On 01 July 2004 11:53, John Kozak wrote: > I'm trying to experiment with image processing in haskell (with which > I haven't much experience). I've written some FFI code to talk to > the ImageMagick library which provokes a few questions (environment is > ghc 6.2.1 on debian): > > 1. Speed: I'm reading in a 2000x1500 pixel image, and have defined a > Pixel type like this: > > data Pixel a = Pixel !a !a !a deriving Show > > I use ImageMagick to load the image, then build an Array of Pixel > Floats. Building the array takes 45 seconds on a 2.5Ghz P4 with > code compiled -O2, which seems slow to me - are my expectations > unrealistic? I've tried various UNPACK things which didn't make > much difference. It depends how you want to use the image data, but this is almost certainly not the best representation. The fastest choice would be simply 'Ptr CFloat' (i.e. do no conversion or marshalling at all). This is essentially what your C program is doing. In Haskell you can allocate the memory using allocaBytes or mallocForeignPtr (no free required). Your other choices are: - IOUArray Int Float Fast access, but you need to convert the entire array into one of these, and back again if you need to pass it back to C. - (IOUArray Int Float, IOUArray Int Float, IOUArray Int Float) i.e. split the planes. Might be useful, depending on how you access the array. Conversion required again. - StorableArray Int CFloat You can convert the 'Ptr CFloat' you get back from C directly into a StorableArray, which gives you easy access using the mutable array primitives in Haskell, and an easy way to pass the array back to C using withStorableArray. Unfortunately accessing StorableArrays isn't as fast as it could be. And there ought to be a way to convert between StorableArray and IOUArray. This is one area that could do with some attention. - Array Pixel, and data Pixel = Pixel {-# UNPACK #-}!Float ... Not too great, because you have a few extra layers of indirection compared to IOUArrays, even with the UNPACKs. - Array (Float,Float,Float) Terrible :-) > 2. How do I convert a CFloat into a Float? Using realToFrac, I guess. > 3. I get the wrong answer ;-) I expect the C and haskell code below > to produce the same pixel data, but they don't (the C code is > right). I suggest fixing a more efficient representation first. This will reduce the amount of manipulation of the data, and either make the bug go away or make it easier to find. Cheers, Simon

1 0

Re: [Haskell-cafe] some newbie FFI questions
by MR K P SCHUPKE 01 Jul '04

01 Jul '04

Yes, deriving unboxable would be nice... I think for images though it is not too much of a problem to work with a record of arrays rather that an array of records. Keean.

1 0

Re: [Haskell-cafe] some newbie FFI questions
by MR K P SCHUPKE 01 Jul '04

01 Jul '04

Oh... also when using unboxed arrays you may well have to have a separate array for each colour plane (r,g,b,a) as I think unboxed arrays can only contain primitive types - although I am not certain about this - it may be enough to have the contents strict. Keean.

2 1

Re: [Haskell-cafe] some newbie FFI questions
by MR K P SCHUPKE 01 Jul '04

01 Jul '04

If you are using GHC the fastest way I know to do this is to build the array using a mutable-unboxed array in the state-monad. Then freeze the array and return an unboxed immutable array. This is a lot faster than building the array by copying (every time you set a value in an immutable array the whole array much be copied - for a sizeable image this is quite a lot of work!) Keean.

1 0

Re: [Haskell] Help in understanding a type error involving forall and class constraints
by Duncan Coutts 30 Jun '04

30 Jun '04

On Wed, 2004-06-30 at 12:00, MR K P SCHUPKE wrote: > Ahh.. I see whats happening: > > MArray (STUArray s) a (ST s) => String -> String -> ST s (UArray (Int,Int) a) > > IArray UArray a => String -> String -> a > > nothing here is specifying a... you cannot leave a polymorphic in this case. > > You need to supply the constraint "MArray (STUArray s) a (ST s)" to distString > but "s" is not in context... Right, because the return type of distString Int is an instance of MArray. But if we try to make 'a' polymorphic then we can't specify the constraint because it involves 's'. So the obvious follow-on question, is is there any intermediate point where 's' is in scope where we can supply a type annotation to supply the context or is it simply impossible? To restate the question for Haskell-Cafe readers: Is it possible to return an arbitrary unboxed array that was constructed in the ST monad (as an STUArray)? The issue is that you end up with a MArray class constraint that involves the state thread's 's' parameter, but this type variable gets 'hidden' by runST which universally quantifies over it. runST :: forall a. (forall s. ST s a) -> a Duncan

1 1