News aggregator

A function that takes a function returning the next seed and an element in the final list

Haskell on Reddit - Wed, 11/26/2014 - 6:39pm

Does this have a name?

chain :: (a -> b -> (a, c)) -> a -> [b] -> [c] chain _ _ [] = [] chain f seed (z : zs) = y : chain f x zs where (x, y) = f seed z

You could use it like this:

λ> chain (\x y -> (succ x, x * y)) 0 [1 .. 10] [0,2,6,12,20,30,42,56,72,90] submitted by im_not_afraid
[link] [8 comments]
Categories: Incoming News

Jasper Van der Jeugt: Image Processing with Comonads

Planet Haskell - Wed, 11/26/2014 - 6:00pm
Introduction

A Comonad is a structure from category theory dual to Monad.

Comonads are well-suited for image processing
– Pretty much everyone on the internet

Whenever Comonads come up, people usually mention the canonical example of evaluating cellular automata. Because many image processing algorithms can be modelled as a cellular automaton, this is also a frequently mentioned example.

However, when I was trying to explain Comonads to a friend recently, I couldn’t find any standalone example of how exactly this applies to image processing, so I decided to illustrate this myself.

I will not attempt to explain Comonads, for that I refer to Gabriel Gonzalez’ excellent blogpost. This blogpost is written in literate Haskell so you should be able to just load it up in GHCi and play around with it (you can find the raw .lhs file here).

