September 2010 - Haskell-Cafe

Applicative instances for Monads
by Gregory Crosswhite 25 Sep '10

25 Sep '10

Hey everyone, There is something that has been bugging me recently about the Applicative class and the Monad class. Any type constructor F that is a Monad has a natural Applicative instance, (<$>) :: F (a -> b) -> F a -> F b mf <$> ma = do f <- mf a <- ma return (f a) So it seems that defining something to be a Monad should automatically make it an instance of Applicative with this definition for (<$>). So far so good, but there are times when this implementation is too "sequential". The nature of Applicative is that later actions are not allowed to depend on earlier actions, which means that it is natural to run them in parallel when possible. So for example, considering the following alternative of Applicative for a newtype AIO that wraps an IO computation: ====================================================================== import Control.Applicative import Control.Concurrent import Control.Concurrent.MVar newtype AIO a = AIO {unAIO :: IO a} instance Monad AIO where return = AIO . return (AIO x) >>= f = AIO (x >>= unAIO . f) instance Functor AIO where fmap f (AIO x) = AIO (fmap f x) instance Applicative AIO where pure = return (AIO mf) <*> (AIO ma) = AIO $ do f_box <- newEmptyMVar forkIO (mf >>= putMVar f_box) a_box <- newEmptyMVar forkIO (ma >>= putMVar a_box) f <- takeMVar f_box a <- takeMVar a_box return (f a) ====================================================================== This seems to me to be an arguably better way to implement Applicative because it uses the fact that we know that the second action is independent from the first to gain parallelism by sparking them in separate threads. So for example if one has six actions m1 ... m6 that could run in parallel then one could write something like the following: ====================================================================== main = do ... (x1,x2,x3,x4,x5,x6) <- (,,,,,) <$> a1 <*> a2 <*> a3 <*> a4 <*> a5 <*> a6 ... ====================================================================== Here is another example: Consider the following instance of Applicative for the Either type: ====================================================================== import Control.Applicative import Data.Monoid instance Monoid error => Applicative (Either error) where pure = Right Right f <*> Right x = Right (f x) Left error <*> Right _ = Left error Right _ <*> Left error = Left error Left error1 <*> Left error2 = Left (error1 `mappend` error2) display :: Either String Int -> IO () display = putStrLn . show main = mapM_ (putStrLn . show) [Right (+1) <*> Right 1 ,Right (+1) <*> Left "[bad value]" ,Left "[bad function]" <*> Right 1 ,Left "[bad function]" <*> Left "[bad value]" ] ====================================================================== This is much like the instance used by the Error monad, but it has the advantage that rather than terminating at the first sign of error it instead gathers together the errors produced by each subcomputation. Again, we can do this because we know that we do not need the result of the first computation in order to evaluate the second computation. To summarize: on the one hand every Monad has a generic instance for Applicative, and yet on the other hand this instance is often arguably not the "correct" one because it ignores the fact that the second computation is independent of the first, which is a fact that can be exploited given additional knowledge about the structure of the Monad. I bring this up because there has been talk here of automatically having instances of Monad also be instances of Applicative, and what bugs me is that on the one hand this makes perfect since as every Monad can also be viewed as an Applicative, and yet on the other hand not only is there often more than one natural way to define an Applicative instance for selected Monads but furthermore the "generic" instance is often an inferior definition because it ignores the structure of the Monad. Thoughts? Cheers, Greg

3 2

Re: [Haskell-cafe] Inverse of HaskellDB
by Jonathan Geddes 25 Sep '10

25 Sep '10

>Have you given any thought as to how you want to approach versioning? After giving this some more thought, I realized: 1) One of the "best practices" (even though I despise the term) of versioning schema is to include a script with the code which checks for each change to the tables, and makes the change if it is needed [1]. Each time you check out new code, you run the script to ensure that the code you are working with matches the tables you are working with. 2) A system that generates tables from Haskell types could also be made to check if a given table faithfully represents a given Haskell record type. It could then make any changes to the table so that it _does_ faithfully represent the record type. 3) In this way, your Haskell records ARE your table update script, just (like most Haskell code) incredibly terse. Your usual code repository will track when and by whom changes are made to the record. Of course, there are some issues with this, but I think it could be made to work well. >Hibernate does this, more or less, for Java classes. That might be a >good place to look for ideas. Good point. I'll start there. [1] http://www.codeproject.com/KB/database/DatabaseSchemaVersioning.aspx --Jonathan On Sat, Sep 25, 2010 at 3:45 PM, Rogan Creswick <creswick(a)gmail.com> wrote: > On Sat, Sep 25, 2010 at 12:31 PM, Jonathan Geddes > <geddes.jonathan(a)gmail.com> wrote: >> >> Does such a thing exist? If not, would you find it useful? I may take >> this up as a side project if it does not already exist and others >> would find it useful. >> > > I've been looking for something along these lines too. > > Hibernate does this, more or less, for Java classes. That might be a > good place to look for ideas. > > --Rogan > >> Thanks, >> >> --Jonathan >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> >

