May 2007 - Haskell-Cafe

A small error
by Andrew Coppin 19 May '07

19 May '07

Um... why doesn't this work? my_fn x = do if x < 0 then do let y = 5 return () else do let y = 8 return () print y (Error: "y" is not in scope.)

2 3

Accepted by Hugs, not by GHC
by Hans van Thiel 19 May '07

19 May '07

Hello All, Defining a partially ordered set as: data Porder = HI | LW | NT deriving (Eq) class (Eq a) => Poset a where pcompare :: a -> a -> Porder and defining an instance for type synonym RuRe: type RuRe = ([Int],[Int]) instance Poset RuRe where pcompare (x1,y1) (x2,y2) | isSub x2 x1 = HI | isSub x1 x2 = LW | otherwise = NT causes no problems in Hugs (-98 flag) but compiling with GHC produces: [hvt@localhost Sandbox]$ ghc --make Main.hs -O [5 of 6] Compiling Abduce ( Abduce.hs, Abduce.o ) Abduce.hs:110:0: Illegal instance declaration for `Poset RuRe' (The instance type must be of form (T a b c) where T is not a synonym, and a,b,c are distinct type variables) In the instance declaration for `Poset RuRe' I've tried several changes, like not using the type synonym, but can't get it right. (I'm using the ghc 6.6.1 Fedora Core 6 package). Many thanks in advance! Hans van Thiel

2 2

What really happens
by Andrew Coppin 19 May '07

19 May '07

