February 2008 - Haskell-Cafe

More powerful error handling
by Philippa Cowderoy 18 Feb '08

18 Feb '08

For a while I've been meaning to propose something along the lines of this class: class (MonadError m e, MonadError m' e') => MonadErrorRelated m e m' e' | m -> e, m' -> e', m e' -> m' where catch' :: m a -> (e -> m' a) -> m' a rethrow :: m a -> (e -> e') -> m' a with an example instance being: instance (Error e, Error e') => MonadErrorRelated (Either e) e (Either e') e' where catch' (Right v) _ = Right v catch' (Left e) h = h e rethrow c ef = catch' c (throw . ef) (yep, that definition of rethrow would make a sensible default and there's a default catch' in terms of rethrow too) The nicest use would be for converting between a more specific error type and a more general one that handles a wider range of errors - enabling us to keep tighter track of which errors are possible in a given piece of code. Bonus points for using it together with polymorphic variants where rethrow becomes rather trivial. The following two functions or close variants might also be useful: catchMaybe :: (MonadError m ()) => Maybe a -> m a catchMaybe Nothing = throwError () catchMaybe (Just a) = return a catchEither :: (MonadError m e) => Either e a -> m a catchEither (Left err) = throwError err catchEither (Right a) = return a No doubt there are some names that could use tweaking. As far as I'm concerned you can count me in the camp of people that resent the existing MonadError instances all requiring an Error instance too, it makes things messier when you have access to something like this. But I guess that's because fail is begging for the following definition: fail = fail -- fail is made of fail -- flippa(a)flippac.org There is no magic bullet. There are, however, plenty of bullets that magically home in on feet when not used in exactly the right circumstances.

2 1

problem with collection (container) class
by Leandro Demarco Vedelago 18 Feb '08

18 Feb '08

Hi! I'm pretty (not to say very) new to haskell and i've to create a new class named container that includes types that hold other values, more specific, i have "created" this two types: data Abb a b = Branch a b (Abb a b) (Abb a b) | Leaf and data ListAssoc a b = Node a b (ListAssoc a b) | Empty and implemented some common functions (add, search, delete, empty,etc). So when I was asked to create this new class I crashed against a big problem, or at least for me. My first attempt was: class Container c where empty :: c but when I had to implement "add" I tried add :: c -> a -> b -> c although I was almost sure that it wouldn't work, so I realized that I had to give Container not one but three parameters, the container and the types of values that the container saved so I started searching and I found similar cases, but the difference iis that in this cases the class was defined as follows: class Container c e | c->e where empty :: c insert :: c -> e -> c member :: c -> e -> Bool but my particular problem here is that the types I designed hold two values of different type and these holds just one value. Besides I knew nothing about functional dependency used in here and I keep knowing almost nothing about them, but I tried something like this: class Container c a b |c -> a, c -> b where empty :: c add :: c -> a -> c search :: c -> a -> Maybe b del :: c -> a -> c toListPair :: c -> [(a,b)] instance Container Abb a b where empty = Leaf add Leaf x y = Branch x y Leaf Leaf add arb@(Branch ni nd ri rd) x y |x == ni = arb |x > ni = Branch ni nd ri (add rd x y) |otherwise = Branch ni nd (add ri x y) rd search Leaf x = Nothing search (Branch ni nd ri rd) x |x == ni = Just nd |x > ni = search rd x |x < ni = search ri x but when I try to load it in WinHugs I get the following error message: - Instance is more general than a dependency allows *** Instance : Container Abb a b *** For class : Container a b c *** Under dependency : a -> b and as I have stated above my knowledge about dependencies is almost null, not to say null, so I don´t even have an idea where the error is. A suggestion that I've received was to change the type of Abb for data Abb (a,b) = Branch a b (Abb (a,b)) (Abb (a,b)) | Leaf and declare container class with just two parameters like I found in all pages I visited. I have not tried this yet, as I still have hope that what I intend to do is possible. Well if you have any suggestions I'd appreciate you send it to me and sorry for bothering you and my english, but i'm "spanish-speaker".

4 4

Designing DSL with explicit sharing [was: I love purity, but it's killing me]
by oleg＠okmij.org 17 Feb '08

17 Feb '08

Matthew Naylor wrote: > it's not immediately clear (to me at least) how efficient your method > will be in "practice". Any method based on common sub-expression > elimination surely must inspect every node in the flattened graph. In > the worst case, an acyclic graph containing n nodes could have 2^n > nodes when flattened to a tree: > > tricky 0 = constant 0 > tricky d = add g g > where > g = tricky (d-1) It should work quite well in practice, as demonstrated below. Once our DSL is extended with a let form (so the user can declare the intention to share results of computations rather than computations themselves), tricky code becomes trivial. The code remains declarative, safe and pure, and, save for the (cosmetic) lack of the monomorphism restriction, Haskell98. The well-commented code is available at http://okmij.org/ftp/Haskell/DSLSharing.hs First a few comments on the tricky code. It is true that (absent programmer's proclamations and code structuring forms) a complete method of common sub-expression elimination must inspect every sub-expression in the program. That inspection must include at least one comparison of a node with some other nodes. As I understand the original problem had less to do with the number of comparison but more to do with the cost of a single comparison. In an impure language, we can use constant-time physical equality. It is usually provided natively as pointer comparison, and can be trivially emulated via mutation. The original poster used pure Haskell and the following representation for the program graph: data Expression = Add Expression Expression | Sub Expression Expression | Variable String | Constant Int deriving Eq Here, the derived equality operation, albeit pure, no longer takes constant time. Comparing nodes near the root of a deep tree really takes a while. As the previous message on DSL with sharing showed, one can do common sub-expression elimination and the conversion of the program tree to a DAG using a constant-time node equality operation, without sacrificing purity. The tricky function is a metaprogram that builds a large DSL program: (tricky 12) yields a single DSL expression with 8191 nodes. Such humongous expressions with thousands of components are unlikely to be written by human programmers (although can be easily generated). Many compilers will choke if we submit a program with one large expression. (Incidentally, the previously posted code converts the tree (tricky 12) to a 12-node DAG in 0.25 secs on 1GHz Pentium). The reason we can compile much larger projects is because we structure them, into compilation units, functions, let-blocks. The structure gives the common sub-expression eliminator and other optimizer phases much needed hints and so significantly limits the search space. For example, hardly any compiler searches for common sub-expressions across compilation units. More importantly for us here, forms like let-expressions let the programmer declare that the results of certain computations be shared. Although the tricky code also contains a let-expression (masqueraded as 'where'), the sharing there occurs at the meta-level and benefits the generator rather than the generated program. We share code generators rather than the generated code. The importance of placing 'let' in the right phase has been extensively discussed in http://www.cs.rice.edu/~taha/publications/conference/pepm06.pdf also in the context of a DSL (for dynamic programming). In our case, we need to give our DSL programmer a way to state their intention on sharing results of DSL computations. The programmer declares certain expressions common, and thus greatly helps the compiler as well as human readers of the code. As Chung-chieh Shan has pointed out, we need to introduce a "let" construct in the _embedded_ language. Since our DSL already has (concrete) variables with string names, we can extend our language thusly: let_ "v1" (add (constant 1) (variable "x)) (add (variable v1") (variable "v1")) We chose a different way: higher-order abstract syntax. We use variables of the metalanguage (that is, Haskell) as let-bound variables. Our language is now defined as > class Exp repr where > constant :: Int -> repr Int > variable :: String -> repr Int > add :: repr Int -> repr Int -> repr Int > sub :: repr Int -> repr Int -> repr Int > let_ :: repr a -> (repr a -> repr b) -> repr b -- like flip ($) Here are simple programs in our language > a = add (constant 10) (variable "i1") > b = sub (variable "i2") (constant 2) > c = add a b > d = add c c > e = add d d -- "e" now as 16 leaf nodes. > e' = let_ d (\x -> add x x) The programs (e) and (e') evaluate to the same integer given the same environment for "i1" and "i2". The two programs differ in how sharing is declared. The program (e) uses the identifier (d) twice; even if GHC shares the corresponding expressions rather than copies them (a Haskell system is not obliged to share anything: sharing is not observable in Haskell98), what GHC shares are metalanguage computations. Although the metalanguage (Haskell) is pure, the object language does not have to be. Indeed, the common-subexpression elimination, when considered as an evaluation of an object expression, is an impure evaluation. The same object expression may give, in different contexts, different results (that is, compile to different assembly code). In the case of (e'), we explicitly stated that "d" is a common sub-expression. It must be executed once, with the results shared. The difference is easy to see if we print e and e': *DSLSharing> test_showe "10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2" *DSLSharing> test_showe' "let v0 = 10 + i1 + i2 - 2 + 10 + i1 + i2 - 2 in v0 + v0" Higher-order syntax for let_ (see e') seems better than that based on concrete variable names. As test-showe' demonstrates, we can easily convert from higher-order abstract to the concrete syntax. The converse is much more cumbersome. We easily extend the previously written common sub-expression eliminator by adding the clause for let_ > instance Exp A where > ... > let_ e f = A(do > x <- unA e > unA $ f (A (return x))) And that is it. We can write the tricky function with the explicit sharing: > tricky' 0 = constant 0 > tricky' d = let_ (tricky' (d-1)) (\g -> add g g) > > test_tricky' n = runState (unA (tricky' n)) exmap0 *DSLSharing> test_tricky' 12 (AAdd 12, ExpMaps {hashcnt = 13, ctmap = fromList [(0,0)], vrmap = fromList [], admap = fromList [(1,(AConst 0,AConst 0)),(2,(AAdd 1,AAdd 1)), (3,(AAdd 2,AAdd 2)),(4,(AAdd 3,AAdd 3)),(5,(AAdd 4,AAdd 4)), (6,(AAdd 5,AAdd 5)),(7,(AAdd 6,AAdd 6)),(8,(AAdd 7,AAdd 7)), (9,(AAdd 8,AAdd 8)),(10,(AAdd 9,AAdd 9)),(11,(AAdd 10,AAdd 10)), (12,(AAdd 11,AAdd 11))], sumap = fromList []}) (0.01 secs, 0 bytes) Indeed it takes negligible time. In fact, test_tricky' 12 takes (0.01 secs, 561860 bytes) test_tricky' 100 takes (0.03 secs, 1444888 bytes) If the DAG corresponding to (test_tricky' 100) were converted to a tree, it would have had 2^101 -1 nodes (which is more than 10^31).

5 4

Re: [Haskell-cafe] Designing a Parser
by PR Stanley 17 Feb '08

17 Feb '08

Actually, I haven't sent this question to the list before. So you're in no danger of repeating yourself. Thanks for your kind reply anyway Paul At 07:03 17/02/2008, you wrote: >On Feb 17, 2008 6:20 AM, PR Stanley <prstanley(a)ntlworld.com> wrote: > > I can't think of an elegant pattern for the last function. I've > > already tried set comprehension. However, something tells me that the > > answer may lie in a complex recursive pattern. I'm not afraid of > > complex solutions but I naturally see them as an easy way out. It's > > those clear simple patterns that separate men from mice. :-) I'd be > > grateful for any advice on this and indeed my approach as a whole. If > > you think I'm on the wrong path from the start feel free to let me > > know. I'm not asking for the answer. I'd like to work that out by > > myself although some guidance would be most appreciated. > >Yes, I definitely think you're on the wrong path from the start. In >high school when I was learning C++ I wrote an arithmetic expression >parser in something like this fashion. I scanned the input for the >first opening bracket, then I walked forward to the matching closing >bracket and extracted the subexpression and evaluated it. > >The approach turned out to be both complicated and inefficient. I >think the biggest problem was that it didn't scale well with >implementation complexity; eg. to add support for prefix functions >like sin() was almost impossible. Think about how you would go about >doing such things using your approach. > >I think I've seen you ask questions relating to this on the list >before, and at the risk of repeating others, I suggest the ReadS in >the Haskell Prelude. You get the benefit of it being a clean, >top-down solution as well as the benefit of having a lot of primitive >Haskell types already implemented for you (such as Integers). > >I'll describe the approach again, describing the combinators, and then >afterward showing how you might use them to accomplish this problem. >I'll leave the details up to you, since you can learn a lot by >implementing combinator libraries like this. > >First, you build a bunch of functions which are "parsers". A "parser" >is just a function of type String -> [(a,String)] for some type 'a'; >that is, it takes a string and returns a list of "parses", where a >parse is the value parsed paired with the remainder of the string. So >if you have a function: > > parseInt :: String -> [(Int,String)] > >Then you can expect this result: > > parseInt "123 hello world" = [(123, " hello world")] > >Or maybe even: > > parseInt "123 hello world" = [(123, " hello world"), (12, "3 hello >world"), (1, "23 hello world")] > >But that latter behavior is not recommended in this case (i.e. it is >advisable force int parsing to be greedy). > >Then to combine parsers you can use some combination operations: > > sequenceParsers :: (String -> [(a,String)]) -> (a -> String -> >[(b, String)]) -> String -> [(b,String)] > >That one may be easier to see if you use the built-in type synonym >ReadS a = String -> [(a, String)]: > > sequenceParsers :: ReadS a -> (a -> ReadS b) -> ReadsB > >The second argument here is a function, because we have already parsed >the first argument and know its value, so the second argument ought to >be able to use it. We can also write: > > alternateParsers :: ReadS a -> ReadS a -> ReadS a > >Which gives all valid parses that the first one recognizes >concatenated with all valid parsers that the second one recognizes. > >Implementation of these combinators is left to you. Since the types >of these functions are quite general, you can use a type-directed >approach (i.e. if your implementation uses all available data and it >typechecks, it's probably correct). > >Now that you have these, how do you use them to actually parse >something? Let's parse simple logical expressions. First we need a >data structure to parse into: > > data Exp > = Variable String > | AndExp Exp Exp > | OrExp Exp Exp > >Let's do it with a top down coding strategy: write a function to >parse an expression using whatever helper functions we need but >haven't written yet :-) > > parseExp :: ReadS Exp > parseExp = parseAnyOf [ parseVariable, parseAndExp, parseOrExp ] > >Where we haven't written parseAnyOf yet. Write that inductively on the list: > > parseAnyOf :: [ReadS a] -> ReadS a > parseAnyOf [] = \input -> [] > parseAnyOf (p:ps) = alternateParsers p (parseAnyOf ps) > >And jump in to the next thing we haven't written, parseVariable: > > parseVariable :: ReadS Exp > parseVariable = mapParser Variable parseString > >mapParser doesn't actually parse anything, it just parses whatever its >argument does and applies a function to the result: > > mapParser :: (a -> b) -> ReadS a -> ReadS b > mapParser :: (a -> b) -> (String -> [(a,String)]) -> String -> > [(b,String)] > >I rewrote the type signature to help guide your implementation. > >That should get you started, and show you how the approach usually >goes. You seem to already get the idea of writing many small >functions and composing them together. This is the same idea, except >the functions are abstracting the problem more. > >Luke

