- Beginners - Haskell.org

Regarding Haskell GSOC projects
by Gautam Sewani 15 Mar '09

15 Mar '09

Hi, I am interested in working on Haskell during GSOC 2009. I wanted to know which Haskell mailing list to use in order to inquire about the various project ideas. Regards Gautam

2 1

Integer factorization
by Sergey V. Mikhanov 15 Mar '09

15 Mar '09

Hello, I am solving a problem of finding the largest prime factor of 600851475143 (Project Euler is great for learning new language!), and came with the following solution (it uses the most ineffective approach to finding prime numbers, however is able to factor the above number in fraction of second): factors :: Integer -> [Integer] factors n = doFactors n (eratosthenesFilter [1..n]) doFactors n primes | null newPrimes = [] | otherwise = let topPrime = head newPrimes in if topPrime == n then [topPrime] else topPrime : (doFactors (n `quot` topPrime) primes) where newPrimes = snd $ break (\x -> (n `rem` x) == 0) primes eratosthenesFilter :: [Integer] -> [Integer] eratosthenesFilter [] = [] eratosthenesFilter (num : nums) | num == 1 = eratosthenesFilter nums | otherwise = num : (eratosthenesFilter $ doFilter num nums) where doFilter num nums = filter (\x -> x > num && (x `rem` num) /= 0) nums What would you do different (including stylistic changes)? What are the general comments about efficiency (not of the algorithm, but of the implementation: for example, is it fine to use break at every invocation of doFactors?) and elegance of the solution? Thanks and regards, Sergey

7 12

Longest common subsequence
by Leslie P. Polzer 13 Mar '09

13 Mar '09

Hi, after the factorial function I tried to write my second Haskell program, tackling the longest common subsequence algorithm: lcsList :: [a] -> [a] -> [a] lcsList [] _ = [] lcsList _ [] = [] lcsList (x:xs) (y:ys) = if x == y then lcsList xs ys else let lcs1 = lcsList x:xs ys lcs2 = lcsList xs y:ys in if (length lcs1) > (length lcs2) then lcs1 else lcs2 main = do putStrLn("Result: " show lcsList [1,2,3] [1,3]) GHC has several problems with it: lcs.hs:4:27: Could not deduce (Eq a) from the context () arising from a use of `==' at lcs.hs:4:27-32 Possible fix: add (Eq a) to the context of the type signature for `lcsList' I understand that I need to specify that type 'a' needs to be a derived type of something that can be compared, but how do I specify this in the code? On a related note, how can I make the function more flexible, to discern between case-sensitive and case-insensitive string comparison, for example? In Lisp I would just write this lambda list: (defun lcs-list (list1 list2 &key (test #'eql)) ...) and it would allow me to specify the test but use some sensible default if I don't. And two other errors which I don't quite get: lcs.hs:7:50: Couldn't match expected type `[a] -> [[a1] -> [a1]]' against inferred type `[a]' In the second argument of `(:)', namely `xs ys' In the expression: lcsList x : xs ys In the definition of `lcs1': lcs1 = lcsList x : xs ys lcs.hs:8:33: Occurs check: cannot construct the infinite type: a = [a] When generalising the type(s) for `lcs2' In the expression: let lcs1 = lcsList x : xs ys lcs2 = lcsList xs y : ys in if (length lcs1) > (length lcs2) then lcs1 else lcs2 in if (length lcs1) > (length lcs2) then lcs1 else lcs2 Can you help me with that? Thanks, Leslie -- LinkedIn Profile: http://www.linkedin.com/in/polzer Xing Profile: https://www.xing.com/profile/LeslieP_Polzer Blog: http://blog.viridian-project.de/

2 1

Re: [Haskell-beginners] Longest common subsequence
by Daniel Seidel 13 Mar '09

13 Mar '09