> {-# LANGUAGE BangPatterns #-} > import qualified Codec.Picture as Juicy > import Control.Applicative ((<$>)) > import Data.List (sort) > import Data.Maybe (fromMaybe, maybeToList) > import qualified Data.Vector as V > import qualified Data.Vector.Generic as VG > import Data.Word (Word8) A simple image type

We need a simple type for images. Let’s use the great JuicyPixels library to read and write images. Unfortunately, we cannot use the image type defined in JuicyPixels, since JuicyPixels stores pixels in a Storable-based Vector.

We want to be able to store any kind of pixel value, not just Storable values, so we declare our own BoxedImage. We will simply store pixels in row-major order in a boxed Vector.

> data BoxedImage a = BoxedImage > { biWidth :: !Int > , biHeight :: !Int > , biData :: !(V.Vector a) > }

Because our BoxedImage allows any kind of pixel value, we get a straightforward Functor instance:

> instance Functor BoxedImage where > fmap f (BoxedImage w h d) = BoxedImage w h (fmap f d)

Now, we want to be able to convert from a JuicyPixels image to our own BoxedImage and back again. In this blogpost, we will only deal with grayscale images (BoxedImage Word8), since this makes the image processing algorithms mentioned here a lot easier to understand.

> type Pixel = Word8 -- Grayscale > boxImage :: Juicy.Image Juicy.Pixel8 -> BoxedImage Pixel > boxImage image = BoxedImage > { biWidth = Juicy.imageWidth image > , biHeight = Juicy.imageHeight image > , biData = VG.convert (Juicy.imageData image) > } > unboxImage :: BoxedImage Pixel -> Juicy.Image Juicy.Pixel8 > unboxImage boxedImage = Juicy.Image > { Juicy.imageWidth = biWidth boxedImage > , Juicy.imageHeight = biHeight boxedImage > , Juicy.imageData = VG.convert (biData boxedImage) > }

With the help of boxImage and unboxImage, we can now call out to the JuicyPixels library:

> readImage :: FilePath -> IO (BoxedImage Pixel) > readImage filePath = do > errOrImage <- Juicy.readImage filePath > case errOrImage of > Right (Juicy.ImageY8 img) -> return (boxImage img) > Right _ -> > error "readImage: unsupported format" > Left err -> > error $ "readImage: could not load image: " ++ err > writePng :: FilePath -> BoxedImage Pixel -> IO () > writePng filePath = Juicy.writePng filePath . unboxImage Focused images

While we can already write simple image processing algorithms (e.g. tone mapping) using just the Functor interface, the kind of algorithms we are interested in today need take a neighbourhood of input pixels in order to produce a single output pixel.

For this purpose, let us create an additional type that focuses on a specific location in the image. We typically want to use a smart constructor for this, so that we don’t allow focusing on an (x, y)-pair outside of the piBoxedImage.

> data FocusedImage a = FocusedImage > { piBoxedImage :: !(BoxedImage a) > , piX :: !Int > , piY :: !Int > }

Conversion to and from a BoxedImage is easy:

> focus :: BoxedImage a -> FocusedImage a > focus bi > | biWidth bi > 0 && biHeight bi > 0 = FocusedImage bi 0 0 > | otherwise = > error "Cannot focus on empty images" > unfocus :: FocusedImage a -> BoxedImage a > unfocus (FocusedImage bi _ _) = bi

And the functor instance is straightforward, too:

> instance Functor FocusedImage where > fmap f (FocusedImage bi x y) = FocusedImage (fmap f bi) x y

Now, we can implement the fabled Comonad class:

> class Functor w => Comonad w where > extract :: w a -> a > extend :: (w a -> b) -> w a -> w b

The implementation of extract is straightforward. extend is a little trickier. If we look at it’s concrete type:

extend :: (FocusedImage a -> b) -> FocusedImage a -> FocusedImage b

We want to convert all pixels in the image, and the conversion function is supplied as f :: FocusedImage a -> b. In order to apply this to all pixels in the image, we must thus create a FocusedImage for every position in the image. Then, we can simply pass this to f which gives us the result at that position.

> instance Comonad FocusedImage where > extract (FocusedImage bi x y) = > biData bi V.! (y * biWidth bi + x) > > extend f (FocusedImage bi@(BoxedImage w h _) x y) = FocusedImage > (BoxedImage w h $ V.generate (w * h) $ \i -> > let (y', x') = i `divMod` w > in f (FocusedImage bi x' y')) > x y

Proving that this instance adheres to the Comonad laws is a bit tedious but not that hard if you make some assumptions such as:

V.generate (V.length v) (\i -> v V.! i) = v

We’re almost done with our mini-framework. One thing that remains is that we want to be able to look around in a pixel’s neighbourhood easily. In order to do this, we create this function which shifts the focus by a given pair of coordinates:

> neighbour :: Int -> Int -> FocusedImage a -> Maybe (FocusedImage a) > neighbour dx dy (FocusedImage bi x y) > | outOfBounds = Nothing > | otherwise = Just (FocusedImage bi x' y') > where > x' = x + dx > y' = y + dy > outOfBounds = > x' < 0 || x' >= biWidth bi || > y' < 0 || y' >= biHeight bi Median filter

If you have ever taken a photo when it is fairly dark, you will notice that there is typically a lot of noise. We’ll start from this photo which I took a couple of weeks ago, and try to reduce the noise in the image using our Comonad-based mini-framework.

The original image

A really easy noise reduction algorithm is one that looks at a local neighbourhood of a pixel, and replaces that pixel by the median of all the pixels in the neighbourhood. This can be easily implemented using neighbour and extract:

> reduceNoise1 :: FocusedImage Pixel -> Pixel > reduceNoise1 pixel = median > [ extract p > | x <- [-2, -1 .. 2], y <- [-2, -1 .. 2] > , p <- maybeToList (neighbour x y pixel) > ]

Note how our Comonadic function takes the form of w a -> b. With a little intuition, we can see how this is the dual of a monadic function, which would be of type a -> m b.

We used an auxiliary function which simply gives us the median of a list:

> median :: Integral a => [a] -> a > median xs > | odd len = sort xs !! (len `div` 2) > | otherwise = case drop (len `div` 2 - 1) (sort xs) of > (x : y : _) -> x `div` 2 + y `div` 2 > _ -> error "median: empty list" > where > !len = length xs

So reduceNoise1 is a function which takes a pixel in the context of its neighbours, and returns a new pixel. We can use extend to apply this comonadic action to an entire image:

extend reduceNoise1 :: FocusedImage Pixel -> FocusedImage Pixel

After applying reduceNoise1

Running this algorithm on our original picture already gives an interesting result, and the noise has definitely been reduced. However, you will notice that it has this watercolour-like look, which is not what we want.

Blur filter

A more complicated noise-reduction filter uses a blur effect first. We can implement a blur by replacing each pixel by a weighted sum of its neighbouring pixels. At the edges, we just keep the pixels as-is.

This function implements the simple blurring kernel:

> blur :: FocusedImage Pixel -> Pixel > blur pixel = fromMaybe (extract pixel) $ do > let self = fromIntegral (extract pixel) :: Int > topLeft <- extractNeighbour (-1) (-1) > top <- extractNeighbour 0 (-1) > topRight <- extractNeighbour 1 (-1) > right <- extractNeighbour 1 0 > bottomRight <- extractNeighbour 1 1 > bottom <- extractNeighbour 0 1 > bottomLeft <- extractNeighbour (-1) 1 > left <- extractNeighbour (-1) 0 > return $ fromIntegral $ (`div` 16) $ > self * 4 + > top * 2 + right * 2 + bottom * 2 + left * 2 + > topLeft + topRight + bottomRight + bottomLeft > where > extractNeighbour :: Int -> Int -> Maybe Int > extractNeighbour x y = fromIntegral . extract <$> neighbour x y pixel

The result is the following image:

The image after using blur

This image contains less noise, but as we expected, it is blurry. This is not unfixable though: if we subtract the blurred picture from the original picture, we get the edges:

The edges in the image

If we apply a high-pass filter here, i.e., we drop all edges below a certain threshold, such that we only retain the “most significant” edges, we get something like:

The edges after applying a threshold

While there is still some noise, we can see that it’s clearly been reduced. If we now add this to the blurred image, we get our noise-reduced image number #2. The noise is not reduced as much as in the first image, but we managed to keep more texture in the image (and not make it look like a watercolour).

After applying reduceNoise2

Our second noise reduction algorithm is thus:

> reduceNoise2 :: FocusedImage Pixel -> Pixel > reduceNoise2 pixel = > let !original = extract pixel > !blurred = blur pixel > !edge = fromIntegral original - fromIntegral blurred :: Int > !threshold = if edge < 7 && edge > (-7) then 0 else edge > in fromIntegral $ fromIntegral blurred + threshold

We can already see how the Comonad pattern lets us combine extract and blur, and simple arithmetic to achieve powerful results.

A hybrid algorithm

That we are able to compose these functions easily is even more apparent if we try to build a hybrid filter, which uses a weighted sum of the original, reduceNoise1, and reduceNoise2.

> reduceNoise3 :: FocusedImage Pixel -> Pixel > reduceNoise3 pixel = > let !original = extract pixel > !reduced1 = reduceNoise1 pixel > !reduced2 = reduceNoise2 pixel > in (original `div` 4) + (reduced1 `div` 4) + (reduced2 `div` 2)

The noise here has been reduced significantly, while not making the image look like a watercolour. Success!

After applying reduceNoise3

Here is our main function which ties everything up:

> main :: IO () > main = do > image <- readImage filePath > writePng "images/2014-11-27-stairs-reduce-noise-01.png" $ > unfocus $ extend reduceNoise1 $ focus image > writePng "images/2014-11-27-stairs-reduce-noise-02.png" $ > unfocus $ extend reduceNoise2 $ focus image > writePng "images/2014-11-27-stairs-reduce-noise-03.png" $ > unfocus $ extend reduceNoise3 $ focus image > where > filePath = "images/2014-11-27-stairs-original.png"

And here is a 300% crop which should show the difference between the original (left) and the result of reduceNoise3 (right) better:

Conclusion

I hope this example has given some intuition as to how Comonads can be used in real-world scenarios. For me, what made the click was realising how w a -> b for Comonad relates to a -> m b for Monad, and how these types of functions naturally compose well.

Additionally, I hope this blogpost provided some insight the image processing algorithms as well, which I also think is an interesting field.

Thanks to Alex Sayers for proofreading!

Categories: Offsite Blogs

John C Reynolds Doctoral Dissertation Award nominations for 2014

Lambda the Ultimate - Wed, 11/26/2014 - 4:05pm

Presented annually to the author of the outstanding doctoral dissertation in the area of Programming Languages. The award includes a prize of $1,000. The winner can choose to receive the award at ICFP, OOPSLA, POPL, or PLDI.

I guess it is fairly obvious why professors should propose their students (the deadline is January 4th 2015). Newly minted PhD should, for similar reasons, make sure their professors are reminded of these reasons. I can tell you that the competition is going to be tough this year; but hey, you didn't go into programming language theory thinking it is going to be easy, did you?

Categories: Offsite Discussion

Hackage.haskell.org emails Now Fixed!

Haskell on Reddit - Wed, 11/26/2014 - 3:19pm

Hopefully most of you haven't run into this. But for a while, some people were having trouble receiving emails from hackage. This made new account creation hard and also got in the way of password reset emails.

We figured out the problem (the wrong server was sending the emails, so some services were filtering them) and fixed it (started sending the emails from the main h.o server, which is trusted).

But if you were trying to register a hackage account, couldn't, and got discouraged, apologies for the inconvenience, and please try again!

submitted by gbaz1
[link] [comment]
Categories: Incoming News

How to enumerate all combinations of the elements of infinite lists?

Haskell on Reddit - Wed, 11/26/2014 - 3:09pm

Consider the typical example: "let allPairs = [(x,y) | x <- [0..], y <- [0..]]" enumerates the pairs of natural numbers, starting with 0 always being the first element of the tuple. As there are unfortunately indefinitely many pairs with 0 as the first component the expression "takeWhile (fst.first (/=1)) allPairs" won't terminate.

So how can I make allPairs enumerate all pairs such that every pair will be yielded in finite time? - I did it using the Cantor diagonalization idea. That's doing the job (inefficiently):

column y = [(x,y) | x <- [0..]]

diagonal i = map (\(i, colIndex) -> (column colIndex)!!i ) (zip [i, (i-1)..0] [0..])

allCantorPairs = concatMap diagonal [0..]

However, is there a way to generalize it to a n-tuple of n infinite lists? Is there already some function/library for doing that nicely? ;)

