October 2009 - Haskell-Cafe

Fwd: [Haskell-cafe] I read somewhere that for 90% of a wide class of computing problems, you only need 10% of the source code in Haskell, that you would in an imperative language.
by Alberto G. Corona 01 Oct '09

01 Oct '09

;) Off topic: Maybe the entire space time, the universe and his history, is isomorphic to a mathematical structure. http://space.mit.edu/home/tegmark/toe_frames.html <http://space.mit.edu/home/tegmark/toe_frames.html> 2009/10/1 Peter Verswyvelen <bugfact(a)gmail.com> > > > On Thu, Oct 1, 2009 at 9:53 AM, Andrew Coppin <andrewcoppin(a)btinternet.com > > wrote: > >> Sure. But what is a computer program? It's a *list of instructions* that >> tells a computer *how to do something*. And yet, the Haskell definition of >> sum looks more like a definition of what a sum is rather than an actual, >> usable procedure for *computing* that sum. (Of course, we know that it /is/ >> in fact executable... it just doesn't look it at first sight.) >> > > Is it? The list of instruction is just an abstraction layer built on top of > purely physical process of electrons and transistors; I'm not sure how much > imperativeness remains at this level? Not to mention the quantum mechanical > processes that take place... And that are also just mathematical models... I > mean, it really depends from which angle and at which detail you look at it, > no? > > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe > >

1 0

river crossing puzzle
by pat browne 01 Oct '09

01 Oct '09

Hi, Does anyone know where there are any Haskell implementations of the the River Crossing puzzle (AKA Farmer/Fox/Goose/Grain). There are several variations but the general ideas are explained at: http://en.wikipedia.org/wiki/River_crossing_puzzle http://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_puzzle I have found one at: http://www.shido.info/hs/haskell9.html Thanks, Pat

4 3

Re: [Haskell-cafe] Exceptions during exception unwinding
by Brian Bloniarz 01 Oct '09

01 Oct '09

Sorry for the garbled post, this should hopefully be plain text: > On Thu, 2009-10-01 at 03:29 +0000, Brian Bloniarz wrote: >> I.e. why does an exception raised during exception handling get >> propagated past the exception that triggered the handler? > > Because it's the obvious and sensible thing to do and it what every > other mainstream language with exceptions does. The behaviour you want, > to automatically discard any exceptions raised in the handler and to > always re-raise the original exception can be implemented using the > current semantics, but the reverse is not true. Good to know ... C++ (the mainstream language I'm most familiar with) treats throwing from a destructor during unwinding as a fatal error. I was suggesting having bracket ignore exceptions from closeSomeHandle when doAction threw, not that it'd ignore any exceptions from closeSomeHandle. It's only the case where bracket has 2 exceptions to choose from that's ambiguous, and I'm saying that there's a fair amount of code out there that'd prefer to see the first one. Your point about ^C gets us into an even grayer area -- maybe code would prefer to propagate whichever of the 2 exceptions is asynchronous, or define a criterion to choose which exception is more serious, who knows. All these behaviors are easy to implement using the building blocks that Control.Exception exports right now, you're right. So I'm free to build my own bracket variants with different behavior and that's what I'll do. I was just wondering if the default behavior that bracket/onException provide (which are themselves built from catch/block/unblock) is the one that most people want. Thanks, -Brian _________________________________________________________________ Microsoft brings you a new way to search the web. Try Bing™ now http://www.bing.com?form=MFEHPG&publ=WLHMTAG&crea=TEXT_MFEHPG_Core_tagline_… bing_1x1

1 0

Exceptions during exception unwinding
by Brian Bloniarz 01 Oct '09

01 Oct '09

