November 2006 - Haskell-Cafe

Updated School of Expression Sources?
by Justin Bailey 17 Nov '06

17 Nov '06

I downloaded the SOE sources from http://www.haskell.org/soe and found they were not compatible with the my version of WinHugs (Sep 2006). I have two questions: 1) Is an updated version of those sources available? 2) If not, would someone like to host mine? I updated all the source files so they at least load without error. Mostly it involved changing a few import statements. I also had to make some updates to the included Haskore files. Also, I found the some of the programs included crash Hugs without warning. For example, evaluating "test cball5" in the file "Fal.lhs" will crash Hugs after running for a few seconds, or if the mouse is moved over the window. Does anyone know why that may occur? Justin

3 2

Newbie; Can't Install Hat From Source
by Aditya Siram 17 Nov '06

17 Nov '06

Hi all, I have been trying to install Hat for the last couple of days but GHC does not recognize it as a package. I compiled 2.05 from source, but at the 'make install' step I see this error message: **Begin Output** ./configure --install Configuring for hat... [ 2.05 ] Starting with earlier config in targets/ix86-Linux/config.cache [ config: ix86-Linux/ by deech@ubuntu on 15 Nov 2006 ] (but cmdline options have precedence) -------- Looking for already-installed Haskell compilers: Looking for ghc... found 6.6 Looking for nhc98... (not found) Looking for hmake... found 3.13 You said you want to use ghc to build hat. Done. -------- Configuration report for hat. You are going to build hat with: ghc Executables need .exe suffix? no (detected) Testing for the glib library: no (using slower replacement) Installation directories are now created/checked. Install directory root is: /usr/local Hat interface files (.hx) go into: /usr/local/include/hat-2.05 (exists) Array.hx ...... Debug/Trace.hx Installing hat as a ghc package: Installing hat package for ghc under /usr/local/lib/hat-2.05/ix86-Linux/ghc-606 ghc-pkg: cannot find package hat <-----ERROR MESSAGE!!!!! Reading package info from stdin ... done. ghc-pkg: package hat-2.4 is already installed Scripts go into: /usr/local/bin (exists) hat-graph hat-trans hat-tools: hat-stack hat-check hat-observe hat-detect hat-delta hat-view hat-trail hat-anim hat-explore hat-cover black-hat hat-nonterm pretty-hat Executables go into: /usr/local/lib/hat-2.05/ix86-Linux (exists) config hat-anim hat-check hat-cover hat-delta hat-detect hat-explore hat-nonterm hat-observe hat-stack hat-trail hat-trans hat-view black-hat pretty-hat Man pages go into: /usr/local/man/man1 (exists) hat-anim.1 hat-delta.1 hat-detect.1 hat-observe.1 hat-stack.1 hat-trail.1 hat-trans.1 pretty-hat.1 Not (re-)installing html documents Saving current configuration in targets/ix86-Linux/config.cache Done. Please ensure /usr/local/bin is in your PATH variable. **End Of Output** The output of 'ghc-pkg list' is: /usr/local/lib/ghc-6.6/package.conf: Cabal-1.1.6, HUnit-1.1, QuickCheck-1.0, base-2.0, cgi-2006.9.6, fgl-5.2, (ghc-6.6), haskell-src-1.0, haskell98-1.0, html-1.0, mtl-1.0, network-2.0, parsec-2.0, readline-1.0, regex-base-0.71, regex-compat-0.71, regex-posix-0.71, rts-1.0, stm-2.0, template-haskell-2.0, time-1.0, unix-1.0, xhtml-2006.9.13 /home/deech/.ghc/i386-linux-6.6/package.conf: (hat-2.4) <----ERROR!!! For some reason it thinks that hat-2.4 is installed. I tried to run a test program saved in HatTest.hs: import Prelude main = do { print "Hello"; } When I compile it with 'hmake -hat HatTest' I get the following error: hat-trans HatTest.hs Wrote Hat/HatTest.hs ghc-6.6 -c -package hat -o Hat/HatTest.o Hat/HatTest.hs Hat/HatTest.hs:3:0: Bad interface file: /usr/local/imports/hat-2.05/ghc-606/Hat/PreludeBasic.hi Something is amiss; requested module hat-2.4:Hat.PreludeBasic differs from name found in the interface file hat:Hat.PreludeBasic I'm not really sure how to proceed. Any help is appreciated. BTW I get the ghc-package: cannot find package hat when I 'apt-get install' it too. Thanks.. Deech _________________________________________________________________ View Athletes Collections with Live Search http://sportmaps.live.com/index.html?source=hmemailtaglinenov06&FORM=MGAC01