submitted by sleepomeno
[link] [11 comments]
Categories: Incoming News

Performance of finite field arithmetic

Haskell on Reddit - Wed, 11/26/2014 - 4:38am

I've recently been learning about the AES in more detail, as well as refreshing my memory on finite field arithmetic, and I implemented a multiplication algorithm for GF(28 ) in both Haskell and C as an exercise (I really started out in C and then decided to see how nice I can make it in Haskell).

This is what I came up with as the Haskell version: http://lpaste.net/7600089018482556928

And this is the C version of the multiplication algorithm: http://lpaste.net/637038203701821440

I've been running some small benchmarks on it and it seems that the Haskell version is a lot slower (on the order of several hundred times slower). Why is that? I understand that this sort of code is really one of C's strong points and the compiler can optimize it into really efficient code (in my benchmarks, a multiplication takes about 1.3ns on average).

It's not that the Haskell version would be unusably slow of course, but the difference is still quite staggering. Can someone shed some light on why Haskell is so much slower here?

As to how my benchmarks worked: I basically just did all possible multiplications and added them together and repeat that 4096 times, time that and divide it by the amount of multiplications done. The addition shouldn't have a big performance impact, since it's basically just a single XOR operation.

submitted by tsahyt
[link] [23 comments]
Categories: Incoming News

Changing directory?

Haskell on Reddit - Wed, 11/26/2014 - 12:13am

Hi all,

I know that it's possible to change working directory using System.Directory.setCurrentDirectory function or by calling cd command using shell-libraries. And it works as expected. You run command-line application from terminal, and working directory changes only for your application. And when process dies (no matter the reason why) you are still in directory from which you called your application.

Few days ago I wrote myself an application that helps me with navigating inside huge directory (don't ask why :D). Currently it returns path depending on given args and I use it like

$ pwd /path1 $ cd $(myapp args) $ pwd /path2

But then I thought that it's tedious. And asked myself if it's possible to

$ pwd /path1 $ myapp args $ pwd /path2

As far as I understand, it's not so easy to achieve. I spent some time trying different libraries that works with shell, but they all 'safe' and doesn't change callers state (or what is it called?).

So, I know, it's kinda dirty, but maybe someone could help me with my problem?

submitted by deadmaya
[link] [7 comments]
Categories: Incoming News