I had a question about onException & friends: what's the rationale for having: (error "foo") `onException` (error "bar") give bar and not foo? I.e. why does an exception raised during exception handling get propagated past the exception that triggered the handler? Most examples I can think for exception unwinding code would prefer the original exception be propagated -- for example, HDBC has a function which rolls back a DB transaction on exception; it implements it like so: > withTransaction conn func = > do r <- onException (func conn) doRollback > commit conn > return r > where doRollback = > -- Discard any exception from (rollback conn) so original > -- exception can be re-raised > Control.Exception.catch (rollback conn) doRollbackHandler > doRollbackHandler :: SomeException -> IO () > doRollbackHandler _ = return () IMHO, it'd be easier to just write: > withTransaction conn func = > do r <- onException (func conn) (rollback conn) > commit conn > return r This same argument applies to bracket, bracket_, bracketOnError & finally; even the common: > bracket openSomeHandle closeSomeHandle doAction If some error arises during doAction, there's a chance closeSomeHandle might fail (even a good chance, given that exception unwinding paths are usually poorly tested), and probably doAction has more accurate information about what went wrong than closeSomeHandle. This is just a thought; I hadn't seen this discussed somewhere. I know for example that Java has the same approach as the current Control.Exception, so there must be good arguments for that too. One that I can think of: using onException to rethrow an exception as a different type, though that's what mapException is for, correct? Thanks, -Brian _________________________________________________________________ Microsoft brings you a new way to search the web. Try Bing™ now http://www.bing.com?form=MFEHPG&publ=WLHMTAG&crea=TEXT_MFEHPG_Core_tagline_… bing_1x1

3 3

Fwd: Uniplate + strict fields = fail. Why?
by Dmitry Astapov 01 Oct '09

01 Oct '09

Hi, I've been playing with generics in general (pardon the pun) and Uniplate in particular, and found out that strict data fields somehow derail Uniplate. Observe: === code === {-# LANGUAGE DeriveDataTypeable #-} module Test where import Data.Generics (Data(..),Typeable(..)) import Data.Generics.PlateData import Data.ByteString import Data.ByteString.Char8 as C data Foo = Foo String deriving (Show, Data, Typeable) tst1 = [ Foo "a", Foo "b" ] test1 = [ show x | Foo x <- universeBi tst1 ] -- *Test> test1 -- ["\"a\"","\"b\""] data Bar = Bar ByteString deriving (Show, Data, Typeable) tst2 = [ Bar (C.pack "a"), Bar (C.pack "b") ] test2 = [ show x | Bar x <- universeBi tst2 ] -- *Test> test2 -- *** Exception: Prelude.undefined === end of code === First, I thought that instance of Data for ByteString is somehow deficient, but this is not the case. If you change definition of Foo to "data Foo = Foo !String", you would get the same error with "Prelude.undefined". Since all fields in ByteString constructors are strict, I have no joy trying to use it with Uniplate. Howere, my type-foo is not strong enough to understand what's wrong. Could someone give me a hint? PS ghc 6.10.4 uniplate 1.2.0.3 bytestring 0.9.1.4 PPS Neil Mitchell is receiving a copy of this email -- Dmitry Astapov

2 1

Re: [Haskell-cafe] Any generic serializer to String? was: Any working example of using genericserialize?
by Dimitry Golubovsky 01 Oct '09

01 Oct '09

Hi, On 9/30/09, Jason Dagit <dagit(a)codersbase.com> wrote: [skip] > Seems like using withList is wrong or the deserializer is simply buggy. It > certainly doesn't work the way I would expect SExp reading to work. I also > notice from reading the source on hackage that there may not be any tests > for this package and it is a 0.1 release. I'd contact the author, as it > seems there is a deficiency in the documentation or a bug in the > implementation. Thanks Jason for trying this. The genericserialize package is probably not finished yet. What else exists that could be used to serialize in generic way (i. e., anything that is an instance of Data and Typeable) into a string? It does not need to be very efficient as structures to be serialized are not huge (but may be pretty complex), and serialization is a part of an utility not to be used frequently. It only needs to "just work". One thing I thought of was to serialize to JSON (there is a generic serializer in one of packages although I did not test it other way) which has higher overhead than S-expressions though. Any other thoughts? Thanks. -- Dimitry Golubovsky Anywhere on the Web

4 5

ANNOUNCE: SourceGraph 0.5.1.0
by Ivan Lazar Miljenovic 01 Oct '09

01 Oct '09

This is an updated version of my graph-theoretic static analysis tool for Haskell, SourceGraph. This version is available from http://hackage.haskell.org/package/SourceGraph-0.5.1.0 (now with docs on the Hackage page!). This version provides the ability to pass in a single Haskell source file rather than a Cabal file for analysis purposes. Note that the Cabal version is still preferred as it is better able to determine the project name and which modules are exported: when using a single source file, that file is presumed to be the only exported module and its module name is used as the overall project name. This feature was requested by Curt Sampson. -- Ivan Lazar Miljenovic Ivan.Miljenovic(a)gmail.com IvanMiljenovic.wordpress.com

1 0

Journals on Haskell and FP?
by Eugene Kirpichov 01 Oct '09