2 2

Generalizing zip
by Jason Dagit 17 Nov '06

17 Nov '06

In #haskell on freenode we had a discussion about isPrefixOf, which is probably implemented roughly as so: isPrefixOf [] _ = True isPrefixOf _ [] = False isPrefixOf (x:xs) (y:ys) = x == y && isPrefixOf xs ys Well, this is basically just a zip with a special base case. But you can't just write it with zipWith because zipWith stops when it exausts either list. How about we define zipWith'' like this: zipWith'' _ [] _ l _ = [l] zipWith'' _ _ [] _ r = [r] zipWith'' f (x:xs) (y:ys) l r = f x y : zipWith'' f xs ys l r Then we can write: isPrefixOf xs ys = and (zipWith'' (==) xs ys True False) A point free reduction might look like the following and probably isn't worth it: isPrefixOf = (and .) . flip flip False . flip flip True . zipWith'' (==) Are there lots of other places where this zipWith'' would come in handy? It seems like I've found lots of times when I needed to manually code the recursion because of the way zip behaves when it exhausts one of its parameter lists. Jason

3 3

topEq for types
by Nicolas Frisby 16 Nov '06

16 Nov '06

I'm sharing what I think is a novel extension of TypeEq. Please 1) cope with my introduction of the motivating problem 2) inform me if something similar has already been presented 3) criticize the solution This presentation is quite a simplification of my actual problem/code, but I'm trying to just show the essence of the technique. Feel free to request the real story or for me to actually code this up. Disclaimer: the following is an untested presentation of correctly functioning code. Thanks for your time. Motivation: In the HList paper, a subtle example involved polymorphism and the singleton list. Because the list was a singleton, TypeCast can be used to resolve the polymorphism. Otherwise, the polymorphism (i.e. free type variables) would prevent crucial typeclass instances from firing. This has inspired a solution to a recent problem of mine. I essentially had an HList of functor values that share the same carrier type. Envision the type of such a list as [F0 Char, F1 Char, ..., Fn Char] where Fi is a functor. I occasionally wanted to "update" one of these values: fn :: F0 Char -> F0 Char fn (F0_CtorOfInterest c) = ...new value... fn f0_c = f0_c newList = specialHMap fn oldList This works fine; the specialHMap method/class is pretty easy to write using TypeEq. The problem arises when I introduce more interesting functors; consider [F Char, G Char, (BF Int) Char] where BF is a bifunctor. Targeting such an functor with an update operation will fail if the update does not specify t. fn2 :: (BF t) Char -> (BF t) Char fn2 (C0 _) = C1 'c' fn2 x = x When the typeclass instances traverse the HList and check each element for a type match, the polymorphism of t in fn2 precludes a successful match of any TypeEq instance. This was frustrating, because it prohibited me from writing modular code! Solution: My solution to the problem was to indicate to the typechecker that certain functors were unique in my HList. So if BF showed up in the HList with a first argument of t', then it would be safe to unify the free t from fn2 with t' (via TypeCast), because no other BF will show up in my list. This quickly generalized to types of various kind with various parameters free. The key to the solution is this class: > class TypeTopEq' () teq x y bn => TypeTopEq teq x y bn > | teq x y -> bn > class TypeTopEq' q teq x y bn > | q teq x y -> bn > class TypeTopEq'' q teq x y bn > | q teq x y -> bn > > instance TypeTopEq' () teq x y bn => TypeTopEq teq x y bn > > > instance TypeCast bn HTrue => TypeTopEq' () TEQ_ hd hd bn > > instance TypeCast bn HTrue => TypeTopEq' () TEQ_0 (hd a) (hd z) bn > instance TypeCast bn HTrue => TypeTopEq' () TEQ_1 (hd a) (hd a) bn > > instance TypeCast bn HTrue => TypeTopEq' () TEQ_00 (hd a b) (hd z y) bn > instance TypeCast bn HTrue => TypeTopEq' () TEQ_01 (hd a b) (hd z b) bn > instance TypeCast bn HTrue => TypeTopEq' () TEQ_10 (hd a b) (hd a y) bn > instance TypeCast bn HTrue => TypeTopEq' () TEQ_11 (hd a b) (hd a b) bn > > -- more instances and TEQ_* for higher kinds of hd TEQ stands for "top equality qualifier". Each 0 specifies that the corresponding argument to the functor is "soft" and not required to match while each 1 specifies that the type is "hard" and is required to match. For example, these instances result in TypeTopEq TEQ_ Int Char HFalse TypeTopEq TEQ_ Int Int HTrue TypeTopEq TEQ_0 (F Int) (F Int) HTrue TypeTopEq TEQ_0 (F Int) (F Char) HTrue TypeTopEq TEQ_0 (F Int) (F Char) HTrue TypeTopEq TEQ_1 (F Int) (F Char) HFalse TypeTopEq TEQ_0 (F Int) (G Int) HFalse TypeTopEq TEQ_1 (F Int) (G Int) HFalse TypeTopEq TEQ_00 (F2 Int Int) (F2 Char Char) HTrue TypeTopEq TEQ_01 (F2 Int Int) (F2 Char Char) HFalse TypeTopEq TEQ_10 (F2 Int Int) (F2 Char Char) HFalse TypeTopEq TEQ_11 (F2 Int Int) (F2 Char Char) HFalse TypeTopEq TEQ_01 (BF t x) (BF Int x) HTrue --- solves the problem above TypeTopEq TEQ_00 (F2 Int Char) (F2 Char Char) HTrue TypeTopEq TEQ_01 (F2 Int Char) (F2 Char Char) HTrue TypeTopEq TEQ_10 (F2 Int Char) (F2 Char Char) HFalse TypeTopEq TEQ_11 (F2 Int Char) (F2 Char Char) HFalse And so on. This class enables typecases based on the "top equality" of two type variables instead of requiring total equality. For example > class SpecialHMap a b l l' | a b l -> l' where specialHMap :: (a -> b) -> l -> l' > -- HNil case elided > instance ( TypeTopEq teq a head bn, HMap_Case bn a b (HCons teq head tail) l' > ) => SpecialHMap a b (HCons teq head tail) l' where > specialHMap = hmap_case (undefined :: bn) > > class HMap_Case a b l l' | a b l -> l' where hmap_case :: bn -> (a -> b) -> l -> l' > instance ( SpecialHMap a b tail tail' > , TypeCast head a > ) => HMap_Case HTrue a b (HCons teq head tail) (HCons teq b tail) where > hmap_case _ fn (HCons hd tl) = HCons (fn . typeCast $ hd) (specialHMap fn tail) > > -- HFalse/recursive instance elided Note that the HTrue instance uses TypeCast instead of multiple occurences of the same variable in the instance parameters. Unfortunately TypeTopEq wanders into the territory of varying kinds and gets a bit out of hand. It has, however, solved my problem. I used a variant of HCons that also has, as a phantom argument, the TEQ to be used for that element. When the typeclass instances traverse the HList, they use the TEQ for each element to decide how to check for a type match with the domain of the update function. Alternatively, I could try to write an overloaded uHCons function that will calculate the proper TEQ value for an element as it adds it to a list; but that was overkill at the moment. I hope that was interesting! I think this could be quickly expanded to other sorts of type-level pattern matching. Please share any thoughts. Thanks again, Nick

1 0

'type' for isomorphism [was poorly named: aggressiveness of functional dependencies]
by Nicolas Frisby 16 Nov '06

16 Nov '06

If anyone is interested, the solution to my problem was to use a type synonym instead of an isomorphism class. Pros: - Not susceptible to the functional dependencies/overlapping instances/open-world issue - Very simple (in fact that simplicity migrated into the rest of the system) Cons: - Obviously less flexible So it works, but it wasn't quite what I had hoped for. Has there been any work/proposals for specifying a "finalized" type class? I.E. Those not subject to overlap and thus "closed" to the world? Thanks, Nick On 11/11/06, apfelmus(a)quantentunnel.de <apfelmus(a)quantentunnel.de> wrote: > Nicolas Frisby wrote: > > First off, thanks for the reply. > > > > I am accustomed to GHC ignoring instance contexts as you mentioned. > > It's the "mostly" part that I'm curious about: mostly implies there's > > some phases that don't ignore context. Is that only the checking the > > type of the method definitions and absolutely nothing else? So it > > seems... > > I just said "mostly" because I don't know exactly... Though I strongly > suspect, like you, that the preconditions are only used in type > inference/checking and not for overlapping instances and similar > questions related to uniqueness of instance declarations. > > > > > My project is rather committed to GHC, but could you elaborate on your > > reference to Hugs being different? > > By tradition from Gofer, Hugs implements type classes more flexible than > GHC does. I once experimented with the following code using overlapping > instances: > > > data Lift a = Lift a > > type Test = Char > > > > class Message m o where > > send :: m -> o -> Test > > > > instance Message (o -> Test) o where > > send m o = m o > > > > instance Message m o => Message m (Lift o) where > > send m (Lift o) = send m o > > > > msg :: Test -> Test > > msg = id > > > > r1 = send msg 'a' > > r2 = send msg (Lift 'b') > > It implements some kind of subtyping. GHC won't typecheck this but "hugs > -98 +m" will. If I remember correctly, the problem was with > > instance Message (Lift a -> Test) (Lift a) > > Does this follow from the first or from the second instance declaration? > GHC ignores the precondition in the second declaration, thus believes it > follows from both and consequently rejects it. But Hugs has no problems > with that: it follows the precondition and sees that the second > declaration does not apply to the culprit because there is no (instance > (Lift a -> Test) a). Note that if you add this instance later on > (perhaps in a different module), things will break. > > The flexibility comes at a price: Gofer's type class system was unsound > and I don't know how much Hugs comes close to this. > > Regards, > apfelmus > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >

2 1

ghc 6.2 and wxhaskell
by Leandro Maia 16 Nov '06

16 Nov '06

Hi Maybe this is not the best place to post this question, but here a lot of people will see and can direct me to the right place. I'm using Linux Slackware 10.2 and 11.0, GHC 6.2 and wxWidgets 2.6.X, 2.7.x I have already tried all kind of combinations but never worked. I tried: GHC 6.2 , 6.2.2, 6.4, 6.4.1, 6.6 wxWidgets 2.6.x, 2.7.x My best result was GHC 6.2 and wxwidgets 2.6.x. But all programs and samples using wxhaskell results in "segmentation fault" I would like to know how to solve this problem. I have to do my exercise but ... Thanks a lot. -- Leandro Maia

1 0

the case of the 100-fold program speedup
by Seth Gordon 16 Nov '06

16 Nov '06

One of Alan Perlis's "Epigrams in Programming" is "A language that doesn't affect the way you think about programming, is not worth knowing". I recently had an experience that demonstrated this principle. I had to write some code that took a polygon (encoded in WKT, a standard format for geographic information exchange), computed its intersection with several rectangles, and then compute the centroid of each one of these intersections. No problem, I thought. People who know more than me about this geometry stuff have written an open-source library, OGR, which has functions for parsing WKT, computing intersections, computing centroids, and computing all sorts of other things. And there are Python bindings for OGR so I don't have to wrestle with C++ to solve my problem. So I wrote a Python program that used OGR to crunch the numbers, ran it through the data set we needed to process, and...it took over sixteen hours to run. Since we want to have this program process this data set with every build of our software, adding sixteen hours to our build time was not a pleasant thought. Then I thought about some of the things I'd read about optimization of functional programming languages, and said, "Hey! The algorithm for clipping the polygon to the rectangle is producing a sequence of vertices, and the algorithm for computing the centroid is consuming a sequence of vertices. I can do some deforestation here!" It took me a week to figure out the right algorithm for combining these two procedures and write some almost-working code that implemented it. It took a co-worker of mine another few days to find the bugs that had eluded me. But after the program worked for my test cases, I ran it again on the full data set...and it took ten minutes. In other words, I sped up the code by two orders of magnitude. And I didn't even have to drop into C++ to do the number-crunching; I used OGR to parse the WKT strings and to look up the coordinates of each vertex of the polygon, but the algorithm itself was implemented in Python. w00t!

3 4

forall and a parse error
by Neil Mitchell 15 Nov '06

15 Nov '06

Hi, I was experimenting with forall and higher rank types briefly, in particular: x :: [forall a . a] This is illegal because of: http://www.haskell.org/ghc/docs/latest/html/users_guide/type-extensions.htm… Which is fine, however its surprising to compare the error messages: [forall a . a] parse error on input `forall' [(forall a . a)] Illegal polymorphic or qualified type: forall a. a In the type signature: lst :: [(forall a. a)] In normal Haskell, I tend to view [x] as equivalent to [(x)] (provided that x is not a tuple) but in this case it has a different meaning - albeit both are erronous meanings. When running the example with Hugs, they both come out as syntax errors - the first on the forall, the second on the closing square bracket. Thanks Neil

5 6

Re: [Haskell-cafe] Re: Debugging partial functions by the rules
by John Hughes 15 Nov '06

15 Nov '06

> From: Robert Dockins <robdockins(a)fastmail.fm> > It seems to me that every possible use of a partial function has some > (possibly imagined) program invariant that prevents it from failing. > Otherwise it is downright wrong. 'head', 'fromJust' and friends > don't do anything to put that invariant in the program text. Well, not really. For example, I often write programs with command line arguments, that contain code of the form do ... [a,b] <- getArgs ... Of course the pattern match is partial, but if it fails, then the standard error message is good enough. This applies to "throw away" code, of course, and if I decide to keep the code then I sooner or later extend it to fix the partiality and give a more sensible error message. But it's still an advantage to be ABLE to write the more concise, but cruder version initially. This isn't a trivial point. We know that error handling code is a major part of software cost--it can even dominate the cost of the "correct case" code (by a large factor). Erlang's "program for the correct case" strategy, coupled with good fault tolerance mechanisms, is one reason for its commercial success--the cost of including error handling code *everywhere* is avoided. But this means accepting that code *may* very well fail--the failure is just going to be handled somewhere else. Haskell (or at least GHC) has good exception handling mechanisms too. We should be prepared to use them, and "let it fail" when things go wrong. The savings of doing so are too large to ignore. John

4 3

submenu doesn't seem to work properly in wxhaskell
by Maarten 15 Nov '06

15 Nov '06

Dear all, The following code doesn't seem to work properly. Either the main entry (m1/mp1) or it's sub menu entry (ms1/mps1) do not seem to propagate the event when pressed. It is possible to make it working by uncomments the lines where the menu commands are registered in the frame. I have the following two questions: 1. Why doesn't the plain code work. Am I missing something or doing something wrong? 2. Doesn't registering eventhandlers in the frame introduce a memory/resource leak, especially in the case of popups? Any suggestions or comments appreciated. Thanks. Kind regards, Maarten Code: <imports> gui :: IO () gui = do f <- frame [ text := "Hello world!" ] m <- menuPane [ text := "&Menu" ] m1 <- menuItem m [ text := "Menu m1", on command := putStrLn "menu m1"] -- set f [ on (menu m1) := putStrLn "menu m1" ] menuLine m sub <- menuPane [text := "Sub menu"] ms1 <- menuItem sub [ text := "submenu ms1", on command := putStrLn "submenu ms1" ] -- set f [ on (menu ms1) := putStrLn "submenu ms1" ] menuSub m sub [ text := "Sub" ] menuItem m [text := "E&xit", on command := close f] set f [menuBar := [m], on mouse := mouseEvent f, clientSize := sz 200 200 ] return () mouseEvent f eventMouse = do case eventMouse of MouseRightDown mousePoint _ -> doPopup f mousePoint _ -> return () doPopup f mousePoint = do m <- makePopupMenu f "&Popup" "Doesnt' work..." menuPopup m mousePoint f objectDelete m makePopupMenu f c t = do mp <- menuPane [ text := c ] mp1 <- menuItem mp [ text := "Popup mp1", on command := putStrLn "popup mp1"] -- set f [ on (menu mp1) := putStrLn "popup mp1" ] menuLine mp sub <- menuPane [text := "more text"] mps1 <- menuItem sub [ text := "Popup mps1", on command := putStrLn "popup mps1"] menuSub mp sub [ text := "Sub" ] -- set f [ on (menu mps1) := putStrLn "popup mps1" ] return mp

2 2