Leslie P. Polzer wrote: > Hi, > > after the factorial function I tried to write my second Haskell > program, tackling the longest common subsequence algorithm: > > lcsList :: [a] -> [a] -> [a] > lcsList [] _ = [] > lcsList _ [] = [] > lcsList (x:xs) (y:ys) = if x == y > then lcsList xs ys > else > let lcs1 = lcsList x:xs ys > lcs2 = lcsList xs y:ys > in if (length lcs1) > (length lcs2) > then lcs1 > else lcs2 > > main = do > putStrLn("Result: " show lcsList [1,2,3] [1,3]) > > GHC has several problems with it: > > lcs.hs:4:27: > Could not deduce (Eq a) from the context () > arising from a use of `==' at lcs.hs:4:27-32 > Possible fix: > add (Eq a) to the context of the type signature for `lcsList' > > I understand that I need to specify that type 'a' needs to > be a derived type of something that can be compared, but > how do I specify this in the code? > > On a related note, how can I make the function more flexible, > to discern between case-sensitive and case-insensitive string > comparison, for example? > > In Lisp I would just write this lambda list: > > (defun lcs-list (list1 list2 &key (test #'eql)) > ...) > > and it would allow me to specify the test but use some sensible > default if I don't. > > > And two other errors which I don't quite get: > > lcs.hs:7:50: > Couldn't match expected type `[a] -> [[a1] -> [a1]]' > against inferred type `[a]' > In the second argument of `(:)', namely `xs ys' > In the expression: lcsList x : xs ys > In the definition of `lcs1': lcs1 = lcsList x : xs ys > > lcs.hs:8:33: > Occurs check: cannot construct the infinite type: a = [a] > When generalising the type(s) for `lcs2' > In the expression: > let > lcs1 = lcsList x : xs ys > lcs2 = lcsList xs y : ys > in if (length lcs1) > (length lcs2) then lcs1 else lcs2 > > in if (length lcs1) > (length lcs2) then lcs1 else lcs2 > > Can you help me with that? > > Thanks, > > Leslie > > Hi, there are some mistakes inside. a compiling version (not sure, if it does what you expect) is lcsList :: Eq a => [a] -> [a] -> [a] lcsList [] _ = [] lcsList _ [] = [] lcsList (x:xs) (y:ys) = if x == y then x : lcsList xs ys else let lcs1 = lcsList (x:xs) ys lcs2 = lcsList xs (y:ys) in if (length lcs1) > (length lcs2) then lcs1 else lcs2 main = do putStrLn("Result: " ++ show (lcsList [1,2,3] [1,3])) There were some common mistakes in your version: 1. type signature needs the type class Eq a, to ensure that you can compare the elements (function (==) is present) 2. function application binds stronger than cons (:), therefore lcsList x:xs ys means (lcsList x): (xs ys) NOT lcsList (x:xs) ys 3. in the main function concatination of strings (++) and braces around the argument of show where missing, which leds to parsing: "Result" as a function with show, lcsList, [1,2,3] and [1,3] as arguments. Greetings, Daniel.

1 0

maximum: stack overflow?
by Patrick LeBoutillier 13 Mar '09

13 Mar '09

Hi all, Why does finding the maximum element of a big list cause a stack overflow: In ghci, if I print out a big list: *Main> [1..1000000] it takes a while but it prints. However, looking for the maximum element fails: *Main> maximum [1..1000000] *** Exception: stack overflow It seems to me like maximum should just be going through the list one by one and keeping track on the largest element seen do far. Why does in need to keep the entire list around (I presume), causing the stack overflow? Patrick -- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

4 4

strange take result--explanation?
by 7stud 12 Mar '09

12 Mar '09

