- Haskell-Cafe - Haskell.org

Buddha and GHC 6.4
by Jim Apple 21 Jun '05

21 Jun '05

Has anyone gotten Buddha (now called "plargleflarp" http://www.cs.mu.oz.au/~bjpop/buddha/) do work with GHC 6.4? I'm getting ghc-6.4: unknown package: buddha Jim P.S. What happened to the old name?

4 6

Announcing cross-platform implementation of Pan
by Sean Seefried 19 Jun '05

19 Jun '05

Hi all, I'd like to announce a new cross-platform implementation of Conal Elliott's image synthesis language - Pan. For more information see: http://www.cse.unsw.edu.au/~sseefried/pan/ This is very much an alpha release of the software. I have only built and tested it on Mac OS X and Linux, although it has been tested on Windows by another. Features: * Uses Don Stewart's hs-plugins library to dynamically load and display effects. * Cross-platform. Uses Daan Leijen's wxHaskell and Sven Panne's HOpenGL libraries. * Uses the Haskell Cabal libraries. Builds with version released in GHC 6.4. Drawbacks: * Not as fully featured as the original. * Not as fast. Implemented directly in Haskell instead of generating C code. Sean

1 0

Functional Programming lecture on video
by Carsten Otto 17 Jun '05

17 Jun '05

Hello! I am student at the RWTH Aachen (Germany) and this semester professor Giesl is lecturing "Functional Programming". In the first part of this lecture Haskell is presented and all basic concepts are explained (recursion, pattern matching, lambda expressions, user declared data types, ...). Later in this lecture the theoretical background is the main topic (semantics, lambda calculus, ...). If you are interested, you can watch this lecture on video: http://video.s-inf.de/#FP.2005-SS-Giesl.(COt).HD_Videoaufzeichnung The lecture of course is being held in English. The video is encoded with XviD 1250 KBit and 64 KBit Mono-MP3. The download-server is connected with about 100 MBit, so your download should be quite fast. Have fun, -- Carsten Otto carsten.otto(a)gmail.com www.c-otto.de

1 0

Hugs parse error in library file
by james pentland 17 Jun '05

17 Jun '05

i am working on ch 15, School of Expression. unfortunately, import Memo causes an Hugs error (see below). also, memoB in ch 15 calls memo1, but there is no memo1 in h:\Program Files\Hugs98\libraries\Hugs\Memo.hs this module contains memoN :: Int -> (a -> b) -> (a -> b) memoN = mkMemo eql hash of course, it should be easy enough to write memo1 :: (a -> b) -> (a -> b) memo1 = memoN 1 Memo.hs imports ST, which is where Hugs reports a parse error. h:\Program Files\Hugs98\libraries\Hugs\ST.hs contains at line 50 newtype ST s a = ST (forall r. (a -> r) -> r) what is the workaround? pentland@thetis /ntd/lo $ hugs Hugs session for: H:\Program Files\Hugs98\libraries\Hugs\Prelude.hs H:\Program Files\Hugs98\libraries\Prelude.hs H:\Program Files\Hugs98\libraries\Hugs\Base.hs Type :? for help Hugs.Base> :v -- Hugs Version 20050113 Hugs.Base> :load xva ERROR "H:\Program Files\Hugs98\libraries\Hugs\ST.hs":50 - Syntax error in type expression (unexpected `.') Animation> pentland@thetis /ntd/lo $ cat xva.hs import Animation (picToGraphic) import Shape import Picture import Memo import SOEGraphics hiding (Region, Event) import qualified SOEGraphics as G (Region, Event) import Draw (xWin,yWin,intToFloat) import Win32Misc (timeGetTime) -- import Word (word32ToInt) import Channel type Time = Float type UserAction = G.Event newtype Behavior a = Behavior (([Maybe UserAction],[Time]) -> [a]) newtype Event a = Event (([Maybe UserAction],[Time]) -> [Maybe a]) time :: Behavior Time time = Behavior (\(_,ts) -> ts) __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

2 1

(small) code review request
by Radu Grigore 16 Jun '05

16 Jun '05

The programming language I know best is C++. Wait, don't close the message. I also know OCaml and a couple of days ago I read "A Gentle Introduction to Haskell". In order to practice what I've learned a bit above "hello world" programs I chose to solve some easy tasks from SPOJ. They have automatic testing so I know if I got it right or not and I can also look at submission statistics (number and accuracy) to choose easy problems. Aside from "easiness" I've chosen at random these: https://spoj.sphere.pl/problems/ADDREV/ https://spoj.sphere.pl/problems/CRSCNTRY/ So these are my first two Haskell "programs" and I'd appreciate any comments you might have, especially better ways of solving the problems. The first one asks you to print rev(rev a + rev b) for two numbers a and b where rev is a function that transforms an integer into an integer you get by reversing the digits. --- BEGIN addrev.hs --- rev :: Int -> Int rev = read . reverse . show solve :: Int -> IO () solve 0 = do return () solve n = do line <- getLine let a:b:_ = words line an = read a bn = read b in (putStrLn . show . rev) (rev an + rev bn) solve (n-1) main = do hSetBuffering stdin LineBuffering line <- getLine solve (read line) --- END addrev.hs --- The second problem happens to be the Longest Common Subsequence problem, which is a classical DP problem. After searching a bit how to do memoisation/dp in Haskell I've found two resources: http://www.haskell.org/hawiki/MemoisingCafs http://portal.acm.org/citation.cfm?id=871896&coll=Portal&dl=ACM&CFID=461433… I chose to try the approach in the Bird&Hinze article. The result is my second Haskell program: --- BEGIN crscntry.lhs --- One of the problems at SPOJ, namely CRSCNTRY, asks you to implement the classical (DP) algorithm for finding the length of the longest common subsequence. The reccurence relation is: lcs [] _ = 0 lcs _ [] = 0 lcs (x:xs) (y:ys) = | x == y = 1 + lcs xs ys | otherwise = lcs (x:xs) ys `max` lcs xs (y:ys) There are of course only mn distinct calls to lcs, where m = 1 + length xs, n = 1 + length ys. I will try here a memoisation approach about which I have read in "Trouble shared is trouble halved", by Bird and Hinze. The basic idea is to explicitly construct the call tree and store in it the result of computing the function. First, note that the reccurence relation above makes either one or two calls. I think we can get by with a binary tree that has this invariant: left . right n = right . left n Let's define the tree. > data Tree a = Empty | Node { left :: Tree a, info :: a, right :: Tree a } > leaf :: a -> Tree a > leaf x = Node Empty x Empty Now imagine the tree nodes put into a matrix l l x <--- x <--- x ^ ^ ^ |r l |r l |r x <--- x <--- x We use two memoisation functions. One of them constructs all the rows above (memo_lcs), while the other reuses the nodes above and constructs only one row to the left (memo_lcs'). We also pass around the lists so that we can constructs nodes correctly. > memo_lcs :: Eq a => [a] -> [a] -> Tree Integer > memo_lcs [] _ = Empty > memo_lcs _ [] = Empty > memo_lcs (x:xs) (y:ys) = > node x y (memo_lcs' t xs (y:ys)) t > where t = memo_lcs (x:xs) ys > memo_lcs' :: Eq a => Tree Integer -> [a] -> [a] -> Tree Integer > memo_lcs' _ [] _ = Empty > memo_lcs' _ _ [] = Empty > memo_lcs' z (x:xs) (y:ys) = > node x y (memo_lcs' l xs (y:ys)) l > where l = tree_left z Both of these functions use a smart constructor. It takes the left and right branches and constructs a new node while also computing the correct value the function must have. > node :: Eq a => a -> a -> Tree Integer -> Tree Integer -> Tree Integer > node x y l r > | x == y = Node l (1 + (value . tree_left) r) r > | otherwise = Node l (value l `max` value r) r The inspection of the value returns 0 for empty nodes. > value :: Tree Integer -> Integer > value Empty = 0 > value (Node _ r _) = r You might be wondering by now what is the function tree_left. > tree_left :: Tree a -> Tree a > tree_left Empty = Empty > tree_left (Node l _ _) = l (I wonder if all this would be simpler if I'd use a border of 0-valued leafs instead of the functions tree_left and value. I'll try soon.) Now the definition of lcs is simple. > lcs :: Eq a => [a] -> [a] -> Integer > lcs x y = value (memo_lcs x y) This is the basic solution of the problem CRSCNTRY. A testcase is just a bit more complicated. > testcase :: [[Integer]] -> Integer > testcase (x:xs) = foldl max 0 (map (lcs x) xs) In order to finish we just need to take care of the IO. > myReadList :: String -> [Integer] > myReadList s = > let (a, t) = head (lex s) in > case read a of > 0 -> [] > n -> n : (myReadList t) > readTest :: IO [[Integer]] > readTest = do > line <- getLine > case myReadList line of > [] -> do return [] > lst -> do > rest <- readTest > return (lst : rest) The solve function reads n tests and solves each of them. > solve :: Integer -> IO () > solve 0 = return () > solve (n+1) = do > test <- readTest > putStrLn (show (testcase test)) > solve n In the main function we read the number of tests we should handle and then solve them > main = do > line <- getLine > solve (read line) That's it. I hope it works (fast enough). --- END crscntry.lhs --- It worked fast enough. Anyway, I was wondering if the O(n) space and O(n^2) time solution can be implemented in Haskell. Another way to ask this. Consider the classic fibonacci example. Can one compute the n-th fibonacci number in O(n) time and O(1) space, i.e. remember only the "last" two values during computation? -- regards, radu http://rgrig.blogspot.com/

2 3

RE: [Haskell-cafe] Garbage collection and finalizer thread priority
by Simon Marlow 16 Jun '05

16 Jun '05

On 13 June 2005 14:32, Gracjan Polak wrote: > Simon Marlow wrote: >> >> I presume you're running GHC. There's no way to increase the >> priority of a thread - GHC's scheduler doesn't have a concept of >> priorities. >> > > Yes, I forgot to state it explicitly. > >> I would look into whether you can use mallocForeignPtr: this is much >> faster than using newForeignPtr with finalizerFree, because the >> memory is garbage collected directly and there's no need for a >> finalizer. > > I use mallocBytes + reallocBytes + addForeignPtrFinalizer > finalizerFree. I wouldn't think this is any different, thanks for > your suggestion. > > May I ask where that difference comes from? mallocBytes allocates memory using C's malloc(), which is expensive. Also, the finalizer to free the memory is also expensive. mallocForeignPtr on the other hand allocates memory directly in GHC's heap (much faster than malloc()), and the memory is garbage collected when it is no longer referenced, so there's no need for the finalizer. Still, ForeignPtr is quite a bit slower than Ptr. We have some ideas for improving it, which I'll hopefully get round to implementing sometime. Cheers, Simon

1 0

RE: [Haskell-cafe] Garbage collection and finalizer thread priority
by Simon Marlow 16 Jun '05

16 Jun '05

On 13 June 2005 16:55, Sebastian Sylvan wrote: > On 6/13/05, Simon Marlow <simonmar(a)microsoft.com> wrote: > >> I presume you're running GHC. There's no way to increase the >> priority of a thread - GHC's scheduler doesn't have a concept of >> priorities. >> > > Just out of curiousity, what scheme does GHC use for scheduling > threads? Just round-robin, at the moment. Cheers, Simon

1 0

Annotating calculations
by Rene de Visser 16 Jun '05

16 Jun '05

Hello, I have a somewhat complicated calculation programmed in Haskell. This calculation is coded without using monads. I want to also produce a report describing the details of this calculation for each particular set of inputs. e.g. Number of hours worked = 100. Gross pay per hour = 50. Total gross = 100 * 50 = 500. etc. But about 20 times more complicated than the above. Naturally I need to write functions to produce the above description/report as it should be well presented. Only showing the important parts of the calculation in a sensible order. But I am wondering how to combine the generation of the report with the calculation together. I think if I add the report generating functions into the calculation functions, it will make them twice as messy, and they are already complicated enough. On the other hand replicating the calculation source code twice, once without reporting and once without seems bad. Any suggestions on how to handle this? Rene.

6 7

Documentation of Data.Map
by Shiqi Cao 16 Jun '05

16 Jun '05

Hi, I just read the API of Data.Map and the source code of it. The documentation of "insertWithKey" is not precise. The following is copied from API. *insertWithKey* :: Ord <http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Prelude.html#t%3AOrd> k => (k -> a -> a -> a) -> k -> a -> Map <http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Data.Map.html#t%3AM…> k a -> Map <http://www.haskell.org/ghc/docs/6.4/html/libraries/base/Data.Map.html#t%3AM…> k a /O(log n)/. Insert with a combining function. This function take a function to solve collision, which can be considered as an operator. However the documentation does not specify the order of arguments to the operator. Because of that we can only supply operator which is communitive. But we all know that there must exist an ordering of arguments. I explored the source code of it as the following. -- | /O(log n)/. Insert with a combining function. insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a insertWithKey f kx x t = case t of Tip -> singleton kx x Bin sy ky y l r -> case compare kx ky of LT -> balance ky y (insertWithKey f kx x l) r GT -> balance ky y l (insertWithKey f kx x r) EQ -> Bin sy ky (f ky x y) l r By the last line the ordering is clear such that the inserted value goes the first. Shiqi Cao

1 0

Trivial question... solve_qe
by Matej 'Yin' Gagyi 15 Jun '05

15 Jun '05

Hi all! I'm new to Haskell... absolutely new. I need some practice, but little problem seems to me like unresolvable... Is there some tutorial of "Exercise, set of resolutions" pairs type? My english is very bat, so there is it in a picture: Exercise 1: hello world Hint: use 'putStrLn' Resolution 1.1 Resolution 1.2 Exercise 2: write functions 'max_num', 'solve_quad_equation', 'reverse_ary' Hint: (Explanation of some technics) Res... Excercise 3: Use do-notation to reverse word in a line read from stdin Hint: Use Exercise 2... (Explain how 'do' works and what to do in common error sitations) So, in a word: I need a tutorial for dummies Now, my current problem is: my program for solving quadratic equation won't compile... import System solve_qe :: Maybe (Double, Double, Double) -> Maybe (Double, Double) solve_qe Nothing = Nothing solve_qe (a, b, c) | d >= 0 = Just ((-b + (sqrt d)) / (2 * a), (-b - (sqrt d)) / (2 * a)) | otherwise = Nothing where d = b^2 - 4*a*c evalArgs :: [String] -> Maybe (Double, Double, Double) evalArgs (a:b:c:[]) = (read a, read b, read c) evalArgs _ = Nothing main = do args <- getArgs print (solve_qe (evalArgs args))

3 2