1 0

Shared thunk optimization. Looking to solidify my understanding
by David Sankel 25 Sep '10

25 Sep '10

The following code (full code available here[1], example taken from comments here[2]), const' = \a _ -> a test1 c = let a = const' (nthPrime 100000) in (a c, a c) test2 c = let a = \_ -> (nthPrime 100000) in (a c, a c) in a ghci session (with :set +s): *Primes> test1 1 (9592,9592) (0.89 secs, 106657468 bytes) *Primes> test2 1 (9592,9592) (1.80 secs, 213077068 bytes) test1, although denotationally equivalent to test2 runs about twice as fast. My questions are: - What is the optimization that test1 is taking advantage of called? - Is said optimization required to conform to the Haskell98 standard? If so, where is it stated? - Could someone explain or point to a precise explanation of this optimization? If I'm doing an operational reduction by hand on paper, how would I take account for this optimization? Thanks, David [1] http://hpaste.org/40033/operational_semantics [2] http://conal.net/blog/posts/lazier-functional-programming-part-2/ -- David Sankel Sankel Software www.sankelsoftware.com

6 7

Re: [Haskell-cafe] Simple question about the function composition operator
by wren ng thornton 25 Sep '10

25 Sep '10

On 9/24/10 5:35 AM, Axel Benz wrote: > Can anybody explain why this happens and how I can compose f and g? > > Hint: It works fine if f is defined as an unary function. As already mentioned: (g . f) x y = (\z-> g (f z)) x y = g (f x) y In order to get it to work you need to say that you want to pass two arguments to f. The immediate answer is ((g .) . f) but that doesn't really give you a general pattern to use. The general pattern is, -- | Binary composition. (...) :: (c -> d) -> (a -> b -> c) -> (a -> b -> d) (...) = (.) . (.) {-# INLINE (...) #-} infixl 8 ... and then (g ... f) x y = g (f x y). Note that the fixity is set up so that (...) plays nicely with (.). You may also be interested in, -- | Compose on second arg. (.^) :: (a -> c -> d) -> (b -> c) -> (a -> b -> d) (.^) = flip ... (.) . flip {-# INLINE (.^) #-} infix 9 .^ -- | Function composition which calls the right-hand -- function eagerly. (.!) :: (b -> c) -> (a -> b) -> a -> c (.!) = (.) . ($!) {-# INLINE (.!) #-} infixr 9 .! -- Live well, ~wren

1 0

ANN: JMacro 0.3.2, A library/dsl for generating Javascript
by Gershom B 25 Sep '10

25 Sep '10

JMacro on hackage: http://hackage.haskell.org/package/jmacro This is the first official release announcement for JMacro, which has been on hackage in some form for over a year, and in the current version since July. JMacro is a library for the programmatic generation of Javascript code. It is designed to be multipurpose -- it is useful whether you are writing nearly vanilla Javascript or you are programmatically generating Javascript either in an ad-hoc fashion or as the backend to a compiler or EDSL. It provides support for hygienic names, as well as sharing of names between the generated Javascript and embedded Haskell antiquotation. In this release it also includes a module which allows the generation of RPC request/response pairs, allowing a lightweight implementation of AJAX-heavy applications. JMacro provides a simple, lightweight quasiquoted syntax that is mainly compatible with standard Javascript. Most Javascript code in the wild can be used as JMacro code with no or minimal modification. However, JMacro extends Javascript syntax in a number of Haskell-friendly ways, including whitespace function application and single character lambdas. Syntax is statically checked at compile time. JMacro expressions may contain antiquoted Haskell code. This code may generate further JMacro code, or it may generate any of a range of standard Haskell types, which are able to be marshalled into JMacro through typeclass methods. JMacro also provides an executable, which allows the standalone processing of JMacro code into Javascript. For more information, see both Hackage and the JMacro documentation on the HaskellWiki: http://www.haskell.org/haskellwiki/Jmacro Some examples or idiomatic JMacro code are available in the source of its provided Javascript Prelude: http://hackage.haskell.org/packages/archive/jmacro/0.3.2/doc/html/src/Langu… Future work on JMacro, when time is available, is geared towards providing an optional layer of static typing with type inference. Patches, bug reports, and feature requests are all very welcome.

