November 2006 - Haskell-Cafe

Wiki page for rewrite rules tips, types and tricks
by dons＠cse.unsw.edu.au 20 Nov '06

20 Nov '06

After suggesting solutions based on rewrite rules to three different questions this week, I though maybe we better have a wiki page on using rewrite rules for non-traditional ad-hoc tricks. http://haskell.org/haskellwiki/Playing_by_the_rules If you've used rewrite rules for something fun (other than implementing a major deforestation system), please add it to the page. -- Don

4 3

Arrows tutorial
by Tim Newsham 20 Nov '06

20 Nov '06

Small arrows tutorial (sorta, I'm learning myself and trying to doc as I go): http://www.thenewsh.com/~newsham/x/arrow.txt comments welcome. I ran into a type issue I couldnt resolve. I'd love any comments on that (documented near the bottom, liftA2'). Also, I'd like to put some info about ghci -farrows syntax when I figure that stuff out. If anyone feels like translating some examples into do-notation or coming up with new examples that showcase do-notation, please post em or send them to me. Tim Newsham http://www.thenewsh.com/~newsham/

2 2

jhc, whole program optimizing compiler.
by szefirov＠ot.ru 20 Nov '06

20 Nov '06

Do anyone had any experience with JHC? I tried to install it second time and again get an error during library build. It's a pity, we need a speed in our very lazy code. ;)

2 1

Cabal ^M bug
by Vyacheslav Akhmechet 19 Nov '06

19 Nov '06

Cabal appears to have an end-of-line bug. If the .cabal file is created on Windows and the project is installed on a Unix system, the resulting executable ends up having ^M at the end because Cabal doesn't properly handle Windows line termination. If the .cabal file is converted to Unix style, everything installs as expected. I tried to submit a ticket to Cabal via the wiki but couldn't authenticate (guest/haskell, as says on the web page, doesn't seem to work). Also HackageDB link seems to be down. I'm not sure who's maintaining the project, so I'm emaling here. Thanks, - Slava.

1 0

Type signatures in FFI exported functions
by Alfonso Acosta 19 Nov '06

19 Nov '06

Hi, The FFI doesn't allow using type signatures in exported functions. Imagine this simplified example class Foo a where action1 :: a -> IO() action2 :: a -> IO() exportable :: Foo a => StablePtr a -> IO() exportable ptr = do deref <- deRefStablePtr ptr action1 deref Currently the FFI doesn't allow to export exportable due to the type signature. But I don't really understand why isn't it feisable. In my code I solved the problem by quantifying existentially data CFoo = forall a.Foo a => CFoo a instance Foo CFoo where action1 (CFoo a) = action1 a action2 (CFoo a) = action2 a exportable' :: StablePtr CFoo -> IO() exportable' ptr = do deref <- deRefStablePtr ptr action1 a Another way to fix it would be, unlike standard Haskell98, allowing dictionaries to be packaged in data constructors data CFoo' a = Foo a => CFoo' a instance Foo (CFoo' a) where action1 (CFoo' x) = action1 x action2 (CFoo' x) = action2 x exportable'' :: StablePtr (CFoo' a) -> IO() exportable'' ptr = do deref <- deRefStablePtr ptr action1 deref As far as I know, the later option has only been recently made available for GADTs in GHC, does anyone know away of doing it with normal ADT? Does anyone know a better workaround? Thanks in advance, Alfonso Acosta

1 0

Debugging partial functions by the rules
by dons＠cse.unsw.edu.au 18 Nov '06

18 Nov '06

So all this talk of locating head [] and fromJust failures got me thinking: Couldn't we just use rewrite rules to rewrite *transparently* all uses of fromJust to safeFromJust, tagging the call site with a location? To work this requires a few things to go right: * a rewrite rule * assertions * and rewrite rules firing before assertions are expanded Let's try this. Consider the program: 1 import qualified Data.Map as M 2 import Data.Maybe 3 4 main = print f 5 6 f = let m = M.fromList 7 [(1,"1") 8 ,(2,"2") 9 ,(3,"3")] 10 s = M.lookup 4 m 11 in fromJust s When we run it we get the not so useful error: $ ./A A: Maybe.fromJust: Nothing Ok, so we have a few tricks for locating this, using LocH (http://www.cse.unsw.edu.au/~dons/loch.html) we can catch an assertion failure, but we have to insert the assertion by hand: 1 import Debug.Trace.Location 2 import qualified Data.Map as M 3 import Data.Maybe 4 5 main = do print f 6 7 f = let m = M.fromList 8 [(1,"1") 9 ,(2,"2") 10 ,(3,"3")] 11 s = M.lookup 4 m 12 in safeFromJust assert s 13 14 safeFromJust a = check a . fromJust Which correctly identifies the call site: $ ./A A: A.hs:12:20-25: Maybe.fromJust: Nothing Now, this approach is a little fragile. 'assert' is only respected by GHC if -O is *not* on, so if we happened to try this trick with -O, we'd get: $ ./A A: Debug.Trace.Location.failure So lesson one: you have to do the bug hunting with -Onot. Currently there's -fignore-asserts for turning off assertions, but no flag for turning them on with -O, Simon, could this be fixed? Could we get a -frespect-asserts that works even with -O ? Ok, assuming this assert trick is used, can we get the compiler to insert the asserts for us? If so, this would be a great advantage, you'd just be able to switch on a flag, or import a debugging module, and your fromJusts would be transparently rewritten. With rewrite rules we do just this! So, to our initial unsafe use of fromJust, we add a rewrite rule: -- -- rewrite fromJust to a located version, and hope that GHC expands -- 'assert' after the rule fires.. -- {-# RULES "located fromJust" fromJust = check assert . myFromJust #-} This just tells the compiler to replace every occurence of fromJust with a assertion-throwing fromJust, should it fail. We have to use myFromJust here, to avoid rule recursion. -- -- Inlined to avoid recursion in the rule: -- myFromJust :: Maybe a -> a myFromJust Nothing = error "Maybe.fromJust: Nothing" -- yuck myFromJust (Just x) = x Ok, so can we get ghc to rewrite fromJust to the safe fromJust magicaly? $ ghc --make -Onot A.hs -fglasgow-exts -ddump-simpl-stats [1 of 1] Compiling Main ( A.hs, A.o ) 1 RuleFired 1 located fromJust Linking A ... Yes, the rule fired! GHC *did* rewrite our fromJust to a more useful fromJust. Running it: $ ./A A: A.hs:19:36-41: Maybe.fromJust: Nothing Looks good! But that is deceiving: the assert was expanded before the rule fired, and refers to the rewrite rule source line (line 19), not the fromJust call site (line 12). Now if we could just have the 'assert' token inserted into the AST before it was expanded, we'd be home and dry. Could this be done with TH? Or could we arrange for asserts in rewrite rules not to be expanded till later? Note that this is still a useful technique, we can rewrite head/fromJust/... to some other possibly more useful message. And if we can constrain the rule to fire in only particular modules, we may be able to narrow down the bug, just by turning on a rule. For example, adding: {-# RULES "located fromJust" fromJust = safeFromJust #-} safeFromJust s = case s of Nothing -> "safeFromJust: failed with Nothing. Ouch" Just x -> x will produce: $ ./A "safeFromJust: failed with Nothing. Ouch" So rewrite rules can be used to transparently alter uses of partial functions like head and fromJust. So, further work: * have 'assert' respected when -O is on * think up a technique for splicing in 'assert' via rewrite rules (or TH ...) such that the src locations are expanded after the rewrite, and correctly reflect the location of the splice point. Any ideas? -- Don

6 10

Re: Debugging partial functions by the rules
by oleg＠pobox.com 18 Nov '06

18 Nov '06

Donald Bruce Stewart wrote: > So all this talk of locating head [] and fromJust failures got me > thinking: > > Couldn't we just use rewrite rules to rewrite *transparently* > all uses of fromJust to safeFromJust, tagging the call site > with a location? I'm sorry for shifting the topic: I'm wondering if, rather than trying to make an error message more informative, we ought to make sure that no error will ever arise? The fromJust and `head of empty list' errors are totally equivalent to the dereferencing of zero pointer in C++ or NullPointerException in Java. It pains me to see that exactly the same problem arises in Haskell -- keeping in mind that already in C++ and Java one may exterminate these errors given right encapsulations. Languages like Cyclone or Cw use the type system to eliminate such errors. Surely Haskell can do something about this? This topic has been discussed at length on this list. It seems that the discussion came to the conclusion that eliminating head of the empty list error is possible and quite easy in Haskell. http://www.haskell.org/pipermail/haskell-cafe/2006-September/017915.html http://www.haskell.org/pipermail/haskell-cafe/2006-September/017937.html As to fromJust: would the world come to an end if this function is just not available? Oftentimes when we get the value of the type |Maybe a|, the algorithm prescribes the actions for the case if this value is Nothing. Thus the function `maybe', the deconstructor, seems to be called for. And if we are dead sure that the |Maybe a| value is definitely |Just smth| and we need to extract this |smth|, we can always write maybe (assert False undefined) id value I like how this phrase stands out in the code, to remind me to double-check my certainty about the value (and perhaps, to re-factor the code). Similarly for empty lists: it is often algorithmically significant as it is the base case for our recursion/induction. Thus, we have to make the null check according to the algorithm anyway. The type system can carry the result of such a test, so we don't have to repeat it. The functions head and tail should operate on the newtype NonemptyList -- in which case they are total. Other list functions may remain as they are, because we can always `forget' the NonemptyList tag. The run-time overhead is zero, the notational overhead is not much: writing a few extra `fromNonemptyList'. Compare with writing `fromIntegral', especially in the FFI-related code. The Haskell type system can do far more complex things, for example, solve the pervasive SQL injections and cross-site scripting problems: http://blog.moertel.com/articles/2006/10/18/a-type-based-solution-to-the-st… (This URL appeared on one of the recent Haskell Weekly News, btw). Surely we can do something about a far simpler problem of head [] and fromJust? We may have to adjust our coding styles a little. The adjustment doesn't appear extensive; besides, isn't the whole point of programming in Haskell is to think differently?

20 31

working with lists of couples
by Clara Zamolo 18 Nov '06

18 Nov '06

Hello, i'd like to write a function that given a list like [1,2,3,4...] returns a list of couple where the first element is the corresponding element of the string, and the second is the sum of the previous elements. An example: input: [1,2,3,4] output: [(1,0)(2,1)(3,3)(4,6)] The problem could seem trivial, and here's a first solution: buildCouples = snd . foldl op (0,[]) where op (v,xs) x = (v+x,xs++[(x,v)]) The problem is that this solution is quadratic, and I want a solution that take time n (2n is not good either). Any suggestion? Thanks, Clare.

4 4

Are associated types synonyms like type classes?
by Brian Smith 18 Nov '06

18 Nov '06

I read the easy parts of the "Associated Types with Class" and "Associated Type Synonyms" papers. An associated type synonym seems to kind of work similarly to a restricted form of class. In what way are the two following examples different? -- define a class with a type synonym, and a set of operations class A a where type B b foo :: a -> B b instance A Int where type B = Bool foo = (==0) -- define two classes, and an function that . class A a, B b where foo :: a -> b instance A Int, B Bool where foo = (==0) Also, has anybody written a paper on the differences between typeclasses + associated types and ML's module system + overloading? Thanks, Brian

4 5

Re[2]: [Haskell] I18N, external strings
by Bulat Ziganshin 18 Nov '06

18 Nov '06

Hello Axel, Friday, November 17, 2006, 11:27:00 AM, you wrote: > (l_ "Translate this") > is compiled into a C string constant, that GHC then turns lazily into a > list of characters, which l_ then turns into an array in C land to pass > to the gettext function, which, in turn, returns a new C string array > that has to be turned into a Haskell string again. So I'm glad Lennart > proposed to turn String into a class which would then make it possible > to pass a pointer to a contant C string to gettext. i'm not sure that you are right. GHC can perform compile-time computation of constant expressions. Don Bruce should know better, once he pointed out how a String constant can be turned into ByteString one at compile time -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

2 1