October 2006 - Haskell-Cafe

A type in search of a name...
by Brian Hulley 13 Oct '06

13 Oct '06

Hi, You'll never believe it but I've been struggling last night and all of today to try and think up a name for the following type and I'm still nowhere near a solution: data ??? = VarId | VarSym | ConId | ConSym this is part of a type to describe Haskell lexemes: data Token = TName !??? !ByteString.T | ... Here are some of my attempts to fill in ??? and my reasons for rejecting them: 1) VarConIdSym - the problem is that it's too long and the first letter is 'v' which could be confused with the letter 'V' in "VarId" or "VarSym" 2) Name - the problem is that this suggests the string itself rather than the VarId/VarSym/ConId/ConSym'ness of the token 3) NameType - I'm trying to avoid using the words "Type" "Kind" etc because I'll probably want to use these later for other things and in any case NameType suggests the type of a lexical name ie Token itself 4) Space - this can be confused with something to represent whitespace or the namespaces introduced by modules 5) Just using data Token = TVarId !BS.T | TVarSym !BS.T | ... -- explodes into too many different cases when you add tokens for qualified names and all their variations (since I'm also representing incomplete tokens like "Foo." and "Foo.where" (as a prefix of "Foo.whereas" etc since it can't stand by itself because "where" is a reserved word)) 6) Using Bool as in data Token = TName !Bool !Bool !BS.T -- problem is that then I won't get any help from the typechecker if I accidentally confuse the order of Bools when matching etc. I could use the record syntax but then code can become very clunky to look at and it would still allow the Bools to get confused when they are passed about Any ideas? I must say that trying to think up names for things is absolutely the most difficult task in programming imho. The problem is that once fixed down, a name gets used all over the place and becomes totally entrenched in the code and affects how one thinks about the code thereby influencing its whole future development in a very deep and pervasive way (think suffixes/ prefixes/ relationships with other concepts etc). I would also be satisfied with just good names for the following types: data ???1 = Var | Con data ???2 = Id | Sym data ???3 = Op | Plain (I just combined ???1 and ???2 in ??? to try and save some space in the representation but ideally they would be separate types if only there were a way to tell the compiler to represent each by 1 bit in a word at the machine level like C's struct {VarCon vc : 1; IdSym is : 1;}) Any suggestions welcome, Thanks, Brian. -- Logic empowers us and Love gives us purpose. Yet still phantoms restless for eras long past, congealed in the present in unthought forms, strive mightily unseen to destroy us. http://www.metamilk.com

2 2

nightnightita
by George Brewster 13 Oct '06

13 Oct '06

hope you're feeing better too.

1 0

Nim Game in Haskell - Someone plz?
by Luis Felipe 13 Oct '06

13 Oct '06

Hi, I need help to develop an implementation of nim game in Haskell. Could anyone send me a implementation of this game in haskell?? thanks -- Luis

2 1

Having typing problem with "tan" function.
by Edward Ing 13 Oct '06

13 Oct '06

Hi, I am new to Haskell, so the following problem is probably easy for you to spot but difficult for me. Any pointers would be appreciated. In GHCI on a load I am getting the following message: SSnowflake.hs:41:45: No instance for (Floating Int) arising from use of `pi' at Snowflake.hs:41:45-46 Probable fix: add an instance declaration for (Floating Int) In the first argument of `(/)', namely `pi' In the first argument of `tan', namely `(pi / 3)' In the second argument of `(*)', namely `(tan (pi / 3))' Failed, modules loaded: none. When I put the expression "tan ( pi / 3)" at the GHCI interpreter prompt I get a value, but this is not accepted on a load the code. Here is the code: >>>> code triangle :: Window -> (Point,Point) -> Int -> IO () triangle window ((x1,y1), (x2,y2)) size = let height = fromIntegral(y2 - y1) * 3 / 2 halfWidth = height * (tan (pi / 3 )) in drawInWindow window (withColor (sizeColorMap size) (polygon [(x1,y1),( x1 - halfWidth, height ), (x1 + halfWidth, height)] ))

3 3

Is Haskell a Keynesian language?
by Henning Thielemann 12 Oct '06

12 Oct '06

Here is another approach of questionable classification of languages. :-) A lazy functional program is demand driven, an imperative program is supply driven. That is, if I request some information by calling a function in GHCi or Hugs, the interpreter develops a plan a how to produce the information I need and then executes the necessary steps. In contrast to that, an imperative program executes what's next on the schedule, whether it is need or not. So is Haskell a Keynesian language and C++ a Say language?

5 4

tail-recursing through an associative list
by Seth Gordon 12 Oct '06

12 Oct '06

In my first posting, I mentioned that I was going to try to translate some of our code to Haskell and see how it worked. Well, I don't have a stunning demonstration of the power of pure functional programming, but I do have an interesting problem. I chose to port a program that we use in our build system that takes a table of geographic data and groups the rows in the table according to [REDACTED]. The description of what the existing program does takes up only a few paragraphs, but the source code is eight pages of dense C++ that has obviously been optimized up the wazoo (and beyond the point where a mortal like myself can understand what's going on). On one of our servers, it can process 200,000 rows in about three minutes. My Haskell translation is three and a half pages of gorgeous lucid almost-entirely-functional code ... that in its first draft, took about three seconds to process 2,000 rows, eight minutes to process 20,000 rows, and overflowed a 1-MB stack when processing 200,000 rows. Oops. After banging together a version that took input from stdin instead of the database (it was easier to do that then to learn enough about Cabal to get HSQL recompiled with profiling), I profiled the code and observed that the most-called-upon function in the program (200 million entries for those 20,000 rows) was structured like this: type AList = [(Key, [MetaThingies])] myFunction :: AList -> Thingie -> AList myFunction [] x = [(key x, [meta x])] myFunction ((k, v):tail) x | matchKeys k (key x) = case tryJoining v x of Nothing -> (k, v) : (myFunction tail x) Just v' -> (k', v') : tail where v' = bestKey k (key x) | otherwise = (k, v) : (myFunction tail x) I'm wondering if the slowness of the program can be attributed to that case statement in the middle--perhaps unwrapping the Maybe type returned by tryJoining is preventing the function from being properly tail-recursive, or something. (I tried making the list construction strict by replacing "(k, v) : (myFunction tail x)" et al. with "(:) (k, v) $! (myFunction tail x)", and it actually slowed the program down, so either I'm not understanding how to improve things with strictness or laziness isn't the problem here.) Any advice from the gurus?

4 4

Gtk2Hs and Glade Tutorial
by Hans van Thiel 12 Oct '06

12 Oct '06

Hello, There is a very nice tutorial on the Glade Interface Designer at http://www.writelinux.com/glade and I've been using it with 'An Introduction to Gtk2Hs, A Haskell GUI Library', by Kenneth Hoste at http://haskell.org/~shae/memory.pdf to learn Gtk2Hs and Glade. The 'Gtk2Hs Introduction', however, is not really aimed at the absolute beginner and so I've written down my experience as an 'appendix' to the glade tutorial, which really is for getting started. I've just asked the author, Eddy Ahmed, for permission to 'translate' his tutorial to Haskell Gtk2Hs, but meanwhile I'd like to submit my separate concept (attached) for comments. Thanks, Hans van Thiel

2 1

do ghci
by Greg Fitzgerald 12 Oct '06

12 Oct '06

Just curious, why does ghci run in the context of a 'do'? This tripped me up when I first started learning Haskell. It's fine once you know what's going on, but why the restriction? Why can't I write the code below without 'let' and ':module'? > two = 1 + 1 > import Data.List > cols = transpose [[1,2,3], [4,5,6]] Thanks, Greg

2 1

Quantifying Partial Type Annotations
by Philippa Cowderoy 12 Oct '06

12 Oct '06

I've done a bit more thinking about partial type annotations (as proposed on the Haskell' list), and I have a somewhat more concrete proposals for some of the extensions to them that perhaps also makes more sense of the original basic idea as well. I'm sending it to the Cafe this time as it's a bit early to consider this for standardisation. I'd like to propose a new quantifier for type variables, which for now I'll call unknown[1] - correspondingly I'll talk about "unknown-quantified variables" and probably "unknown variables" where it's not ambiguous. Unknown quantifiers will never be introduced by the typechecker without a corresponding annotation - only propagated inwards. Whereas universal type variables must not accumulate additional constraints during typechecking (and in a traditional Hindley-Milner implementation only become universally quantified during a generalisation step), unknown type variables can - indeed this is their raison d'etre. Furthermore, they are never propagated 'outwards' - either the variable is constrained sufficiently that it can be replaced with a monotype or, having otherwise finished typechecking the corresponding term, the unknown quantifier is replaced with a forall. For example: add' :: unknown x. x -> x -> x add' = (+) add'' :: unknown x. x -> x -> x add'' x y = (x::Int) + (y::Int) will typecheck, resulting in these types when the identifiers are used: add' :: forall x. Num x => x -> x -> x add'' :: Int -> Int -> Int It's probably also sensible to allow "wildcard" variables written _, generated fresh and implicitly unknown-quantified much as universal variables are now. Type synonyms seem to present an interesting question though - it seems to me most sensible to hang on to the quantification at top-level and generalise it only as we finish type-checking a module, rather than copying out the quantifier anew each time. Any comments? The amount of thinking I've done about interactions with rank-n variables is limited - I guess we'd need to prohibit unifying with type variables that're of smaller scope than the unknown variable? I'm don't think I can see any other worrying issues there. Unknown variables in method declarations seem... meaningless to me, they're not proper existentials and I don't think there's a sane meaning for them that isn't a kludge for associated types instead. I don't think they belong in instances for similar reasons. Incidentally, I think there's also a cute use case in .hs-boot files, where an unknown-quantified variable could be used to tie some knots in a manner similar to the way recursive bindings are checked now. If so, I have an interesting use for this. [1] Other names that have occurred to me are "solve" (as in "solve for x"), and "meta" (by analogy to metavariables in the typechecker - because by the time we've finished checking the annotated term we'll have removed the quantifier), but unknown seems by far the strongest to me. No doubt someone'll suggest a far better name shortly after I post this! -- 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.

3 2

Yet Another Haskell Tutorial Question
by Bill Mill 12 Oct '06

12 Oct '06

I've been working through the "Yet Anther Haskell Tutorial" at http://www.cs.utah.edu/~hal/docs/daume02yaht.pdf , and I've gotten up to Excercise 4.6. It says: === YAHT === Write a datatype Tuple which can hold one, two, three or four elements, depending on the constructor (that is, there should be four constructors, one for each number of arguments). Also provide functions tuple1 through tuple4 which take a tuple and return Just the value in that position, or Nothing if the number is invalid (i.e., you ask for the tuple4 on a tuple holding only two elements). === /YAHT === I've got a brute-force answer, but I'm sure that there's a better way, and I can't find it. The code I've currently got is at http://paste.lisp.org/display/27806 . Anybody want to point me in the right direction? Thanks Bill Mill bill.mill at gmail.com

3 3