2 1

GHC + interactive input/output
by Jonathan Cast 17 Feb '08

17 Feb '08

$ cat > foo.c #include <stdio.h> int main() { char s[1024]; printf("gsi> "); gets(s); printf("%s\n", s); return 0; } $ make foo cc gsi.c -o gsi $ ./foo warning: this program uses gets(), which is unsafe. gsi> hello hello $ cat > foo.hs main = do putStr "gsi> " s <- getLine putStrLn s $ ghc foo.hs -o foo $ ./foo hello gsi> hello (This is on MacOS X). It strikes me that GHC is being extraordinarily unhelpful here. Is there anyone on the planet who ever actually wants this behavior? jcc

13 25

ANN: winerror-0.1
by Felix Martini 17 Feb '08

17 Feb '08

This is a small package for error handling when making foreign calls to the Windows API. The functions are similar to those in Foreign.C.Error, e.g. throwWinErrorIf corresponds to throwErrnoIf. Dynamic io errors are thrown with GHC so the catchWinError function can catch specific Windows error codes and handle them. Regards, Felix

1 0

Designing a Parser
by PR Stanley 17 Feb '08

17 Feb '08

Hi friends I'm in the process of designing a series of functions which you might collectively call a parser. The idea is to evaluate an input string for a proof software. So a typical input string would be something like "(P & Q) -> q". There are a number of things to consider here, for example, does the string belong to the domain which is a subset of the 7-bit ASCII table, starting from 32 and ending at 126. Then you need to remove all space characters to make things a bit simpler. Next we find out if the logical sentnece is bracketted. I start this by looking for a bracket in the string. If true then I isolate the brackets into a new set in order to spot any odd ones. Here is what I've done so far: domain :: [Char] domain = [x | x <- ascii7, x >= ' ' && x <= '~'] where ascii7 = ['\0'..'\127'] -- a legal input character is a member of domain. isInDomain :: Char -> Bool isInDomain x = any (==x) domain -- a legal input string is a subset of domain. isSubset :: [Char] -> Bool isSubset input = all isInDomain input -- delete spaces for easier parsing. noSpace :: [Char] -> [Char] noSpace input = [x | x <- input, x /= space] where space = ' ' -- set of brackets brackets = ['(', ')', '[', ']', '{', '}'] -- Are there any brackets in input? hasBrackets :: [Char] -> Bool hasBrackets input = or [True | x <- input, any (==x) brackets] -- filter all brackets into a subset. getBrackets :: [Char] -> [Char] getBrackets input = [x | x <- input, any (==x) brackets] -- What are matching brackets? areMatched :: Char -> Char -> Bool areMatched '(' ')' = True areMatched '[' ']' = True areMatched '{' '}' = True areMatched _ _ = False -- Can all the brackets in input be paired up? allMatched :: [Char] -> Bool I can't think of an elegant pattern for the last function. I've already tried set comprehension. However, something tells me that the answer may lie in a complex recursive pattern. I'm not afraid of complex solutions but I naturally see them as an easy way out. It's those clear simple patterns that separate men from mice. :-) I'd be grateful for any advice on this and indeed my approach as a whole. If you think I'm on the wrong path from the start feel free to let me know. I'm not asking for the answer. I'd like to work that out by myself although some guidance would be most appreciated. Thanks, Paul

