- Haskell-Cafe - Haskell.org

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

Haskell Debugging
by Valentin Gjorgjioski 15 Nov '06

15 Nov '06

I'm pretty new in Haskell, few days since I started learning it. I want to debu my programs. I'm currently using WinHugs, and I prefer debugger for this. I tried googling and I found Hugs.Observer. I like it how it works, but still I have one BIG problem with it. It doesn't work well with floats. Following example import Hugs.Observe ex8 :: [Float] ex8 = (observe "after reverse" ) reverse [10.0,7.0,3.0,0.0,4.0] gives me >ex8 [4.0,0.0,3.0,7.0,10.0] >>>>>>> Observations <<<<<< after reverse { \ ($-990871 : $-990888 : $-990905 : $-990922 : $-990939 : []) -> $-990939 : $-990922 : $-990905 : $-990888 : $-990871 : [] } Which is not useful. After that I try to install http://www.haskell.org/hat/ but for installing that I need hmake, and when I try to install hmake, I typed first configure -prefix, and then, make. cd src/hmake; make HC=ghc BUILDCOMP=ghc all config make[1]: Entering directory `/cygdrive/E/Haskell/hmake/src/hmake' Makefile:59: *** target pattern contains no `%'. Stop. make[1]: Leaving directory `/cygdrive/E/Haskell/hmake/src/hmake' make: *** [targets/ix86-CYGWIN_NT-5.1/hmake-ghc] Error 2 as you can see I'm using cygwin. I'm really stacked here, and I will kindly ask for help. Thanks, Valentin -- Valentin Gjorgjioski Bachelor of Computer Science Department of Knowledge Technologies, Jozef Stefan Institute Jamova 39, SI-1000 Ljubljana, Slovenia Phone: +386 1 477 3343 Fax: +386 1 477 3315 Web: http://kt.ijs.si/ValentinGjorgjioski/ Email: Valentin.Gjorgjioski(a)ijs.si

5 11

Re: Haskell custom search engine
by Alberto G. Corona 15 Nov '06

15 Nov '06

By the way, I have developped the core of a search engine completely in Haskell. It can index arbitrary objects (including files, of course) has definitions for filters, with predefined filters for plain text, HTML/XML and a general filter for Haskell data types It has basic search capabilities: it returns a list of identifiers (URIs) of the objects that contains all the entered keywords. But it is fairly easy to accept arbitrary AND OR and NOT conditions. Just query parsing is necessary. More info: http://haskell-web.blogspot.com/2006/11/search-engine-written-in-haskell.ht… The source of Search.hs can be found here<http://www.box.net/public/fdkami7jbk>

1 0

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

15 Nov '06

Hello Johannes, Wednesday, November 15, 2006, 10:36:10 AM, you wrote: > What methods and tools are there for i18n of Haskell programs? > In Haskell, I see at least two problems: > a) reading the file is in IO if you need utf8 and other encodings support, you can use Streams lib: h <- openFile "test" ReadMode >>= withEncoding utf8 http://haskell.org/haskellwiki/Library/Streams > b) there are no "global variables". implicit parameters perhaps? there is a sort of global vars: ref_command = unsafePerformIO$ newIORef$ error "undefined ref_command" uiStartCommand command = do writeIORef ref_command command .. uiStartProcessing filelist = do command <- readIORef ref_command .. but implicit parameters, of course, are more intelligent approach -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

1 0