01 Oct '09

Hi. I was going to add a reference to the recently born Russian journal "Practice of functional programming" (http://fprog.ru/ ; had its 1st issue in July and 2nd was Sep.28) to haskellwiki into a section devoted specifically to journals, but it turned out there is no such section and, consequently, no information on journals: just books, tutorials and research papers. I think this is very valuable information and it's a shame that it's not listed on haskellwiki. So, I added such a subsection to http://haskell.org/haskellwiki/Books_and_tutorials#Journals and added a reference to Monad.Reader (the only other openly available journal on FP that I am aware of) , and I encourage the community to mention some more journals there. I also encourage the Russian readers who have not yet seen the aforementioned journal to give it a look :) -- Eugene Kirpichov Web IR developer, market.yandex.ru

1 0

error on "--++ bla bla bla"
by Hong Yang 01 Oct '09

01 Oct '09

Hi, I got an error if one of lines reads "--++ bla bla bla" where I tried to comment, but "-- ++ bla bla bla" (notice the space after "--") is OK. Do you think this revealed a tiny bug in the GHC compiler (I am using Windows Haskell Platform 2009.2.0.2)? Thanks, Hong

5 7

combinatorial search with running bound
by Michael Mossey 30 Sep '09

30 Sep '09

I have a combinatorial search problem that requires a running lower bound to be tracked in order to prune the search. I have enough Haskell experience to know how to do a combinatorial search, for example with list compresions or the list monad, but I don't know how to keep a running lower bound. The problem is: I have two groups of boxes, and need to figure out how closely the centers of the groups can be brought left-right. For example, 55 11111 55 11111 44 22 44 22 + <- how close? -> + 33333 6666 33333 6666 33333 The left group consists of boxes 1, 2, and 3, which have both a size and a position (the position is relative to the center of the group, represented with the +). The right group has boxes 4, 5, and 6. The problem is to determine how closely the groups can be brought together without any boxes intersection. The basic algorithm is to consider each pair of boxes and ask if they have any "vertical overlap"---if so, figure out how closely they can be brought together without intersecting, otherwise ignore them. Then take the maximum of those numbers. -- (Here assume lrSeparation returns minBound for boxes that don't have -- vertical intersection.) boxesSep :: [Box] -> [Box] -> Int boxesSep lefts rights = maximum [ lrSeparation l r | l <- lefts, r <- rights ] However, this algorithm can be improved by pruning. - Define the 'left extent' of a box by how far its left edge sticks out to the left of the group center. Similarly the 'right extent'. - Sort the list of left boxes in the order of decreasing right extent. Sort the list of right boxes in order of decreasing left extent. - Consider pairs of boxes as a kind of outer loop on the left boxes, and inner loop on the right boxes. - Track the current maximum required separation, which is a lower bound on the final answer. - If at any point in the inner loop, the right extent has gotten so small that there's no way you could find a new maximum, skip the rest of the inner loop (skip the remainder of the right boxes). Here's my attempt to write this using a state monad. There's probably a more idiomatic way to do it. -- This is state used in the state monad. data SearchState = SearchState { -- running maximum: ssMaximum :: Int -- remember the full list of right boxes -- so we can initiate a new outer loop , ssRights :: [Box] } boxesSep2 :: [Box] -> [Box] -> Int boxesSep2 lefts rights = let ls = sortBy ((flip compare) `on` rightExtent) lefts rs = sortBy ((flip compare) `on` leftExtent) rights in fst $ runState (boxesSep2' ls rs) (SearchState minBound rs) boxesSep2' :: [BoxBounds] -> [BoxBounds] -> State SearchState Int -- Termination of algorithm: boxesSep2' [] _ = gets ssMaximum -- Initiate a new inner loop: boxesSep2' (l:ls) [] = do rights <- gets ssRights boxesSep' ls rights -- Common case: boxesSep2' lss@(l:ls) (r:rs) = do -- In this way of writing the code, we distinguish between the -- left/right separation which is the sum of the extents, and the -- question of whether there is vertical overlap. let v = isVerticalOverlap l r sep = lrSeparation l r ss <- get let max = ssMaximum ss if sep <= max then boxesSep' ls (ssRights ss) --Here we "prune" (initiate new inner loop) else do -- Update max is needed: when v (put ss { ssMaximum = sep }) boxesSep' lss rs So if there is a better way to do this, I'm all ears.

3 5