- Haskell-Cafe - Haskell.org

Haskell Weekly News?
by aditya siram 23 Jun '10

23 Jun '10

Hi all, I haven't seen a "Haskell Weekly News" in a while. Is there anything I can do to help? -deech

9 16

In other words is there a good place to post stuff like the following?
by caseyh＠istar.ca 23 Jun '10

23 Jun '10

-- Algorithms From: "Selected Papers on Design of Algorithms", Donald Knuth, 2010 -- Chapter 10 Addition Machines -- Haskell version by Casey Hawthorne -- Note this is only a skeleton of the chapter, -- so as to wet your interest to buy the book. -- Addition Machine -- The only operations allowed are the following: -- read x -- x <- y -- x <- x + y -- x <- x - y -- if x >= y -- write x -- Can all functional versions be tail recursive? ----------------------------------------------------------------------- ----------------------------------------------------------------------- -- Modulus -- Assuming without loss of generality x>=0 and y>0, -- since one can use various identities for other cases. -- Performs floor(x/y) subtractions. modulusNaive x y | x >= y = modulusNaive (x-y) y | otherwise = x -- Can we do better? -- Uses a doubling procedure to subtract larger multiplies of y. -- Bounded by O(log(x/y))^2 modulusByDoubling x y | x >= y = helper y y | otherwise = x where helper w z | x < z = helper z z+z | otherwise = modulusByDoubling (x-w) y -- Can we do better? -- Want bounded by O(log(x/y)). -- Addition Machine, so cannot divide by 2. -- Implicitly use the Fibonacci representation of floor(x/y) -- instead of its the binary representation. -- F0 = 0; F1 = 1; Fn = F(n-1) + F(n-2), n >=2 -- Every nonnegative integer n can be uniquely represented in the form -- n = F(m1) + F(m2) + ... + F(mt), m1 >> m2 >> ... >> mt >> 0 -- where t >= 0 and m >> m' means that m - m' >= 2 -- If n > 0 this representation can be found by choosing m1 such that -- F(m1) <= n < F(m1+1) ----------------------------------------------------------------------- -- Furthermore Fibonacci numbers grow exponentially, -- about 69% as fast as powers of 2. -- They have been used as power-of-2 analogs in a variety of algorithms. ----------------------------------------------------------------------- modulusFib x y | x >= y = helper x y y | otherwise = x where helper x y z | x < z = helper x z y+z | otherwise = helper2 x y z helper2 x y z | x >= y = helper2 (x-y) y z | y > z = helper2 x (z-y) y | otherwise = x

2 1

In other words is there a good place to post stuff like the following?
by caseyh＠istar.ca 23 Jun '10

23 Jun '10

-- Algorithms From: "Selected Papers on Design of Algorithms", Donald Knuth, 2010 -- Chapter 10 Addition Machines -- Haskell version by Casey Hawthorne -- Note this is only a skeleton of the chapter, -- so as to wet your interest to buy the book. -- Addition Machine -- The only operations allowed are the following: -- read x -- x <- y -- x <- x + y -- x <- x - y -- if x >= y -- write x -- Can all functional versions be tail recursive? ----------------------------------------------------------------------- ----------------------------------------------------------------------- -- Modulus -- Assuming without loss of generality x>=0 and y>0, -- since one can use various identities for other cases. -- Performs floor(x/y) subtractions. modulusNaive x y | x >= y = modulusNaive (x-y) y | otherwise = x -- Can we do better? -- Uses a doubling procedure to subtract larger multiplies of y. -- Bounded by O(log(x/y))^2 modulusByDoubling x y | x >= y = helper y y | otherwise = x where helper w z | x < z = helper z z+z | otherwise = modulusByDoubling (x-w) y -- Can we do better? -- Want bounded by O(log(x/y)). -- Addition Machine, so cannot divide by 2. -- Implicitly use the Fibonacci representation of floor(x/y) -- instead of its the binary representation. -- F0 = 0; F1 = 1; Fn = F(n-1) + F(n-2), n >=2 -- Every nonnegative integer n can be uniquely represented in the form -- n = F(m1) + F(m2) + ... + F(mt), m1 >> m2 >> ... >> mt >> 0 -- where t >= 0 and m >> m' means that m - m' >= 2 -- If n > 0 this representation can be found by choosing m1 such that -- F(m1) <= n < F(m1+1) ----------------------------------------------------------------------- -- Furthermore Fibonacci numbers grow exponentially, -- about 69% as fast as powers of 2. -- They have been used as power-of-2 analogs in a variety of algorithms. ----------------------------------------------------------------------- modulusFib x y | x >= y = helper x y y | otherwise = x where helper x y z | x < z = helper x z y+z | otherwise = helper2 x y z helper2 x y z | x >= y = helper2 (x-y) y z | y > z = helper2 x (z-y) y | otherwise = x

1 0

FastCGI, new maintainer
by Christopher Done 23 Jun '10

23 Jun '10

I'm the new maintainer of the FastCGI package[1]. Please upgrade to the latest version, 3001.0.2.3. It includes a fix for a special but real case in which the library throws an exception when the httpd server unexpectedly closes the connection[2], and the base version and exceptions have been upgraded to the latest versions.[3] Any problems, get in touch, or post an issue on this github project: http://github.com/chrisdone/fastcgi If you have patches preferably fork the fastcgi project on github and do a "Pull request". Alternatively just send me a diff. Cheers [1]: http://hackage.haskell.org/package/fastcgi [2]: http://github.com/chrisdone/fastcgi/commit/de8d303b30dec097a1d24a8991da85d3…

