February 2010 - Beginners

Fast tree manipulation
by Gabi 04 Feb '10

04 Feb '10

Maybe Data.Sequence is a good option. Seems to be designed to give good performance when mutating If trees could be represented using Data.Sequence, I think that tree manipulation performance would be bearable. Any other libraries that might be useful? -- Regards, Gabi http://bugspy.net

2 1

wanto post haskell question
by 조광래 03 Feb '10

03 Feb '10

hi I have a question about haskell coding. Matrices One of many ways to define matrices in Haskell is the list of matrix rows, where a row is a list of double precision oating point numbers: type Matrix=[[Double]] Using this type you should define the following functions (definition of dim is given as an inspirational example). dim :: Matrix -> (Int,Int) --returns matrix dimension (number of rows and columns) dim m = if (not.isMatrix) m then error "Not a matrix" else (length m, length (head m)) isMatrix :: Matrix -> Bool --checks whether all rows have the same length isMatrix m = and [length (head m) == length a | a <- m] I have done upto here and I am stuck on multSM. multSM :: Double -> Matrix -> Matrix --multiplies a scalar and a matrix when I do: multSM d m = [[(b*a)| b<-[d], a<-(head m)]] or [map (*d) (head m)] ...I get (using Hugs): Main> multSM 3 [[2,3,4],[1,3,4],[6,3,0]] [[6.0,9.0,12.0]] So I solve 3 [2,3,4] but I do not know how to get the rest 3 [[1,3,4],[6,3,0]. Please help me on this problem.

2 1

Fast tree manipulation
by Gabi 03 Feb '10

03 Feb '10

I might be wrong but I think this is a weak spot for many functional langs, including Haskell - The ability to manipulate in high rate data structures without killing the performance . Even in langs like Clojure, which enable the cheap creation of new modified structures out of old ones(using "persistent structures") -it is much slower than using an imperative language to manipulate data in place. What is the approach of Haskell to this ? -- Regards, Gabi http://bugspy.net

3 2

Fast tree manipulation
by Gabi 03 Feb '10

03 Feb '10

I plan to implement some form of GP (GeneticProgramming) system. The trees would represent execution trees which means each node in the tree will represent a function, and leaves would represent terminals. An efficient GP system would fail if the tree manipulation operators (crossover, mutation) are slow. -- Regards, Gabi http://bugspy.net

2 1

Fast tree manipulation
by Gabi 03 Feb '10

03 Feb '10

Hi I need to manipulate trees in great numbers and frequencies (lots of trees, lots of manipulations). What would be the right approach to achieve this and get good performance ? Maybe a library already exists ? -- Regards, Gabi http://bugspy.net

2 1

Cure me of my OOP ways
by David Gordon 03 Feb '10

03 Feb '10

Hi Folks, I am redesigning a system previously implemented in C++ using Haskell. I am keen to adopt a native programming style, but certain things about the original implementation still make perfect sense to me, including the C++-style subtype polymorphism. I'd be grateful if someone could take a look at the following sample and tell me if I'm missing some neater possible implementation in Haskell. {-# OPTIONS -fglasgow-exts #-} -- for existential types -- all subclasses take the same input format and can be created factory-pattern style data Input = Input Int Int -- this is the class we have to implement when creating a 'subtype' class InternalAPI i where doitImpl :: i -> Input -> Int -- factory function, everything is initialised by giving an "i" and the Input create :: i -> Input -> PublicAPI create a b = PublicAPI a b -- this is the object clients see, regardless of the underlying implementation data PublicAPI = forall p. InternalAPI p => PublicAPI p Input doit (PublicAPI p i) = doitImpl p i -- Here's an example implementation of something trivial data Adder = Adder instance InternalAPI Adder where doitImpl _ (Input a b) = a + b -- first argument is superfluous -- There's the factory function in use: test = create Adder (Input 1 2) result = doit test I'm actually pretty happy with this. I'm not trying for a complete OOP implementation but it lets me: - have the 'base class' (InternalAPI) implement default versions of methods with full access to the 'Input' structure containing the member data - do further inheritance, since I can select the implementation of a method using that first argument (e.g. on doitImpl) - base and derived classes see the same member data - Implementations of 'InternalAPI' can reference each other through the PublicAPI interface. Admittedly it's a rather vague question. I wonder if there are any articles out there showing how to reformulate problems solved using C++-style object models into Haskell programs? After all, it's hardly as if the C++ model is particularly elegant... thanks, David

2 1

Problems installing TagSoup.Parsec
by Mark Wong-VanHaren 02 Feb '10

02 Feb '10

Hi, folks- I'm a Haskell newbie. There's a very real chance my question has a simple answer. I wish to use the library Text.HTML.TagSoup.Parsec ( http://hackage.haskell.org/package/tagsoup-parsec) which looks very cool. When I attempt to install it, I get this error: # cabal install tagsoup-parsec Resolving dependencies... Configuring tagsoup-parsec-0.0.6... Preprocessing library tagsoup-parsec-0.0.6... Building tagsoup-parsec-0.0.6... [1 of 1] Compiling Text.HTML.TagSoup.Parsec ( Text/HTML/TagSoup/Parsec.hs, dist/build/Text/HTML/TagSoup/Parsec.o ) Text/HTML/TagSoup/Parsec.hs:37:5: `Tag' is not applied to enough type arguments Expected kind `*', but `Tag' has kind `* -> *' In the type synonym declaration for `WholeTag' cabal: Error: some packages failed to install: tagsoup-parsec-0.0.6 failed during the building phase. The exception was: exit: ExitFailure 1 It would seem to be a type mismatch between TagSoup.Parsec and the base TagSoup (on which it depends). Suspecting that the version-number dependency information might be incorrect, I tried uninstalling TagSoup and reinstalling an older version. This didn't help. Can anyone steer me in the right direction? Thanks! -Mark

2 3

hunit question
by Joe Van Dyk 02 Feb '10

02 Feb '10

I have a little binary search function and am trying to write tests for it in hunit. The below approach doesn't compile, because I'm attempting to build a list of tuples of different types, which isn't working for me. What's the appropriate way to do this test? http://gist.github.com/293031 import Test.HUnit import JoeBinarySearch -- Note: -- JoeBinarySearch.binary_search :: (Ord a) => [a] -> a -> Maybe Int assertions = [ ([1], 1, (Just 0)), ([1, 3], 1, (Just 0)), ([1, 3, 4], 4, (Just 2)), ([1,2,4,6,8,9,12,15,17,20], 17, (Just 8)), ([1,2,4,6,8,9,12,15,17,20], 20, (Just 9)), ("hello", 'l', (Just 2)), -- BOOM ([0.0, 1.5, 3.0], 3.0, (Just 2)), ([], 1, Nothing), ([1,3], 2, Nothing), ([1,4,6,8,9,12,15,17,20], 2, Nothing), ([1,4,6,8,9,12,15,17,20], 100, Nothing), ([1,4,6,8,9,12,15,17,20], (-100), Nothing)] test_list = TestList test_cases where test_cases = map test_func assertions test_func (lst, input, expected) = TestCase $ assert_equal' ( binary_search lst input ) expected assert_equal' = assertEqual "should equal" main :: IO () main = do runTestTT test_list print "DONE" -- Joe Van Dyk http://fixieconsulting.com

2 5

Using Debug.Trace
by legajid 02 Feb '10

02 Feb '10

Hi, Starting with trace, i have trouble with my calcul'' function while calcul' is ok. When afftrace in calcul'' is commented, the program compiles. When uncommented ( afftrace (" calcul'' vide") ), i get the following messages : ------------------------------------------------------------------------------------------- *Main> :r [1 of 1] Compiling Main ( sud3c.hs, interpreted ) sud3c.hs:62:3: Couldn't match expected type `[Char]' against inferred type `(Plateau, Char)' In a stmt of a 'do' expression: afftrace (" calcul'' vide") In the expression: do afftrace (" calcul'' vide") (pxv, False) In the definition of `calcul''': calcul'' pxv _ [] = do afftrace (" calcul'' vide") (pxv, False) Failed, modules loaded: none. ------------------------------------------------------------------------------------------- I don't understand why, in calcul', it's ok and why, in calcul'', it's problematic. Because return value of calcul'' is a tuple ? When my program is ok, should i remove all trace instructions (and associated do commands too) or just set my modetrace value to False ? Thanks for helping, Didier Below my code : calcul' :: Plateau -> [Cellule] -> Plateau calcul' pxv [] = do afftrace (" Calcul' vide") pxv calcul' pxv (c:cs)= do afftrace (" Calcul' ok1="++show ok1++" c:cs= "++show (c:cs)) afftrace (" "++show xv1) if ok1 then do afftrace (" Calcul' suite") calcul' xv1 cs else do afftrace (" Calcul' pas de valeur") pxv where vallib=[1..length pxv]++[5..7] nbvlib=length vallib (xv1,ok1)=calcul'' pxv c vallib calcul'' :: Plateau -> Cellule -> [Valeur] -> (Plateau, Bool) calcul'' pxv _ [] = do --afftrace (" calcul'' vide") (pxv, False) calcul'' pxv c (li : lis) = do --afftrace (" "++show pxv) --afftrace (" "++show c ++ " "++show(li:lis)) v2 where v2= if (elem li pxv || li==4) then calcul'' pxv c lis else do --afftrace (" calcul'''") (calcul''' pxv c li, True) calcul''' :: Plateau -> Cellule -> Valeur -> Plateau calcul''' pxv c li = take (c-1) pxv ++ [li] ++ drop c pxv afftrace x= if modetrace then trace x " " else " "

2 2

Performance of Idiomatic lazy Haskell
by Markus Böhm 02 Feb '10

02 Feb '10

As a beginner fascinated about Haskell's lazy, idiomatic style I tried a small example: Calculate a numerical approximation of PI based on the Leibniz formula. Variant 1: My lazy, idiomatic approach (as I understand it so far). It takes on my machine with eps = 0.00000001 approx. 25 sec. import Data.List main :: IO () main = do putStrLn "EPS: " eps <- readLn :: IO Double let pi14 = calcpi14 eps putStrLn $ "PI mit EPS "++(show eps)++" = "++ show(4*pi14) calcpi14:: Double->Double calcpi14 eps = foldl' (+) 0 $ takeWhile (\x -> 4 * abs x > eps) ev where e = map (\x->1.0/x) [1.0,3.0..] ev = zipWith (*) e $ cycle [1.0,-1.0] Variant 2: My "C-style" approach achieving state via additonal function parameters. It takes on my machine with eps = 0.00000001 approx. 5 sec. import Data.List main :: IO () main = do putStrLn "EPS: " eps <- readLn :: IO Double let pi14 = pisum 1 3 False eps putStrLn $ "PI mit EPS "++(show eps)++" = "++ show(4*pi14) pisum s i _ eps | 4/i < eps = s pisum s i True eps = let h = s + 1/i in h `seq` pisum h (i+2) False eps pisum s i False eps = let h = s - 1/i in h `seq` pisum h (i+2) True eps I'd like to do idiomatic, lazy Haskell w/o such a performance penalty? How can I learn/achive that? -- Markus

6 23