- Beginners - Haskell.org

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

Re: foldl' vs seq
by Gabi 02 Feb '10

02 Feb '10

Thank you Ertugrul, I think I got it now. My lesson here is to avoid recursion as much possible and use foldr' instead.There are too many pitfalls. -- Regards, Gabi http://bugspy.net

2 1

foldl' vs seq
by Gabi 02 Feb '10

02 Feb '10

Hi Stephen, Thanks for the answer. Now I got confused :) 1. What is seq used for if it doesn't force strictness ? 2. Why the accumulator is important ? In other words why the following is much slower ? Isn't it RT too ? slowSum :: [Integer] -> Integer slowSum[] = 0 slowSum (x:xs) = x `seq` x + slowSum xs

3 3

Re: [Haskell-beginners] one more step backwards
by Felipe Lessa 01 Feb '10

01 Feb '10

On Mon, Feb 01, 2010 at 10:32:00PM +0000, John Moore wrote: > Hi Felipe, > this is way complicated for my level, could you look at this > below and see if I could use this instead. I understand you, it also took me some time to understand the monad transformer library :). > evalStep :: Expression -> Expression > evalStep (Val x)= (Val x) > evalStep (Add x y) > = case x of > (Val a) -> case y of > (Val b) -> Val (a+b) > left -> Add x (evalStep y) > right -> Add (evalStep x)y Even without the Writer monad you capture that pattern in an auxiliary function. You just extract the common bits and abstract the specific ones: aux calcOp mkOp x y = case x of (Val a) -> case y of (Val b) -> Val (a `calcOp` b) left -> mkOp x (evalStep y) right -> mkOp (evalStep x) y Note that: - I've changed (+) into calcOp and Add into mkOp. - Instead of deconstructing with a pattern match, I receive x and y as proper arguments. The type is type CalcOp = Integer -> Integer -> Integer type MkOp = Expression -> Expression -> Expression aux :: CalcOp -> MkOp -> Expression -> Expression -> (Expression -> Expression) You can write your evalStep as evalStep :: Expression -> Expression evalStep (Val x) = Val x evalStep (Add x y) = aux (+) Add x y evalStep (Subtract x y) = aux (-) Subtract x y evalStep (Multiply x y) = aux (*) Multiply x y evalStep (Divide x y) = aux div Divide x y Much cleaner ;). > What I mean to do is build up a history on a list and then take it of a > list( Same principle as a stack but a little more simple) the problem is how > do I get the other elements back of the list as in the line "r" -> evaluate > (I'm not sure what I put here) Hopes this makes some sort of sense. It does makes sense. In most languages this is the sort of code you would write: when the user tell us to evaluate, we evaluate and then save the result. However in our language we can leverage the laziness: buildHistory :: Expression -> [Expression] buildHistory expr = expr : buildHistory (evalStep) You may recognize this function as buildHistory = iterate evalStep (Note that unless your expression is infinite, then this list will contain an infinite number of duplicates when we reach the fixed point of the evalStep function.) The idea is to take everything you can out of IO. With buildHistory we take the logic of evaluating the expressions further out of IO. Now your function is as trivial as mine. In fact, it is the same. HTH, -- Felipe.

1 0