2 1

GHC strange behavior
by Ruslan Evdokimov 16 Feb '08

16 Feb '08

Hi, all! I have strange GHC behavior. Consider the code: import Control.Parallel main = print (o `par` (fromInteger e) / (fromInteger o)) where [e,o] = map sum $ map (`filter` numbers) [even, odd] numbers = [1..10000000] When it compiled without threaded it has 19068 ms to run, 396 Mb total memory in use and %GC time 88.2%, the same with -threaded and +RTS -N1, but with +RTS -N2 it takes only 3806 ms to run, 3 Mb total memory in use and %GC time 8.1%. Why it so? It's a bug or I missed something? I test it on dual-core Athlon X2 4200+ 2Gb running 64bit Gentoo system. gcc 4.2.2 and ghc 6.8.2. -- Ruslan

4 8

Haskell project support and analysis on ohloh
by Don Stewart 16 Feb '08

16 Feb '08

Recently ohloh.net added support for analysing haskell code. You can see a range of Haskell projects analysed on ohloh here: http://www.ohloh.net/projects/search?q=haskell Including: http://www.ohloh.net/projects/11789?p=nhc98 http://www.ohloh.net/projects/6869?p=xmonad http://www.ohloh.net/projects/4078?p=HUGS http://www.ohloh.net/projects/6949?p=yi http://www.ohloh.net/projects/10496?p=bytestring http://www.ohloh.net/projects/11766?p=parsec http://www.ohloh.net/projects/11779?p=mtl http://www.ohloh.net/projects/11729?p=binary http://www.ohloh.net/projects/11769?p=X11 http://www.ohloh.net/projects/11790?p=array Which gives rise to some fun 'reports' (and also helps non-Haskell people notice that there are lots of Haskell projects, and developers with experience): xmonad: " Over the past twelve months, 34 developers contributed new code to xmonad. This is one of the largest open-source teams in the world, and is in the top 2% of all project teams on Ohloh. " nhc98: "nhc has a mature, well established code base. The first lines of source code were added to nhc98 in 1999. This is a relatively long time for an open source project to stay active, and can be a very good sign. A long source control history like this one shows that the project has enough merit to hold contributors's interest for a long time. It might indicate a mature and relatively bug-free code base, and can be a sign of an organized, dedicated development team. " Now, they don't support analysing darcs repos, but the do support git, and with darcs-to-git and darcs2git I've been able to (slowly) get a bunch of repos into git form. You can find the git conversions here, if you're interested: http://www.cse.unsw.edu.au/~dons/git/ (git clone http://www.cse.unsw.edu.au/~dons/git/parsec for example). GHC, base and lambdabot are still in the process of conversion. If you want to do your own conversions, I suggest trying darcs2git first, which is very fast. If that doesn't suceed, try darcs-to-git, which is *much* slower (damn ruby), but seems to be more robust. You can then register the resulting git repo for analysis. The global language statistics, and individual Haskell statistics will update in the next few hours, I suspect. http://www.ohloh.net/languages/38 Though at the time of writing they appear out of date. Happy hacking. -- Don