*Main> let x = [] *Main> take (length x - 1) [1, 2, 3] [] *Main> length x 0 *Main> take (0 - 1) [1, 2, 3] [] *Main> take -1 [1, 2, 3] <interactive>:1:0: No instance for (Num (Int -> [a] -> [a])) arising from a use of `-' at <interactive>:1:0-16 Possible fix: add an instance declaration for (Num (Int -> [a] -> [a])) In the expression: take - 1 [1, 2, 3] In the definition of `it': it = take - 1 [1, 2, 3] <interactive>:1:6: No instance for (Num ([t] -> Int -> [a] -> [a])) arising from the literal `1' at <interactive>:1:6-16 Possible fix: add an instance declaration for (Num ([t] -> Int -> [a] -> [a])) In the second argument of `(-)', namely `1 [1, 2, 3]' In the expression: take - 1 [1, 2, 3] In the definition of `it': it = take - 1 [1, 2, 3] *Main> take - 1 [1, 2, 3] ----- Why does take (0 - 1) [1, 2, 3] produce a result but not take -1 [1, 2, 3] ? Thanks

4 5

Simple data summarization
by Andy Elvey 11 Mar '09

11 Mar '09

Hi all - In the process of learning Haskell I'm wanting to do some simple data summarization. ( Btw, I'm looking at putting any submitted code for this in the "cookbook" section of the Haskell wiki. Imo it would be very useful there as a "next step" up from just reading in a file and printing it out. ) This would involve reading in a delimited file like this - ( just a contrived example of how many books some people own ) - Name,Gender,Age,Ethnicity,Books Mary,F,14,NZ European, 11 Brian,M,13,NZ European, 6 Josh,M,12,NZ European, 14 Regan,M,14,NZ Maori, 9 Helen,F,15,NZ Maori, 17 Anna,F,14,NZ European, 16 Jess,F,14,NZ Maori, 21 .... and doing some operations on it. As you can see, the file has column headings - I prefer to be able to manipulate data with headings (as it is what I do a lot of at work, using another programming language). I've tried to break the problem down into small parts as follows. a) Read the file into a list of pairs. The first element of the pair would be the column heading. The second will be a list containing the data. For example, ("Name", [Mary, Brian, Josh, Regan, ..... ] ) b) Select a numeric variable to summarise ( "Books" in this example) c) Do a fold to summarize the variable. I think a left-fold would be the one to use here, but I may be wrong.... After looking through previous postings on this list, I found some code which is somewhat similar to what I'm after (although the data it was crunching is very different). This is what I've come up with so far - summarize [] = [] summarize ls = let byvariable = head ls numeric_variable = last ls sum = foldl (+) 0 $ numeric_variable in (byvariable, sum) : sum ls main = interact (unlines . map show . summarize . lines) I think this might be a useful start, but I still need to read the data into a list of pairs as mentioned, and I'm unsure as to how to do that. Many thanks in advance for any help received. As mentioned, I'm sure that examples like this could be very useful to other beginners, so I'm keen to make sure that any help given is made maximum use of (by putting any code on the Haskell wiki). - Andy

4 4

folds -- help!
by 7stud 10 Mar '09

10 Mar '09

