- Haskell-Cafe - Haskell.org

(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 15 Jun '05

15 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 15 Jun '05

15 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

(**) over integers
by Maurício 15 Jun '05

15 Jun '05

Hi, I'm trying to do this: let f n = mod (n**5) 12 but I see that I can't because ** only operates on floats. Is there an equivalent operator that works on integers? How should I do that? Thanks, Maurício

2 1

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

14 Jun '05

On 13 June 2005 11:30, Gracjan Polak wrote: > My space problems continued... :) > > I have some ForeignPtr's, with finalizers (finalizerFree only). And I > have lazyly produced list of those (yes, there is some unsafePerformIO > magic behind, but I think I got this right). The problem is I get > out-of-memory condition because elements get produced faster than > those consumed are garbage collected. > > Example: > > list = ... > mapM_ writeOut list > > writeOut :: Ptr Word8 > writeOut dat = do > hPutBuh handle dat 1024 > -- Control.Concurrent.threadDelay 1000 > > Uncommenting this line allows gc thread to run finalizers, memory gets > freed, everything runs smoothly... > > As far as I know finalizers are run in separate thread. How do I > increase priority of this thread so it runs faster? 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. 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. Cheers, Simon

4 7

Generic types
by Adde 14 Jun '05

14 Jun '05

I'm writing a small unit library to excercise my barely existing Haskell skills. However I can't figure out how to make Haskell accept any type of a specific class. This is what I've got so far: <code> class Unit u where shortName :: u -> String data Meter = Meter instance Unit Meter where shortName u = "m" data UnitValue = UnitValue {uUnit :: Unit u => u, uValue :: Num n => n} </code> Meter is supposed to be a type in the Unit class. UnitValue is supposed to represent unit values regardless of the Unit type. Meter appears to be a subclass of Unit, so far so good: *Units> shortName Meter "m" But I can't get UnitValue to accept Meter as a Unit: *Units> UnitValue Meter 10 <interactive>:1:10: Couldn't match the rigid variable `u' against `Meter' `u' is bound by the polymorphic type `forall u. (Unit u) => u' at <interactive>:1:0-17 Expected type: u Inferred type: Meter In the first argument of `UnitValue', namely `Meter' In the definition of `it': it = UnitValue Meter 10 I strongly suspect that I've got the declaration of UnitValue wrong but I've spent two hours searching the web and trying to get it to work without any success.

3 9

Notes and questions from a first-time Cabal user.
by Brian Smith 13 Jun '05

13 Jun '05

I succeeded in getting my project to build under Cabal. As I converted my makefile to Cabal, I took some notes about things that I found unintuitive, so that the documentation can be improved for future new users. There are some questions mixed in as well. I am using GHC, Cabal, Happy, Alex, and Haddock, all from the CVS head, all built with GHC 6.2.2, all executing under MSYS 1.0's bash 2.04.0(1) on Windows XP Pro SP2. * If I use "Executable: check-ocl2," then under Windows the executable's name really becomes "check-ocl2.exe." This is desireable behavior. But, this causes "Setup.hs copy" and "Setup.hs install" to fail because it tries to copy a file named "check-ocl2" (without the ".exe"), which obviously doesn't exist. How can I get Cabal to generate "check-ocl2.exe" on Windows and "check-ocl2" on all other platforms, and have the "copy" and "install" commands work, without using autoconf? * What is the easiest way to create a "Setup.hs all" command, analogous to "make all" that simply executes "configure." "build," "haddock," and "test" in sequence, stopping on the first failed step? * The tutorial documentation should explain how to use tools like alex and happy. As far as I could tell, the way to do this is to add "Other-Modules: Module.Name.Of.Parser.y Module.Name.Of.Lexer.x" to each executable/library stanza. But, I am not sure why this is necessary, as it seems like it should be able to find them automatically (i.e. without having to list them in the Other-Modules: field) * Is there some way to tell Cabal to generate all intermediate files into a directory that is different than the source directory? I usually keep all my sources in a "src" directory, and then generate all .hi, .o, and .hs files from Happy and Alex into a "build" directory alongside it. This way, my "src" directory only contains stuff that belongs in my version control repository, and "make clean" was simply "rm -Rf build." * If I run "runghc ./Setup.hs" I get this message: No command given (try --help). This is confusing because it isn't clear that it is a cabal error message and not a runghc error message. That is, it isn't clear whether to run "runghc --help" or "runghc Setup.hs --help," and both commands are valid. The message should be improved, or "--help" should be the default command. * Chapter 2 needs to be updated to replace "Hs-Source-Dir" with "Hs-Source-Dirs," since Hs-Source-Dir is deprecated. * It is unintuitive that the examples in chapter 2 use mixed case (e.g. "Hs-Source-Dir") while the program issues error messages using lowercase only ("hs-source-dir"). * Chapter 2 of the documentation states that identifiers can contain underscores. However, Cabal gives "*** Exception: Line 1: Parse of field 'name' failed" if I use "Name: ocl2_haskell" whereas "Name: ocl2haskell" works fine. * Chapter 2 of the documentation states that identifiers must start with a letter. However, "Name: 2" is parsed without complaint. * Chapter 2 of the documentation states that idenfiers must start with a letter. However, "letter" is not defined. Presumably the intention is to restrict identifiers to English letters only? * I originally put my "Build-depends: base" in an "Executable:" stanza. This seems reasonable because presumably different executables (and libraries) could have different dependencies, and it is advantageous to keep track of dependencies on a fine-grained basis. Yet, Cabal requires the Build-depends to be in the main stanza. Why is this? Couldn't Cabal combine all the Build-Depends it finds into the one that it puts into the final package specification? For example, my unit tests require HUnit, but nothing else does. Should I put my unit tests into a seperate package? * The error message for putting "Build-depends: base" in an "Executable: " stanza is: "*** Exception: Line 10: Unknown field 'build-depends' but I think it would be better to say *** Exception: Line 10: field 'build-depends' does not apply to executables or even better: *** Exception: Line 10: field 'build-depends' applies only to the main stanza (and similarly for other fields, e.g. "field 'main-is" applies only to executables") * Chapter 2 of the documentation states that I should be able to use syntax like "foo > 1.2" in Build-depends, but I could not get "HUnit > 1.1" or "HUnit >= 1.1" to work; they fail with parser errors. Regards, Brian

1 0