1 0

Help with error
by Jeff φ 16 Feb '08

16 Feb '08

Hello, I get an error message on the code below with GHC. I can't figure out how to get rid of the error. I'd appreciate suggestions on how to fix this. (BTW, the code may look overly combersome because I stripped out anything unnecessary to demonstrate the error.) {-# OPTIONS_GHC -fglasgow-exts -fbreak-on-exception -fallow-undecidable-instances #-} import qualified Prelude import Prelude import Data.Array.IArray class Sequence seq where slength :: (seq e) -> Int snull :: (seq e) -> Bool shead :: (seq e) -> e stail :: (seq e) -> (seq e) instance Sequence [] where slength = length snull = null shead = head stail = tail class From_seq t where from_seq :: (Sequence seq) => (seq e) -> (t e) instance From_seq [] where from_seq seq | snull seq = [] | otherwise = (shead seq) : (from_seq (stail seq)) from_seq' seq | snull seq = (listArray (0,-1) []) | otherwise = listArray (0,fromIntegral (slength seq) -1) (from_seq seq) {- When I uncomment this out, I get the error messages: Error.hs:41:19: Could not deduce (IArray a e) from the context (From_seq (a i), Ix i, Num i, IArray a e1, Sequence seq) arising from a use of `from_seq'' at Error.hs:41:19-31 instance (Ix i, Num i, IArray a e) => From_seq (a i) where from_seq seq = from_seq' seq -} When I load the module above, I can evaluate the folloing in GHCI *Main> from_seq' [0..5] :: Array Int Double array (0,5) [(0,0.0),(1,1.0),(2,2.0),(3,3.0),(4,4.0),(5,5.0)] But, I'd like to do this with the From_seq class. If anyone has suggestions, I'd be grateful. Thanks, Jeff

2 2