Send Beginners mailing list submissions to beginners@haskell.org To subscribe or unsubscribe via the World Wide Web, visit http://www.haskell.org/mailman/listinfo/beginners or, via email, send a message with subject or body 'help' to [EMAIL PROTECTED]
You can reach the person managing the list at [EMAIL PROTECTED] When replying, please edit your Subject line so it is more specific than "Re: Contents of Beginners digest..." Today's Topics: 1. Re: [Haskell-cafe] ANNOUNCE: Haskell Communities and Activities Report (15th ed., November 2008) (Don Stewart) 2. Re: Re: Installing Gtk2hs (Duncan Coutts) 3. Re: Re: Installing Gtk2hs (Duncan Coutts) 4. Re: Memoization (Apfelmus, Heinrich) 5. Re: ANNOUNCE: Haskell Communities and Activities Report (15th ed., November 2008) (Benjamin L.Russell) 6. What causes <<loop>>? (Martin Hofmann) 7. Special session on Haskell language (John Edward) ---------------------------------------------------------------------- Message: 1 Date: Fri, 28 Nov 2008 16:15:30 -0800 From: Don Stewart <[EMAIL PROTECTED]> Subject: [Haskell-beginners] Re: [Haskell-cafe] ANNOUNCE: Haskell Communities and Activities Report (15th ed., November 2008) To: Janis Voigtlaender <[EMAIL PROTECTED]> Cc: [EMAIL PROTECTED], [EMAIL PROTECTED], [EMAIL PROTECTED], beginners@haskell.org, [EMAIL PROTECTED], [EMAIL PROTECTED] Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain; charset=us-ascii Good work! It is always interesting to see the secret Haskell projects that only get announced via the HCAR. Things not on haskell@ or on hackage. For example, this under-the-radar project: http://www.haskell.org/communities/11-2008/html/report.html#sect7.7 7.7 IVU Traffic Technologies AG Rostering Group Haskell to solve constraints on EU bus timetables! In production use! -- Don voigt: > On behalf of the many, many contributors, I am pleased to announce > that the > > Haskell Communities and Activities Report > (15th edition, November 2008) > > http://www.haskell.org/communities/ > > is now available from the Haskell Communities home page in PDF and > HTML formats. ------------------------------ Message: 2 Date: Sun, 30 Nov 2008 22:33:54 +0000 From: Duncan Coutts <[EMAIL PROTECTED]> Subject: Re: [Haskell-beginners] Re: Installing Gtk2hs To: Colin Paul Adams <[EMAIL PROTECTED]> Cc: beginners@haskell.org Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain On Sun, 2008-11-30 at 09:08 +0000, Colin Paul Adams wrote: > Colin> Now make fails with: > > Colin> svgcairo/Graphics/Rendering/Cairo/SVG.chs:201:2: Couldn't > Colin> match expected type `()' against inferred type `CInt' > Colin> Expected type: Render () Inferred type: Render CInt In the > So I tried changing Render () to Render CInt in four places in > SVG.chs. Aye, the cairo C library changed it's API from 1.6 to 1.8. It added an int return type to several functions that previously returned void. > Now it installs OK with 6.8.3, and all the demos run. > > I'd have a go at getting it to work with 6.10.1 if I knew what to do. > It appears the library structure has changed incompatibly (and ghc > didn't even change its version number - that's pretty bad). The version of ghc did change of course, 6.8 -> 6.10, but perhaps you mean the versions of the libraries? They changed also, to reflect the API changes. > Is there a document anywhere that details the structure changes? Yes, the ghc-6.10 release notes. Duncan ------------------------------ Message: 3 Date: Sun, 30 Nov 2008 22:43:45 +0000 From: Duncan Coutts <[EMAIL PROTECTED]> Subject: Re: [Haskell-beginners] Re: Installing Gtk2hs To: Colin Paul Adams <[EMAIL PROTECTED]> Cc: beginners@haskell.org Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain On Sun, 2008-11-30 at 09:24 +0000, Colin Paul Adams wrote: > >>>>> "Colin" == Colin Paul Adams <[EMAIL PROTECTED]> writes: > > Colin> Now it installs OK with 6.8.3, and all the demos run. > > Well, not quite all: > > mozembed fails to compile with: > > TestEmbedMoz.hs:5:7: > Could not find module `Graphics.UI.Gtk.MozEmbed': > Use -v to see a list of the files searched for. > make: *** [testembedmoz] Error 1 This almost certainly is because you didn't build the mozembed component of gtk2hs. The ./configure script lists all the bits that it's going to build. By default if the corresponding C devel package is not available then the binding will not be built. If you really want to build it then use ./configure --enable-firefox or --enable-xulrunner and it will stop and report exactly what bits it needed but could not find. > And the svgviewer programs fail at runtime with: > > svgviewer: user error (Pattern match failure in do expression at > SvgViewer.hs:11:2-9) That's kind of by design, it's a simple demo program that does no error checking on the command line arguments. See that line in the source code: (file:_) <- getArgs So if you call it with a single .svg file parameter it should work. > and: > > svg2png: user error (Pattern match failure in do expression at > Svg2Png.hs:9:2-18) Same issue. > and for treelist: > > make: *** No rule to make target `TreeSort.hs', needed by `treesort'. Stop. Good catch, that file is missing from the tarball. > and for opengl: > > ghc --make RotatingCube.hs -o cube > > RotatingCube.hs:7:17: > Could not find module `Graphics.UI.Gtk.OpenGL': > Use -v to see a list of the files searched for. > make: *** [cube] Error 1 Same as the fist problem. You built gtk2hs without the opengl component. Use ./configure --enable-opengl and it'll tell you what you're missing. > and for sourceview: > > ghc --make SourceViewTest.hs -o sourceview > > SourceViewTest.hs:5:7: > Could not find module `Graphics.UI.Gtk.SourceView': > Use -v to see a list of the files searched for. > make: *** [sourceview] Error 1 Same problem again, but for the sourceview component. ./configure --enable-sourceview Basically you need to install a bunch of -devel fedora packages so that the Haskell bindings can be built. The thing to check is the summary produced at that end of running ./configure Duncan ------------------------------ Message: 4 Date: Mon, 01 Dec 2008 11:02:08 +0100 From: "Apfelmus, Heinrich" <[EMAIL PROTECTED]> Subject: [Haskell-beginners] Re: Memoization To: beginners@haskell.org Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain; charset=ISO-8859-1 abdullah abdul Khadir wrote: > Hi, > I am a student and we had an assignment in Haskell. The question, was > given a string of the form "1-2+3*5-7+4-6+3" i.e., any sequence of integers > as well as some operators between them we had to find a maximum possible > value for the expression as well as the expression itself . So for maxval > "1-2+3*5-7+4-6+3" it is (76,"(1-((2+3)*((5-(7+4))-(6+3))))"). The function > we had to write was maxval :: String -> (Int,String). For further details on > the question, have a look at our sir's web page > here<http://www.cmi.ac.in/%7Emadhavan/courses/programming08/assignment6.txt>. > > I solved the question, we had to use memoization, and submitted the > solution. It is given below. Now the problem is I am just wondering if it > can be solved in a better manner. Translation : Is there some way in Haskell > to do it in a more simpler way and as well as to reduce the number of lines > of the program. Yes, your solution can be made more beautiful. Let me show how. First of all, we should separate *parsing* the input into a list of numbers and operations from *computing* the result. maxval :: String -> (Int, String) maxval = compute . parse In other words, parse extracts the numbers and arithmetic operations from the input. One example implementation is type Op = Char parse :: String -> ([Int], [Op]) parse [] = ([],[]) parse s = let (n,s2) = parseInt s in case s2 of [] -> ([n],[]) op:s3 -> let (ns,ops) = parse s3 in (n:ns,op:ops) parseInt :: String -> (Int, String) parseInt s = (n, s') where (digits, s') = span isDigit s n = foldl (\x c -> 10*x + fromDigit c) 0 digits fromDigit c = ord c - ord '0' but it's more complicated then necessary. We should at least use the reads functions from the Prelude . And in any case, *parser combinators* are the best way to parse something. But for now, the straightforward way above shall suffice. Second, we can considerably clarify things by defining new types. Our first abstraction is the *expression* type Expr = (Int,String) value :: Expr -> Int value = fst which consists of a value and its textual representation. For instance, (20, "((6*3)+2)") (30, "(6*(3+2))") are expressions. We can combine two expression by applying one of our arithmetic operations both to the value and the textual representation applyExpr :: Op -> Expr -> Expr -> Expr applyExpr op (x,ex) (y,ey) = (f op x y, "(" ++ ex ++ [op] ++ ey ++ ")") where f '+' = (+) f '-' = (-) f '*' = (*) Our main algorithm will choose maximal and minimal values from a set of possible expressions. Therefore, we introduce the following type data MinMax = M Expr Expr deriving (Show) which represents a range of values by recording expressions of minimal and maximal value. maxexpr :: MinMax -> Expr maxexpr (M _ e) = e We can merge two such ranges ("union") by choosing the lower first and the higher second part: merge :: MinMax -> MinMax -> MinMax merge (M x y) (M x2 y2) = M emin emax where emin = if value x < value x2 then x else x2 emax = if value y > value y2 then y else y2 merges :: [MinMax] -> MinMax merges = foldr1 merge fromExpr :: Expr -> MinMax fromExpr e = M e e Now, we also want to apply arithmetic expressions to these ranges. For '+','-' and '*', the following function does the right thing: applyMinMax :: Op -> MinMax -> MinMax -> MinMax applyMinMax op (M x y) (M x2 y2) = merges [fromExpr (applyExpr op z z2) | z<-[x,y], z2<-[x2,y2]] With these preliminaries, we can now express the algorithm. The main ingredient is a function (f :: Int -> Int -> MinMax) that calculates the range of possible values for expression that only utilize numbers between the positions i and j in the list. And as common in dynamic programming, we employ a memo table to store the intermediate results. compute :: ([Int], [Op]) -> Expr compute (xs,ops) = maxexpr (f 1 n) where n = length xs f = memoize n f' f' i j | i == j = let x = xs !! (i-1) e = (x,show x) in fromExpr e | otherwise = merges [applyMinMax (ops !! (k-1)) (f i k) (f (k+1) j) | k <- [i..(j-1)]] Where exactly is the memo table? It's hidden in memoize :: Int -> (Int -> Int -> a) -> (Int -> Int -> a) memoize n f = \i j -> table ! (i,j) where table = array ((1,1),(n,n)) [((i,j), f i j) | i<-[1..n], j<-[1..n]] which takes a function of two arguments from 1 to n and tabulates its values in an array. (You need to import Data.Array for the arrays.) In other words, f tabulates the results of f' which in turn uses the tabulated values returned by f to compute its results. Thanks to lazy evaluation, this "tabulate the result before it's available" works. To summarize, the key points of the new solution are * Parse input. * Abstractions. * Memoization is a simple higher order function. But there is more. Namely, there are many different ways to implement the memoization. I used an array, you were asked to use a linked list. The former is O(1) the latter O(n). There is a way to do it with plain trees but still O(1), see also section 3 of Richard Bird and Ralf Hinze. "Trouble Shared is Trouble Halved" http://www.informatik.uni-bonn.de/~ralf/publications/HW2003.pdf And there is even more! Namely, we knew that the problem is an instance of dynamic programming, we knew the algorithm before implementing it. But how to find the algorithm in the first place? Well, the usual answer is "by thinking hard". However, there are very systemic ways to derive dynamic programming algorithms from just the problem specification! In a sense, much of the work of R. Bird centers this topic. The book "Algebra of Programming" http://web.comlab.ox.ac.uk/oucl/research/pdt/ap/pubs.html#Bird-deMoor96:Algebra is one of the cornerstones. The systematic derivation of dynamic programming algorithms has been rediscovered in a more direct but less general fashion http://bibiserv.techfak.uni-bielefeld.de/adp/ Regards, H. Apfelmus ------------------------------ Message: 5 Date: Wed, 03 Dec 2008 15:39:41 +0900 From: Benjamin L.Russell <[EMAIL PROTECTED]> Subject: [Haskell-beginners] Re: ANNOUNCE: Haskell Communities and Activities Report (15th ed., November 2008) To: beginners@haskell.org Cc: [EMAIL PROTECTED], [EMAIL PROTECTED] Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain; charset=us-ascii On Fri, 28 Nov 2008 16:15:30 -0800, Don Stewart <[EMAIL PROTECTED]> wrote: >Good work! > >It is always interesting to see the secret Haskell projects that only >get announced via the HCAR. Things not on haskell@ or on hackage. > >For example, this under-the-radar project: > > http://www.haskell.org/communities/11-2008/html/report.html#sect7.7 > > 7.7 IVU Traffic Technologies AG Rostering Group > >Haskell to solve constraints on EU bus timetables! In production use! Speaking of production use, one type of project that would be interesting would be a study examining how Haskell can increase programmer productivity for production use for programmers who are not necessarily gifted in programming, but whose forte may lie in another field and who are very interested in functional programming; i.e., some type of tabulated data (preferably a graph, although a table would work, too) of data quantifying how useful Haskell is in allowing one whose forte may not necessarily be in programming (say, a physicist, mathematician, or even a translator who happens to have an algorithmically-focused computer science degree) to equal or excel the productivity of, say, a gifted C/C++ programmer in, say, setting up a commercial Web site. The reason is that recently, there has been news of people in academia leaving for other realms because of worsening conditions (see "As strikes begin, lecturer quits to become plumber" at http://www.guardian.co.uk/uk/2004/feb/24/lecturerspay.highereducation, and "Why I am Not a Professor OR The Decline and Fall of the British University" at http://www.lambdassociates.org/blog/decline.htm). Up to know, my dream was to publish a paper on type theory to motivate study of Haskell, but now it looks like I may need to aim for creating a commercial Web site. However, I am not sure of being able to compete with commercial Web sites, because I am more of a writer/translator who happens to like functional programming than a real-life programmer. I've already seen such articles as "Why Functional Programming Matters" (see http://www.md.chalmers.se/~rjmh/Papers/whyfp.html), "Why Haskell Matters" (see http://www.haskell.org/haskellwiki/Why_Haskell_matters), and "Beating the Averages" (see http://www.paulgraham.com/avg.html). However, these essays tend to focus on how a functional language FL is structurally better than non-functional languages NFL in general, without specifying the skill-level of the programmer. Instead, it would be interesting to find the minimum skill-level s necessary for, say, somebody whose forte is not in programming, but who, say, studies functional programming as a hobby, to use Haskell as a tool in achieving a productivity level equivalent to that of a gifted C/C++ programmer. To sum: Can a theoretically-minded Haskell student who studies Haskell out of interest in type theory compete with star C/C++ programmers in developing, say, commercial Web sites? This is not quite clear, because even if Haskell can increase programmer productivity by tenfold, a star programmer can also be more productive than an average programmer by tenfold. How risky is this challenge? -- Benjamin L. Russell > >-- Don > > >voigt: >> On behalf of the many, many contributors, I am pleased to announce >> that the >> >> Haskell Communities and Activities Report >> (15th edition, November 2008) >> >> http://www.haskell.org/communities/ >> >> is now available from the Haskell Communities home page in PDF and >> HTML formats. -- Benjamin L. Russell / DekuDekuplex at Yahoo dot com http://dekudekuplex.wordpress.com/ Translator/Interpreter / Mobile: +011 81 80-3603-6725 "Furuike ya, kawazu tobikomu mizu no oto." -- Matsuo Basho^ ------------------------------ Message: 6 Date: Wed, 03 Dec 2008 10:25:07 +0100 From: Martin Hofmann <[EMAIL PROTECTED]> Subject: [Haskell-beginners] What causes <<loop>>? To: beginners@haskell.org Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain I've already posted this mail on haskell-cafe, but apparently the subject suggested a too simple question, so I try it here again. I am picking up a discussion with the same topic from haskell-users on 8th November. Thunks with reference on themselves was mentioned as main reason for <<loop>>. > A safe recursive definition would be > let x = Foo (x+1) > However, if you leave out the constructor, > let x = x + 1 > you get a <<loop>> (or a deadlock). > Are there any other reasons? I am trying to debug monadic code which stores state information in a record maintaining several Data.Maps, but in vain so far. A state is modified/changed in several steps by a compound function i.e. changeA $ changeB $ changeC state Could this also lead to a deadlock? If so, can I prevent this using CPS? If the state transformation is the main purpose/computation of the monad at all, is it better to use CPS? Is code using mtl, records or Data.Map more prone to <<loop>> or does this not matter at all. How can I identify self-referencing thunks more easily? Is there any rule of thumb to prevent <<loop>>? Are there any less obvious newbie mistakes causing <<loop> then the one above? Sorry, a lot of questions at once, but I am kind of helpless because I can't find any reason of my <<loop>>, so any comments, experience, and tips are highly appreciated. Thanks, Martin ------------------------------ Message: 7 Date: Wed, 3 Dec 2008 17:57:21 -0800 (PST) From: John Edward <[EMAIL PROTECTED]> Subject: [Haskell-beginners] Special session on Haskell language To: beginners@haskell.org Message-ID: <[EMAIL PROTECTED]> Content-Type: text/plain; charset="iso-8859-1" Special session on Haskell language at MULTICONF-09 call for papers Special session on Haskell language will be held at the 2009 Multi Conference in Computer Science, Information Technology and Control systems and Computational Science and Computer Engineering (MULTICONF-09) (website: http://www.PromoteResearch.org) and it will be held during July 13-16 2009 in Orlando, FL, USA. We invite draft paper submissions. The event consists of the following conferences: · International Conference on Artificial Intelligence and Pattern Recognition (AIPR-09) · International Conference on Automation, Robotics and Control Systems (ARCS-09) · International Conference on Bioinformatics, Computational Biology, Genomics and Chemoinformatics (BCBGC-09) · International Conference on Enterprise Information Systems and Web Technologies (EISWT-09) · International Conference on High Performance Computing, Networking and Communication Systems (HPCNCS-09) · International Conference on Information Security and Privacy (ISP-09) · International Conference on Recent Advances in Information Technology and Applications (RAITA-09) · International Conference on Software Engineering Theory and Practice (SETP-09) · International Conference on Theory and Applications of Computational Science (TACS-09) · International Conference on Theoretical and Mathematical Foundations of Computer Science (TMFCS-09) The website http://www.PromoteResearch.org contains more details. Sincerely John Edward Publicity committee -------------- next part -------------- An HTML attachment was scrubbed... URL: http://www.haskell.org/pipermail/beginners/attachments/20081203/2b0f6236/attachment.htm ------------------------------ _______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners End of Beginners Digest, Vol 6, Issue 1 ***************************************