June 2006 - Haskell-Cafe

RE: [Haskell-cafe] newbie type signature question
by Brock Peabody 12 Jun '06

12 Jun '06

> From: Brandon Moore > Getting them both is tricky, but you can do it if you use a GADT to > write a type that means "exists a such that a = m and a is a Monad": Is GADT a way to assemble types at compile-time? It looks really cool. > {-# OPTIONS -fglasgow-exts #-} > data TyEq (a :: * -> *) (b :: * -> *) where ^ ^ Compiling this fails here (the first '*') for me with "parse error on input '*'" (ghc 6.4.1), but I'll keep playing with it. Thanks, Brock

2 1

Inferred type not most general?
by Greg Buchholz 10 Jun '06

10 Jun '06

I'm curious about a type inference oddity. In the code below, if I leave off the type signature for tmap, both GHC and Hugs infer that tmap has type... tmap :: (b -> a, b -> a) -> Twist b b -> Twist a a ...I'm wondering why they couldn't infer the more general... tmap :: (a -> b, c -> d) -> Twist a c -> Twist b d >data Twist a b = Nil | Cons a (Twist b a) deriving Show > >x = (Cons "foo" (Cons 1 (Cons "bar" (Cons 2 Nil)))) > >tmap :: (a->b,c->d) -> Twist a c -> Twist b d >tmap _ Nil = Nil >tmap (f,g) (Cons x rest) = Cons (f x) (tmap (g,f) rest) Thanks, Greg Buchholz

2 1

Re: Inferring types from functional dependencies
by oleg＠pobox.com 10 Jun '06

10 Jun '06

Jeff Harper defined typeclasses > class Reciprocate a b | a -> b where > recip :: a -> b > class Multiply a b c | a b -> c where > (*) :: a -> b -> c and encountered the problem with > -- Here I define a default (/) operator that uses the > -- Reciprocate and Multiply class to perform division. > class (Reciprocate b recip, Multiply a recip c) => Divide a b c | a b -> c > where > (/) :: a -> b -> c > (/) x y = x * (recip y) which doesn't work, because the type variable 'recip' doesn't appear in the class head. He wrote > I also, wonder if it would be appropriate to include in future > versions of Haskell, the ability to infer functional dependences in a > new class definition, so that my first attempt at a definition of > class Divide works. I'm afraid there may be the problem with the example rather than with Haskell. Let us suppose that the above definition of Divide works. Jeff Harper writes elsewhere > However, taking the reciprocal and then multiplying may not always be > the best way of dividing. So, I'd like to put this into a divide > class, so (/) can be defined differently for different types. The key phrase is that we wish (/) defined differently for different types, because using reciprocals is not always the best way of dividing. Then why do we insist that every instance of Divide must be also an instance of Reciprocate (because that's what the definition of Divide says)? Why is that that whenever we divide something by the value of type 'b', it must be possible to reciprocate that value of type b? Even if we don't use reciprocals in the division? If we assume that we need Reciprocate only if we are going to use the 'default' method, the solution becomes obvious. It does involve overlapping and undecidable instances, sorry. These extensions are really useful in practice. Here's the solution: > class Divide a b c | a b -> c where > (/) :: a -> b -> c Here's the most general instance. It applies when nothing more specific does. It is in this case that we insist on being able to take the reciprocal: > instance (Reciprocate b recip, Multiply a recip c) => > Divide a b c where > (/) x y = x * (recip y) Now, a specific instance only for Integers, which involves no reciprocals: > instance Divide Integer Integer (Ratio Integer) where > (/) = (%) Another specific instance. It too involves no reciprocals. Incidentally, the posted code does not even define an instance of Reciprocate for Ints! > instance Divide Int Int (Ratio Integer) where > x / y = (fromIntegral x) % (fromIntegral y) A few tests: > test0 = (1::Int) / (2::Int) > test1 = (1::Integer) / (2::Integer) > test2 = (1::Double) /(2::Double) P.S. A remark for Haskell': the most general instance above (repeated below) > instance (Reciprocate b recip, Multiply a recip c) => > Divide a b c where > (/) x y = x * (recip y) shows why we can never be satisfied with only decidable instances -- why we need the undecidable instances extension. The instance makes it clear that we cannot decide if the instance selection process for Divide terminates just by looking at this instance. There is no information to decide on termination: we must examine instances of Reciprocate and Multiply (in particular, we should check if those instances refer back to Divide). Thus, no _local_ instance termination criterion would ever be able to handle above instance. OTH, it seems quite unreasonable to require a Haskell system to employ a global instance selection termination criterion (short of recursion stack limit or other such `dynamic' test).

1 0

Features of Haskell
by Niels Van Och 09 Jun '06

09 Jun '06

Hi, I'm a Master student in Computer Science, and for my bachelor thesis, I've written 'an introduction to Haskell'. In this document, I've discussed syntax, evaluation, polymorphism, monads etc. Now, in a week I have to present this work formally, and I'm a bit stumped as to how I'm going to do this. I've got about 15-20 minutes, so I can only discuss the major features. Right now I'm thinking about: - Short introduction to functional programming, and Haskell in it - Basic syntax in a few minutes - Features like polymorphism, overloading, higher-order functions, comprehensions, .. - Lazy evaluation - Monads: why and how? However, I'd love to know what you think. Furthermore, do you think I should include an example on the usage of Haskell, and if so, which? Many thanks! Niels

8 9

Inferring types from functional dependencies
by Jeff.Harper＠handheld.com 09 Jun '06

09 Jun '06

The following message is in a Haskell module. It will be easier to read in a fixed point font. {-# OPTIONS -fglasgow-exts #-} -- Hi, -- -- I ran into an issue while working with functional dependencies. -- Consider the following code. I'm rewriting many of the prelude -- operators using functional dependencies. The type of he return value -- is determined by the operators parameters. -- Use "P." in front of functions to access the preludes version of these -- functions. import qualified Prelude as P -- I override prelude operators with my own operators. import Prelude hiding ( (*), recip ) import Ratio -- recip returns the reciprocal of its parameter. I've given the -- Reciprocate class the ability to return a type that is different from -- its argument. class Reciprocate a b | a -> b where recip :: a -> b -- Here are some example instances of Reciprocate. In most cases, -- recip will return the same type as it's argument. However, taking -- the reciprocal of an Integer returns a (Ratio Integer). instance Reciprocate Double Double where recip = P.recip -- I call prelude's recip here. instance Reciprocate (Ratio Integer) (Ratio Integer) where recip = P.recip -- I call prelude's recip here. instance Reciprocate Integer (Ratio Integer) where recip x = (1::Integer) % x -- (*) multiplies its parameters. The resulting type is determined by -- the type of the arguments class Multiply a b c | a b -> c where (*) :: a -> b -> c -- Here are some example instances of Multiply. instance Multiply Double Double Double where (*) = (P.*) -- Multiplying Integer by Double returns a Double instance Multiply Integer Double Double where (*) x y = (P.*) (fromIntegral x) y instance Multiply Double Integer Double where (*) x y = (P.*) x (fromIntegral y) instance Multiply Integer (Ratio Integer) (Ratio Integer) where (*) x y = (P.*) (x%1) y -- Now, this is where I ran into some trouble I define a Divide class -- as follows. Here I define a default (/) operator that uses the -- Reciprocate and Multiply class to perform division. However, this code -- produces error messages. So, I commented it out. Even if I don't want -- to implement (/) with recip and (*), requiring this relationship -- -- | -- ---------------------------------------------- -- | -- v is consistent with defining -- _____________________________________ the divide operation in -- | | terms of the multiplicative -- | | inverse {- class (Reciprocate b recip, Multiply a recip c) => Divide a b c | a b -> c where (/) :: a -> b -> c (/) x y = x * (recip y) -} -- This definition of (/) works. However, taking the reciprocal and then -- multiplying may not always be the best way of dividing. So, I'd like to -- put this into a divide class, so (/) can be defined differently for -- different types. {- (/) :: (Reciprocate b recip, Multiply a recip c) => a -> b -> c (/) a b = a * (recip b) -} -- I finally discovered that the following definition of a Divide -- class works class (Reciprocate b recip_of_b, Multiply a recip_of_b c) => Divide a b c recip_of_b | a b -> c recip_of_b where (/) :: a -> b -> c (/) a b = a * (recip b) -- Default definition can be overridden -- The thing I don't like is that when defining a new Divide class, I have -- to place the reciprocal of the "b" type into the class definition. -- Here are some examples of Divide: -- -- This type ---------------------------- -- must be the type that is | -- returned when this | -- type ------------------ | -- is passed to recip. | | -- | | -- v v instance Divide Double Double Double Double where (/) x y = (P./) x y -- For Doubles -- Another example: -- -- This type ------------------------------------------ -- must be the type that is | -- returned when this | -- type ------------------- | -- is passed to recip. | | -- | | -- v v instance Divide Integer Integer (Ratio Integer) (Ratio Integer) where (/) x y = x % y -- The reason I don't like it is there is enough information available to infer -- the type of recip_of_b in the following class. The Reciprocate class is -- defined with functional dependencies, so that recip_of_b can be determined -- by the type of b.-- -- | -- ______________________ -- | | -- -- class (Reciprocate b recip_of_b, Multiply a recip_of_b c) -- => Divide a b c recip_of_b | a b -> c recip_of_b where -- (/) :: a -> b -> c -- (/) a b = a * (recip b) -- -- Respecifying the recip_of_b when I declare an instance of Divide -- seem redundant. I'm wondering if there is a better way to -- define this. I also, wonder if it would be appropriate to include -- in future versions of Haskell, the ability to infer functional -- dependences in a new class definition, so that my first attempt -- at a definition of class Divide works.

1 0

Re: Newbie request
by Chad Scherrer 09 Jun '06

09 Jun '06

Philip, you wrote: ------------------------------------------------------------------------------------- I am trying to learn Haskell. As an exercise, I wrote a function to create a binary tree in level-order. I am attaching the code. I am sure there are a number of places where the code could be improved. Could you please point these out? Thanks, Philip >countNodes :: Tree a -> Integer >countNodes Empty = 0 >countNodes (Tree rootNode left right) = 1 + countNodes left + countNodes right -------------------------------------------------------------------------------------- Stylistically, this is usually written using a fold. Try writing a function fold :: (a -> b -> b -> b) -> b -> Tree a -> b Then rewrite countNodes as countNodes = fold f 0 where f x left right = 1 + left + right A huge number of other handy functions can then be written in terms of fold. -- Chad Scherrer "Time flies like an arrow; fruit flies like a banana" -- Groucho Marx

1 0

Newbie request
by Geevarghese Philip 09 Jun '06

09 Jun '06

I am trying to learn Haskell. As an exercise, I wrote a function to create a binary tree in level-order. I am attaching the code. I am sure there are a number of places where the code could be improved. Could you please point these out? Thanks, Philip ------------------------------------------------------------------------------ BinTree.lhs : Implementation of a binary tree. createTree accepts a sequence and builds a binary tree in level-order. ------------------------------------------------------------------------------ >module BinTree where ------------------------------------------------------------------------------ A binary tree either 1. is empty, or 2. consists of three distinct binary trees : a root node, a left subtree, and a right subtree. ------------------------------------------------------------------------------ >data Tree a = Empty | Tree {rootNode::a, left::(Tree a), right::(Tree a)} deriving (Eq, Show) ------------------------------------------------------------------------------ Count the number of nodes in a binary tree, using the simple recursive definition of the count. ------------------------------------------------------------------------------ >countNodes :: Tree a -> Integer >countNodes Empty = 0 >countNodes (Tree rootNode left right) = 1 + countNodes left + countNodes right ------------------------------------------------------------------------------ Insert a single element into the proper place in the tree, as per level-order. ------------------------------------------------------------------------------ >insert :: Eq a => Tree a -> a -> Tree a >insert tree x = if tree == Empty > then Tree x Empty Empty > else if (left tree) == Empty > then Tree (rootNode tree) (Tree x Empty Empty) (right tree) > else if (right tree) == Empty > then Tree (rootNode tree) (left tree) (Tree x Empty Empty) > else if countNodes (left tree) <= countNodes (right tree) > then Tree (rootNode tree) (insert (left tree) x) (right tree) > else Tree (rootNode tree) (left tree) (insert (right tree) x) ------------------------------------------------------------------------------ Use insert to create a tree from a sequence. ------------------------------------------------------------------------------ >createTree :: Eq a => [a] -> Tree a >createTree [] = Empty >createTree (x:xs) = foldl insert (insert Empty x) xs

3 3

Literate Haskell in Vim - a bug and a workaround (?)
by Piotr Kalinowski 09 Jun '06

09 Jun '06

Hi, I've been recently playing with literate haskell in latex mode in Vim. The versions are: Vim - 6.4.6 tex.vim - 30 lhaskell.vim - 1.01 I encountered a bug. If you put \section (or \subsection or \chapter or other similar command), haskell syntax highlighting is lost from this command onwards. I tried some googling and searching this list's archives but found nothing. After going through tex.vim and reading vim docs I found out, that adding 'containedin tex.*Zone' to the following line: syntax region lhsHaskellBeginEndBlock start="^\\begin{code}\s*$" matchgroup=NONE end="\%(^\\end{code}.*$\)\@=" contains=@haskellTop,@beginCode appears to solve the problem. Apparently the bug is caused by texSectionZone (and other zones) syntax region which extends from \section command until another \section command. Since lhsHaskellBeginEndBlock region was not allowed inside texSectionZone, it was not recognised. Adding containedin clause addresses this problem letting vim to recognise \begin{code} as beginning of the Haskell file part. Such change however breaks tex lexical checks. More specifically - texMatcher from tex.vim is unable to match braces around section titles (chapter, subsection, etc.). I tried tampering with lhaskell.vim for some time but found no way to fix it. (Which is not surprising, given the fact that I am far from being vim expert. In fact I know almost nothing about vim programming.) Therefore the patch I attach simply turns lexical checks off setting g:tex_no_error variable. The variable is then unset immediately after loading tex.vim in order not to affect other buffers where it can work correctly. I attach the patch with those two changes. It is diff -u output. Any comments are welcome. I would especially be happy to learn how to fix texMatcher issue without turning it off. Regards, Piotr Kalinowski -- Intelligence is like a river: the deeper it is, the less noise it makes

1 0

Re: [Haskell-cafe] Re: Editors for Haskell
by Imam Tashdid ul Alam 09 Jun '06

09 Jun '06

hya this topic is hot, and I wonder why :s well, I've been thinking, the EclipseFP people have done more or less a fine job (I'm trying their "live" build, things feel natural). but the problem is, to build something like EclipseFP you have to know both Java and Haskell and on top of that you have to be very familiar with the Eclipse plug-in architecture. whining: - should have had folds for where and let clauses - the error messages are still cryptic (and unformatted!) - there was no tooltip for functions - the default color chosen for functions is way too bright - ... (many silly Java expectations follow) but what if we _ask_ eclipse.org to help us out? like, an official collaboration? they have done an excellent job promoting free software. this should be sort of a recognition for them. the point is, GUI _is_ easier to build in Java. and those people are experts. should not take much time. as for me, I'll be happy to watch the impact Haskell will have on Java fans. two things just to make sure this post is not absolutely superfluous: - without drinking anything I was feeling drunk that night and so I posted some of my hIDEous thoughts in http://www.haskell.org/haskellwiki/Talk:HIDE page. Lemmih left a note saying I was not so genuine, a project called Proxima has implemented (or at least, proposed) most of the ideas. I checked it out and was ashamed of my lack of original idea. however, though the paper was absolutely dreamy, the implementation,.. how do I put it humbly.. sucked. I am sure the Eclipse people will appreciate the Proxima ideas. please ask them to build a Proxima style IDE for Haskell. - about formatted error messages (I am sure you guys don't care), could someone build a light GHC front end that given a .hs/.lhs file produces two XML files with specified DTD, the parsed structure and the error messages? the reason for choosing XML is that not only the Java people (including Leif Frenzel) but also virtually anyone can access these information (in order to create a great IDE) immediately and without loosing the structure. cheers, Imam __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