1 0

Tree Construction
by Tom Hawkins 25 Sep '10

25 Sep '10

Hi, Often I need to assemble a tree from things with unstructured hierarchical paths. I built a function [1] to do this for ImProve. But does a library already exist that does this? If not I may create one, as I need it for a few different libraries. data Tree a b = Branch a [Tree a b] | Leaf a b tree :: (Eq a, Ord a) => (b -> [a]) -> [b] -> [Tree a b] Note, type 'a' is some sort of label, most often a string, and type 'b' form the leaves of the tree. The function passed into 'tree' returns the hierarchical path of a leaf object. -Tom [1] http://hackage.haskell.org/packages/archive/improve/0.0.12/doc/html/Languag…

3 2

Throwing and catching exceptions in STM
by Bas van Dijk 24 Sep '10

24 Sep '10

Hello, The IO monad has the following function for throwing an exception: throwIO :: Exception e => e -> IO a Is there an analogous way of throwing an exception in the STM monad? I can try using: throw :: Exception e => e -> a. But does this guarantee ordering with respect to other STM actions? The IO monad has the following function for catching exceptions: catch :: Exception e => IO a -> (e -> IO a) -> IO a Why is catchSTM defined as: catchSTM :: STM a -> (SomeException -> STM a) -> STM a And not as the more general and more consistent: catchSTM :: Exception e => STM a -> (e -> STM a) -> STM a Thanks, Bas

1 0

Re: [Haskell-cafe] Simple question about the function composition operator
by Miguel Mitrofanov 24 Sep '10

24 Sep '10

(g . f) x y = (\z -> g (f z)) x y = g (f x) y, and you need g (f x y), which is definitely not the same thing. 24.09.2010 13:35, Axel Benz пишет: > > Hello, > > this is maybe a simple question: > > cbinary :: a -> b -> (a -> b -> b) -> (b -> c) -> c > > -- Version 1 works: > > cbinary x y f g = g (f x y) > > -- Version 2 should be exactly the same according > > -- to my understanding of the "." operator definition, > > -- but fails with: > > -- Occurs check: cannot construct the infinite type: b = b -> b > > -- When generalising the type(s) for `cbinary' > > -- cbinary x y f g = (g . f) x y > > Can anybody explain why this happens and how I can compose f and g? > > Hint: It works fine if f is defined as an unary function. > > Thank you very much! > > Axel > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe

1 0

Simple question about the function composition operator
by Axel Benz 24 Sep '10

24 Sep '10

Hello, this is maybe a simple question: cbinary :: a -> b -> (a -> b -> b) -> (b -> c) -> c -- Version 1 works: cbinary x y f g = g (f x y) -- Version 2 should be exactly the same according -- to my understanding of the "." operator definition, -- but fails with: -- Occurs check: cannot construct the infinite type: b = b -> b -- When generalising the type(s) for `cbinary' -- cbinary x y f g = (g . f) x y Can anybody explain why this happens and how I can compose f and g? Hint: It works fine if f is defined as an unary function. Thank you very much! Axel

1 0

ANNOUNCE: tableaux-0.1
by Pedro Baltazar Vasconcelos 24 Sep '10

24 Sep '10

Hi everyone, I'd just like to announce the first release of Tableaux, a web-based interactive theorem prover for first-order logic based on the method of semantic tableaux (cf. "First-Order Logic", Raymond Smullyan, Dover). This prover was intended as a teaching aid for undergraduate students and enforces a step-by-step construction of proofs. It could also be used as a basis for provers for other logics. Tableaux runs on any web server supporting the CGI interface; uou can check it out at http://www.ncc.up.pt/~pbv/cgi/tableaux.cgi. The source package is available from Hackage: http://hackage.haskell.org/package/tableaux. Best regards, Pedro Vasconcelos

1 0