March 2009 - Beginners

MD2 Implementation
by Sean Bartell 17 Mar '09

17 Mar '09

I've just recently started learning Haskell, and I wrote an MD2 implementation. This version is correct, but crashes on large files because of the weak evaluation. What I'm wondering is, what's the sort of thought-process I would go through to find the problem areas and fix it? Also, please post any suggestions you have for this code, for style or whatever :). {-# LANGUAGE BangPatterns #-} module MD2 (md2) where import qualified Data.ByteString as B import Data.Bits (xor) import Data.List (foldl', mapAccumL) import Data.Word (Word8) table = B.pack [0x29, 0x2E, 0x43, 0xC9, 0xA2, 0xD8, 0x7C, 0x01, 0x3D, 0x36, 0x54, 0xA1, 0xEC, 0xF0, 0x06, 0x13, 0x62, 0xA7, 0x05, 0xF3, 0xC0, 0xC7, 0x73, 0x8C, 0x98, 0x93, 0x2B, 0xD9, 0xBC, 0x4C, 0x82, 0xCA, 0x1E, 0x9B, 0x57, 0x3C, 0xFD, 0xD4, 0xE0, 0x16, 0x67, 0x42, 0x6F, 0x18, 0x8A, 0x17, 0xE5, 0x12, 0xBE, 0x4E, 0xC4, 0xD6, 0xDA, 0x9E, 0xDE, 0x49, 0xA0, 0xFB, 0xF5, 0x8E, 0xBB, 0x2F, 0xEE, 0x7A, 0xA9, 0x68, 0x79, 0x91, 0x15, 0xB2, 0x07, 0x3F, 0x94, 0xC2, 0x10, 0x89, 0x0B, 0x22, 0x5F, 0x21, 0x80, 0x7F, 0x5D, 0x9A, 0x5A, 0x90, 0x32, 0x27, 0x35, 0x3E, 0xCC, 0xE7, 0xBF, 0xF7, 0x97, 0x03, 0xFF, 0x19, 0x30, 0xB3, 0x48, 0xA5, 0xB5, 0xD1, 0xD7, 0x5E, 0x92, 0x2A, 0xAC, 0x56, 0xAA, 0xC6, 0x4F, 0xB8, 0x38, 0xD2, 0x96, 0xA4, 0x7D, 0xB6, 0x76, 0xFC, 0x6B, 0xE2, 0x9C, 0x74, 0x04, 0xF1, 0x45, 0x9D, 0x70, 0x59, 0x64, 0x71, 0x87, 0x20, 0x86, 0x5B, 0xCF, 0x65, 0xE6, 0x2D, 0xA8, 0x02, 0x1B, 0x60, 0x25, 0xAD, 0xAE, 0xB0, 0xB9, 0xF6, 0x1C, 0x46, 0x61, 0x69, 0x34, 0x40, 0x7E, 0x0F, 0x55, 0x47, 0xA3, 0x23, 0xDD, 0x51, 0xAF, 0x3A, 0xC3, 0x5C, 0xF9, 0xCE, 0xBA, 0xC5, 0xEA, 0x26, 0x2C, 0x53, 0x0D, 0x6E, 0x85, 0x28, 0x84, 0x09, 0xD3, 0xDF, 0xCD, 0xF4, 0x41, 0x81, 0x4D, 0x52, 0x6A, 0xDC, 0x37, 0xC8, 0x6C, 0xC1, 0xAB, 0xFA, 0x24, 0xE1, 0x7B, 0x08, 0x0C, 0xBD, 0xB1, 0x4A, 0x78, 0x88, 0x95, 0x8B, 0xE3, 0x63, 0xE8, 0x6D, 0xE9, 0xCB, 0xD5, 0xFE, 0x3B, 0x00, 0x1D, 0x39, 0xF2, 0xEF, 0xB7, 0x0E, 0x66, 0x58, 0xD0, 0xE4, 0xA6, 0x77, 0x72, 0xF8, 0xEB, 0x75, 0x4B, 0x0A, 0x31, 0x44, 0x50, 0xB4, 0x8F, 0xED, 0x1F, 0x1A, 0xDB, 0x99, 0x8D, 0x33, 0x9F, 0x11, 0x83, 0x14] -- NOTE: There's a problematic typo in RFC 1319 in section 3.2. It says -- Set C[j] to S[c xor L], but it should be Set C[j] to C[j] xor S[c xor L]. type Block = B.ByteString two x = (x, x) applySnd f (x, y) = (x, f y) zeroBlock = B.replicate 16 0 checksumInitial = (0, zeroBlock) foldlBlocks :: (a -> Block -> a) -> a -> B.ByteString -> a foldlBlocks f v x | B.null x = v | otherwise = foldlBlocks f v' rest where (block, rest) = B.splitAt 16 x !v' = f v block checksumBlock :: (Word8, Block) -> Block -> (Word8, Block) checksumBlock (l, cs) bs = applySnd B.pack $ mapAccumL updateL l $ B.zip cs bs where updateL l (c, b) = two $ c `xor` table `B.index` fromIntegral (l `xor` b) doBlock :: Block -> Block -> Block doBlock ds bs = B.take 16 xs' where xs = ds `B.append` bs `B.append` B.pack (B.zipWith xor ds bs) (_, xs') = foldl' doRound (0, xs) [0..17] doRound (t, xs) n = let (t', xs') = B.mapAccumL updateT t xs in (t' + n, xs') updateT t b = two $ b `xor` table `B.index` fromIntegral t doBlockAndCS (csState, blockState) block = (checksumBlock csState block, doBlock blockState block) padding n = B.replicate n (fromIntegral n) md2 :: B.ByteString -> Block md2 bs = let padded = bs `B.append` padding (16 - B.length bs `mod` 16) ((_, cksum), state) = foldlBlocks doBlockAndCS (checksumInitial, zeroBlock) padded in doBlock state cksum

2 1

Binary.Put and Double
by Rick R 15 Mar '09

15 Mar '09

I need to serialize an ieee compliant 64 bit floating point number, most often used as a Double in C. I'm guessing that the value I need to serialize is CDouble, but Put supports putWord64* . How do I convert Double to Word64 while ensuring that it is in the format of CDouble? Is this the right approach? If so, how is this done? -- We can't solve problems by using the same kind of thinking we used when we created them. - A. Einstein -- We can't solve problems by using the same kind of thinking we used when we created them. - A. Einstein

1 0

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