Hi everybody. Conceptually, all "ordinary" data structures in Haskell are immutable. For example, map (2*) takes a list and generates a completely separate, *new* list. And conceptually, SELECT * FROM customer, order WHERE order.cid = customer.cid; computes the extended Cartesian product of the two tables and then restricts the result according to the predicate. Which is, of course, *absurdly* inefficient. However, no sane database engine in Creation actually *does* it this way. ;-) It's just that conceptually, that's how the result is defined. Is there any circumstances under which an expression like map (2*) would perform an in-place update rather than generating a new list? (Obviously this depends on which compiler we're talking about. I'm implicitly assuming GHC.) Assuming the old list isn't needed again, an in-place update is obviously significantly cheaper. (Less RAM used, less time allocating RAM, less GC time, etc.) For something like an integer which can be "unboxed", you could write a very tight loop of machine code to perform a multiplication by 2 over a single-linked list. Similarly, according to the rules, something like length . filter odd will take a list, generate a new list containing only the odd elements, and then proceed to count the size of that list and throw the list itself away. I might hope that this would be "optimized" into a tight loop of machine code that actually just traverses the original linked list and increments a CPU register with the count of odd elements found. But is GHC actually that cleaver? I spend lots of time telling people that Haskell compilers can actually make big optimizations like this, and coding my own stuff as if this will happen, but is it actually so? Am I assuming the optimizer is all-powerful when in fact it's not? Similarly, I could ask lots of other, related questions to the above. (E.g., can all types be optimized like this, or is it only built-in lists?) And I know of no way of finding answers, other than pestering the people on this mailing list. (Certainly I don't know enough about IA32 assembly to take apart the actual compiled code and see what it does.) Anybody have anything useful to say on the matter?

2 1

Short and sweet
by Andrew Coppin 19 May '07

19 May '07

Greetings. Can anybody tell me what complexity class "nub" belongs to? (The implementation in the Language Report appears to have n^2 complexity. Do the actual implementations out there follow?)

5 6

Made me smile
by Andrew Coppin 19 May '07

19 May '07

OK, so I was hanging out on this newsgroup I often lurk. And we're having a discussion. And I'm all like "Haskell is the greatest!" And they're all like "nah, Haskell sux". And this one dude goes "hey, look at this C++ code. How do you do that in Haskell?" And three other people look at this C++ and can't figure out what the heck it even does. So eventually he tells us what it does, and so I post some Haskell in a reply. And the some other guy writes this... (OK, not much point to this email. But it seriously made me LOL IRL!) Invisible wrote: >>>> int main() >>>> { >>>> typedef std::istream_iterator<std::string> Is; >>>> typedef std::ostream_iterator<std::string> Os; >>>> std::set<std::string> t((Is(std::cin)), Is()); >>>> std::copy(t.begin(), t.end(), Os(std::cout, "\n")); >>>> } > OK then. > main = interact $ unlines . sort . nub . words Pwned! -- Darren New / San Diego, CA, USA (PST) His kernel fu is strong. He studied at the Shao Linux Temple.

3 4

Picking an architecture for a Haskell web app
by Joel Reymont 19 May '07

19 May '07

Folks, I have finished an alpha version of my EasyLanguage [1] to C# compiler and need to deploy it on Amazon EC2/S3. The compiler web interface is very simple: paste EL code, get back C# code or the same EL code with the error highlighted. I view the site as more than just a compiler, though, and want a blog, forums, etc. Last but not least, I want to be able to update portions of the site without shutting it down. My choice seems to boil down to HAppS [2], HOPE [3], or a combination of Ruby/Rails with Lambdabot. At first glance, HAppS lacks publishing (my ultimate need) but promises an interface to S3 sometime in the future. My understanding is that it's ready but is not being released. HAppS is heavy on features that I may not make use of. I had a hard time understanding the HPaste [4] code written using HAppS and I don't fancy using XSLT as my HTML template language. HOPE has a publishing framework (blog, RSS, comments). I could write the forums or just use Google Groups. I like the module system and the FCGI interface should let me couple HOPE with Lighty [5]. The HOPE code base looks clean and simple and I'm guessing that adding Lambdabot-style dynamic loading of modules would be straightforward. Overall, HOPE has everything that I need, without unnecessary extras. It does not have an interface to Amazon S3, though, and I would need that to rewrite the storage bits to use S3 instead of a regular database. Lambdabot by itself doesn't offer much apart from robust dynamic loading of Haskell code. Its features have been heavily tested, though, which gives me a warm feeling. I'm thinking that the same hot- loading technology that Lambdabot uses could be coupled with either HAppS or HOPE. Lambdabot has a FCGI which should make mixing it with HOPE particularly easy. Going with Ruby and Rails I will have everything I need and more. The compiler could run in a separate server (think Lambdabot) but I would need to manage two different platforms. Is my assessment correct? Did I miss anything? What approach do you favor? Thanks, Joel P.S. I have the same compiler written in OCaml which is what I started with. Developing it has been a relative breeze but deploying on the web was a tale of frustration. I gave up and finished the Haskell version. [1] http://lambda-the-ultimate.org/node/2201 [2] http://happs.org/HAppS/README.html [3] http://hope.bringert.net/about [4] http://hpaste.org [5] http://www.lighttpd.net/ -- http://wagerlabs.com/

9 19

where do I point the type annotations
by Alex Jacobson 19 May '07

19 May '07

I am playing with using SYB to make generic indexed collections. The current code is this: data Syb = Syb [Dynamic] -- list of [Map val (Set a)] empty item = Syb $ gmapQ (toDyn . emp item) item where emp::x->y->Map.Map y (Set.Set x) emp x y = Map.empty insert x (Syb indices) = Syb $ zipWith f indices (gmapQ toDyn x) where f dynIndex dynAttr = toDyn $ Map.insert attr (maybe (Set.singleton x) (Set.insert x) $ Map.lookup attr index) index where index = fromJust $ fromDynamic dynIndex attr = fromJust $ fromDynamic dynAttr e = empty i where i=i::Test t1 = Test "foo" 2 c1 = insert t1 e Which causes the following error (the line numbers are wrong because there was other code in the original): Ambiguous type variable `a' in the constraints: `Ord a' arising from use of `insert' at Main.hs:113:5-15 `Typeable a' arising from use of `insert' at Main.hs:113:5-15 Probable fix: add a type signature that fixes these type variable(s) What am I doing wrong? Is there a better way to define insert that does not have this problem? Note: I also tried doing this so that each attribute tried to find a matching index using fromDynamic, but that gave me an error involving gmapQ not have an Ord constraint. -Alex-

2 1

Help with Programming in Haskell example
by Andre Nathan 19 May '07

19 May '07

Hello I've been reading Programming in Haskell, and I'm trying to go through the parser examples in chapter. However, I'm getting a type error when using the "do" notation. Here's the code I'm trying to load in ghci, which is copied from the book: import Prelude hiding ((>>=), return) import Char type Parser a = String -> [(a, String)] return :: a -> Parser a return v = \inp -> [(v, inp)] failure :: Parser a failure = \inp -> [] item :: Parser Char item = \inp -> case inp of [] -> [] (x:xs) -> [(x, xs)] parse :: Parser a -> String -> [(a, String)] parse p inp = p inp (>>=) :: Parser a -> (a -> Parser b) -> Parser b p >>= f = \inp -> case parse p inp of [] -> [] [(v, out)] -> parse (f v) out p :: Parser (Char, Char) p = do x <- item item y <- item return (x, y) The problem is in the definition of "p": Couldn't match expected type `Char' against inferred type `[(Char, String)]' In the expression: x In the first argument of `return', namely `(x, y)' In the expression: return (x, y) Now if I define p as p :: Parser (Char, Char) p = item >>= \x -> item >>= \_ -> item >>= \y -> return (x, y) it works fine, so I'm wondering what else I need to do for the "do" notation to work. Thanks in advance, Andre

2 2

Module dependency graph generator
by Alfonso Acosta 19 May '07

19 May '07

Hi all, I'm searching for a tool which generates a module dependency graph (a graphviz backend would be more than enough). Does anybody know a tool with such functionality? Cheers, Fons

2 1

Quick Sort Algorithm
by PR Stanley 19 May '07

19 May '07

Hi folks qSort (x:xs) = qSort smaller ++ [x] ++ qSort larger where smaller = [a | a . xs, a x ] larger = [b | b . xs, b > x ] Any idea why I can't get this to work? Thanks, Paul

5 9