4 3

Type class hell
by Christophe Poucet 08 Jun '06

08 Jun '06

Dear, I am writing a compiler (as you may have gathered from some previous messages). Anyways I am stuck with a small monadic issue. I mostly use indirect composite as this gives me the most flexibility with regards taking out parts of the AST, or decorating at whim. Basically the question regards how to implement a certain instance. Currently I have the code that can be seen below. What I would like to do is combine HasVars and Type (mostly because in my framework the two concepts shouldn't be divided from a design perspective) into one type class to clean it up a bit. However I fail to see how I would implement toType and fromType for the given instance. Is this feasible without resorting to ugly hacks? --- Types data MonoType mt = TyVar Var | TyConst Const [mt] deriving (Eq, Show) data PolyType mt = TyPoly [Var] mt deriving (Show) class Type mt where toType :: mt -> MonoType mt fromType :: MonoType mt -> mt class HasVars a where freeVars :: a -> [Var] occurs :: Var -> a -> Bool toPoly :: (HasVars a) => a -> PolyType a toPoly x = TyPoly (freeVars x) x instance HasVars a => HasVars (MonoType a) where freeVars (TyVar x) = [x] freeVars (TyConst _ xs) = nub . concatMap freeVars $ xs occurs x (TyVar y) = x == y occurs x (TyConst _ xs) = or . map (occurs x) $ xs Cheers, Christophe(vincenz) -- Christophe Poucet Ph.D. Student Phone:+32 16 28 87 20 E-mail: Christophe (dot) Poucet (at) imec (dot) be Website: http://notvincenz.com/ IMEC vzw – Register of Legal Entities Leuven VAT BE 0425.260.668 – Kapeldreef 75, B-3001 Leuven, Belgium – www.imec.be *****DISCLAIMER***** This e-mail and/or its attachments may contain confidential information. It is intended solely for the intended addressee(s). Any use of the information contained herein by other persons is prohibited. IMEC vzw does not accept any liability for the contents of this e-mail and/or its attachments. **********

5 10