1 0

Control.Alternative --- some and many?
by Gregory Crosswhite 23 Jun '10

23 Jun '10

Hey everyone, Could someone explain to me (or point me to a reference explaining) the purpose of the "some" and "many" methods of the Alternative class? Also, there is a link posted in the documentation for Control.Applicative to a paper which describes the motivation behind the Applicative class; is there similarly a paper explaining the motivation behind the Alternative class? (The problem with Googling for "Alternative" is that this word is used a whole lot of the time, and very rarely does it refer to the Alernative class. :-) ) Cheers, Greg

3 2

TypeFamillies and UndecidableInstances - why?
by Maciej Piechotka 23 Jun '10

23 Jun '10

When I tried to do something like: > {-# LANGUAGE FlexibleContexts #-} > {-# LANGUAGE TypeFamilies #-} > > class Test a where > type TestMonad a :: * -> * > from :: a b -> TestMonad a b > to :: TestMonad a b -> a b > > data Testable a b = Testable (a b) > > instance (Test a, Functor (TestMonad a)) => Functor (Testable a) where > f `fmap` Testable v = Testable $! (to . fmap f . from) v > It asks for adding UndecidableInstances as: test.hs:11:0: Constraint is no smaller than the instance head in the constraint: Functor (TestMonad a) (Use -XUndecidableInstances to permit this) In the instance declaration for `Functor (Testable a)' What is undecidable? a is bound so TestMonad a should be bound so Functor (TestMonad a) should be valid. Is it a bug/missing feature in ghc or do I fail to see something? Regards

4 4

ANN: srec-0.0.0
by Tom Hawkins 23 Jun '10

23 Jun '10

A little library for reading s-record files: http://hackage.haskell.org/package/srec -Tom

2 2

TH instance code.
by Andy Stewart 22 Jun '10

22 Jun '10

Hi all, I have below duplicate code, but i don't know how to use TH instance code. ------------------------------> duplicate code start <------------------------------ instance Variable PageType where toVariant = toVariant . show fromVariant x = fmap (\v -> read v :: PageType) $ fromVariant x instance Variable Int where toVariant = toVariant . show fromVariant x = fmap (\v -> read v :: Int) $ fromVariant x instance Variable (Maybe Char) where toVariant = toVariant . show fromVariant x = fmap (\v -> read v :: Maybe Char) $ fromVariant x instance Variable (Maybe Int) where toVariant = toVariant . show fromVariant x = fmap (\v -> read v :: Maybe Int) $ fromVariant x instance Variable ProcessID where toVariant = toVariant . show fromVariant x = fmap (\v -> read v :: ProcessID) $ fromVariant x instance Variable GWindowId where toVariant = toVariant . show fromVariant x = fmap (\v -> read v :: GWindowId) $ fromVariant x ------------------------------> duplicate code end <------------------------------ Any TH expert help? Thanks, -- Andy

4 5

Minix
by Henk-Jan van Tuyl 22 Jun '10

22 Jun '10

L.S., I just read about Minix and found a discussion [1] about Andrew Tanenbaum (the creator of Minix) wanting to try drivers written in Haskell on Minix. It has been four years since, is there currently a way to (cross)compile Haskell programs for Minix? Haskell well suited to write reliable software and Minix is all about reliability; they seem to match perfectly. It would increase visibility of Haskell if it can be used on Minix systems. Regards, Henk-Jan van Tuyl [1] http://groups.google.com/group/fa.haskell/browse_thread/thread/43f22847305b… -- http://Van.Tuyl.eu/ http://members.chello.nl/hjgtuyl/tourdemonad.html --

2 1

Different choice operations in a continuation monad
by Sebastian Fischer 22 Jun '10

22 Jun '10

Dear Café, `MonadPlus` instances are usually required to satisfy certain laws, among them the monad laws and monoid laws for `mzero` and `mplus`. Additionally one may require that (>>=f) is a monoid morphism, that is: mzero >>= f = mzero (a `mplus` b) >>= f = (a >>= f) `mplus` (b >>= f) The list monad satisfies these additional laws, the `Maybe`-Monad does not satisfy the second, distributive, law: ghci> (return False `mplus` return True) >>= guard :: [()] [()] ghci> (return False `mplus` return True) >>= guard :: Maybe () Nothing Instead of the distributive law, the `Maybe` monad satisfies a different law: return x `mplus` a = return x that is, `return` annihilates the `Maybe`-Monad regarding `mplus`. This "cancellation law" is incompatible with the distributive law because (together with other laws) it implies that the result of the above example expression is `Nothing` whereas the distributive law implies that it is `Just ()`. We can lift the `Maybe` type into a continuation monad: > newtype CMaybe r a = CMaybe ((a -> Maybe r) -> Maybe r) > > instance Monad (CMaybe r) where > return x = CMaybe (\k -> k x) > CMaybe ca >>= f = CMaybe (\k -> ca (\x -> let CMaybe cb = f x in cb k)) > > instance MonadPlus (CMaybe r) where > mzero = CMaybe (\_ -> mzero) > CMaybe ca `mplus` CMaybe cb = CMaybe (\k -> ca k `mplus` cb k) Unlike the `Maybe`-monad, the `CMaybe`-monad satisfies the distributive law, not the cancellation law. Can you define an associative operation orElse :: CMaybe r a -> CMaybe r a -> CMaybe r a with identity `mzero` that satisfies the cancellation law? Cheers, Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.)

5 16