This is an example that shows how foldl and foldr work (from RWH p.93-94): foldl (+) 0 (1:2:3:[]) == foldl (+) (0 + 1) (2:3:[]) == foldl (+) ((0 + 1) + 2) (3:[]) == foldl (+) (((0 + 1) + 2) + 3) [] == (((0 + 1) + 2) + 3) foldr (+) 0 (1:2:3:[]) == 1 + foldr (+) 0 (2:3:[]) == 1 + (2 + foldr (+) 0 (3:[]) == 1 + (2 + (3 + foldr (+) 0 [])) == 1 + (2 + (3 + 0)) The book says on p.94: ----- The difference between foldl and foldr should be clear from looking at where the parentheses and the empty list elements show up. With foldl, the empty list element is on the left, and all the parentheses group to the left. With foldr, the zero value is on the right, and the parentheses group to the right. ---- Huh? With foldl, the only empty list element I see is on the right. Initially, it looked to me ike they did the same thing, and that the only difference was the way they called step. I think "step" is a horrible, non-descriptive name, so I'm going to use "accFunc" instead: foldl calls: accFunc acc x foldr calls: accFunc x acc So it looks like you can define a function using either one and get the same result. Here is a test: --I am going to use odd for pfunc and [1, 2, 3] for xs: myFilter1 pfunc xs = foldl accFunc [] xs where accFunc acc x | pfunc x = acc ++ [x] | otherwise = acc myFilter2 pfunc xs = foldr accFunc [] xs where accFunc x acc | pfunc x = acc ++ [x] | otherwise = acc *Main> myFilter1 odd [1, 2, 3] [1,3] *Main> myFilter2 odd [1, 2, 3] [3,1] Hmmm. So there is a difference. foldr appears to grab elements from the end of the list. Therefore, to get the same result from the function that uses foldr, I did this: myFilter3 pfunc xs = foldr accFunc [] xs where accFunc x acc | pfunc x = x : acc | otherwise = acc *Main> myFilter3 odd [1, 2, 3] [1,3] But then RWH explains that you would never use foldl in practice because it thunks the result, which for large lists can overwhelm the maximum memory alloted for a thunk. But it appears to me the same thunk problem would occur with foldr. So why is foldr used in practice but not foldl?

7 9

installing cabal with 6.10 - ubuntu
by B 10 Mar '09

10 Mar '09

So I was wanting to try out some code that relies on 6.10, I'm using ubuntu 8.04. Also, I'd like to have cabal installed so I can get and install packages easily. I found some directions online that said that compiling from source might be a good way to go. I downloaded and compiled ghc 6.10.1, installing it locally. The directions I used: ----------- directions ------------ I use 6.8.3 and 6.10.1 on ubuntu without problems. I always build ghc from source. It takes a bit of cpu time, but not much effort on my part. Assuming I've got an older version of GHC in my path, here's all I do: tar -xjf ~/Downloads/ghc-6.10.1-src.tar.bz2 tar -xjf ~/Downloads/ghc-6.10.1-src-extralibs.tar.bz2 cd ghc-6.10.1/ echo "HADDOCK_DOCS = YES" >mk/build.mk ./configure --prefix /usr/local/ghc-6.10.1 make -j sudo make install ------- end of directions -------- Ok so I did this. It works! Then, wanting to keep things simple, I removed ghc 6.8.3 so I'd only have one compiler and libraries around - lessening the chance of wierd conflicts. Done. Now to install cabal-install. Directions I got: - unpack cabal-install-0.6.2.tar.gz somewhere - cd into the resulting directory and run "sh bootstrap.sh" - add "~/.cabal/bin" to you path. Unfortunately, this doesn't work for me. bootstrap.sh requires parsec and network. parsec, in turn, requires mtl. - installed mtl - installed parsec Ok. Now when I go to build network I get this: Could not find module `Data.Generics': it is a member of package base-3.0.3.0, which is hidden According to google, the above message actually indicates that 'syb' is needed, the bug is here: http://hackage.haskell.org/trac/ghc/ticket/2980 - installed syb-0.1.0.0. - still get the same message. At this point I'm stuck! I should say that I'm using this to install all these things: runhaskell Setup configure --user runhaskell Setup build runhaskell Setup install So everything is installed 'locally' and not globally. Thanks for any help with this - I feel like this is harder than it is supposed to be, what am I missing??

2 2

Top beginner mistakes
by 7stud 09 Mar '09

09 Mar '09

Here are my top three: 1) Putting an equals sign after a function name when using guards: myfunction x y = | x < 2 = "a" | y > 20 = "b" | otherwise = "c" dhask.hs:2:4: parse error on input `|' Failed, modules loaded: none. 2) Writing "if" in front of the guard conditions: myfunction x y = | if x < 2 = "a" | if y > 20 = "b" | otherwise = "c" dhask.hs:2:25: parse error on input `=' Failed, modules loaded: none. 3) Not putting parentheses around arguments of the form x:xs dosomething x:xs = head xs dhask.hs:1:0: Parse error in pattern Failed, modules loaded: none. In all three cases, the error messages don't help spot the problem.

5 7