- Beginners - Haskell.org

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

Log_b(a)
by Matthew J. Williams 08 Mar '09

08 Mar '09

Dear friends, What is the Haskell equivlent of log_b(a)? To clarify, log of 36 to the base 1.5. Sincerely Matthew J. Williams

3 2

compiling first program --> warning
by 7stud 08 Mar '09

08 Mar '09

When compiling my first haskell program (the program on p. 71-72 of RWH), which I have in a file called hhask.hs, I got the following warning: $ ghc --make hhask [1 of 1] Compiling Main ( hhask.hs, hhask.o ) Linking hhask ... /usr/bin/ld: warning -F: directory name (/Users/me/Library/Frameworks) does not exist The program works fine, but I'm wondering about that warning. Does that mean I installed haskell in the wrong place? I installed haskell only last week on osx 10.4.11, and here is what I did: 1) I downloaded GMP.framework and GNUreadline.framework, which my mac automatically unzipped and placed on my desktop. I then dragged the resulting two folders into Library/Frameworks as per the instructions at: http://www.haskell.org/ghc/download_ghc_682.html#macosxintel 2) I downloaded ghc-6.8.2 3) I unzipped and untared into: /Users/me/my_tar_extractions 4) I cd'ed into the newly created ghc-6.8.2 folder. The full path to that folder is: /Users/me/my_tar_extractions/ghc-6.8.2 5) I read the INSTALL document in the ghc-6.8.2 folder. 6) I ran the command: $ ./configure 7) Then I rand the command: $ sudo make install 8) At the end of the install output, I got a message that said: ------------- Installation of ghc-6.8.2 was successful. To use, add /usr/local/bin to your PATH. Warning: this binary distribution does NOT contain documentation! -------------- 9) I appended /usr/local/bin onto the PATH in ~/.bash_profile.

1 0

Using The Cabal that comes with GHC 6.10 on Windows
by Glenn 08 Mar '09

08 Mar '09

Hi, I'm sure this should be very simple, but I can't find any obvious documentation in the GHC doco that tells me how to get started with Cabal. I've installed GHC 6.10.1, which comes with Cabal. However, it doesn't seem to come in executable form ? So, I'm not sure what I need to do - build the executable, presumably ? I could download the prebuilt executable version of Cabal, but it seems pointless to include it in GHC, and then go download another one. Sorry for this stupid question ! Could anyone give me a hint on how to proceed ? Thanks ! :)

4 3