- Beginners - Haskell.org

Re: Advice wanted on parallel processing
by Colin Paul Adams 18 Mar '09

18 Mar '09

>>>>> "Daniel" == Daniel Fischer <daniel.is.fischer(a)web.de> writes: Daniel> If e.g. Daniel> data Move = Move {from :: Position, to :: Position} Daniel> , the instance would be Daniel> instance NFData Move where rnf (Move f t) = rnf f `seq` Daniel> rnf t `seq` () Daniel> That might require NFData instances for Position and its Daniel> components, but specifying these should be automatic. <switched to beginners list> Move is somewhat more complicated than that, but it comes down to specifying instances for data Piece_colour = Black | White and data Piece_type = Lance | Reverse_chariot | Side_mover | Vertical_mover | White_horse | Rook ... many more which I'm not sure how to do. I tried added a deriving clause, but the compiler complains: Can't make a derived instance of `NFData Piece_colour' (`NFData' is not a derivable class) In the data type declaration for `Piece_colour' here I don't have and fields to force. -- Colin Adams Preston Lancashire

2 1

Re: [Haskell-beginners] Understanding recursion in Haskell.
by The_Polymorph＠rocketmail.com 18 Mar '09

18 Mar '09

Hi Adrian, Thanks for the explanations. Could we perhaps examine one recursive example in detail, i.e., step-by-step, as I'm still confused? Maybe the following program from chapter 2 of http://book.realworldhaskell.org? myDrop n xs = if n <= 0 || null xs then xs else myDrop (n - 1) (tail xs) Danke, Caitlin --- On Wed, 3/18/09, Adrian Neumann <aneumann(a)inf.fu-berlin.de> wrote: From: Adrian Neumann <aneumann(a)inf.fu-berlin.de> Subject: Re: [Haskell-beginners] Understanding recursion in Haskell. To: beginners(a)haskell.org Date: Wednesday, March 18, 2009, 12:05 AM Am 18.03.2009 um 06:28 schrieb Caitlin: > > Hi. > > As a Haskell beginner, I was wondering if someoneone could explain how the following programs function (pardon the pun)? > This function takes some type which has an ordering defined, i.e. you can compare its elements to one another > maximum' :: (Ord a) => [a] -> a it doesn't work for an empty list > maximum' [] = error "maximum of empty list" the maximum of a one element list is the lone element. this is the base case which will be eventually reached by the recursion > maximum' [x] = x should the list have more than one element > maximum' (x:xs) compare the first element to the maximum of the other elements. if it's greater, it's the maximum > | x > maxTail = x otherwise the maximum of the other elements is the maximum of the whole list > | otherwise = maxTail how to compute the maximum of the other elements? just use this function again. after a while we will only have one element left and reach the base case above. > where maxTail = maximum' xs > > This function takes a number and a list of some type a > take' :: (Num i, Ord i) => i -> [a] -> [a] first, ignore the list and check whether n is <= 0. in this case return an empty list. this is the base case, that's eventually reached by the recursion > take' n _ > | n <= 0 = [] otherwise, check if the list is empty. this is another base case. > take' _ [] = [] if neither n<=0 or the list empty, take the first element, x, and put it on front of the prefix of length (n-1) of the other elements. use take' again, to get that prefix. after a while either n is 0 or there are no more elements in the list and we reach the base case > take' n (x:xs) = x : take' (n-1) xs > > Take two lists > > zip' :: [a] -> [b] -> [(a,b)] if either one of them is empty, stop > zip' _ [] = [] > zip' [] _ = [] otherwise prepend a tuple, build from the two first elements to the zipped list of the other elements. after a while one of the lists should become empty and the base case is reached. > zip' (x:xs) (y:ys) = (x,y):zip' xs ys > > > > quicksort :: (Ord a) => [a] -> [a] empty list -> nothing to do > quicksort [] = [] > quicksort (x:xs) = otherwise take the first element of the list and use it to split the list in two halves. one with all the elements that are smaller or equal than x, the other one with all those that are bigger. now sort them and put x in the middle. that should give us a sorted whole. how to sort them? just use quicksort again! after some splitting the lists will become empty and the recursion stops. > let smallerSorted = quicksort [a | a <- xs, a <= x] > biggerSorted = quicksort [a | a <- xs, a > x] > in smallerSorted ++ [x] ++ biggerSorted -----Inline Attachment Follows----- _______________________________________________ Beginners mailing list Beginners(a)haskell.org http://www.haskell.org/mailman/listinfo/beginners

5 5

Hudak state emulation discussion - can you give me some idea?
by Girish Bhat 18 Mar '09

18 Mar '09

Hi Everyone, I was going through the classic Hudak paper "Conception, Evolution, and Application of Functional Programming". Probably the most valuable part is towards the end where he talks about how state is represented in Haskell. On Page 48 of the PDF (page 406 of the ACM Computing survey volume), he gives the following equations "For expository purposes we would like to make the state as implicit as possible, and thus we express the result as a composition of higher-order functions. To facilitate this and to make the result look as much like the original program as possible, we define the following higher-order infix operators and functions": 1 f:=g =\s -> +fs(gs) 2 f;g =\s -> g(fs)=\s-+fs(gs) 3 f;g =\s -> g(fs) 4 goto f = f 5 f+‘g=\s-+fs+gs 6 f<‘g=\s-+fs<gs 7 if’ p c = \s + (if (p s) then (c s) else s) Unfortunately I am unable to parse/understand what he is doing here. My closure understanding too seems to be wonky. :) Would someone be kind enough to translate each of the above into plain english and explain how to read such eqns in the future? thanks!

3 5

How to display a time difference?
by Colin Paul Adams 18 Mar '09

18 Mar '09

The code of the following routine is intended to indicate how long it takes for the computer to make a move. However the time is printed (as very close to zero) long before the move is made. I must be missing something about sequencing actions in the IO monad. play_move :: IORef Game_state -> IO () play_move game_state_ior = do (_, state, _) <- readIORef game_state_ior putStr "Playing AI: " start_time <- getCurrentTime let move = recommended_move state modifyIORef game_state_ior (update_interactive_from_move move) end_time <- getCurrentTime putStrLn $ show $ (diffUTCTime end_time start_time) -- Colin Adams Preston Lancashire

4 11

Understanding recursion in Haskell.
by Caitlin 18 Mar '09

18 Mar '09

Hi. As a Haskell beginner, I was wondering if someoneone could explain how the following programs function (pardon the pun)? maximum' :: (Ord a) => [a] -> a maximum' [] = error "maximum of empty list" maximum' [x] = x maximum' (x:xs) | x > maxTail = x | otherwise = maxTail where maxTail = maximum' xs take' :: (Num i, Ord i) => i -> [a] -> [a] take' n _ | n <= 0 = [] take' _ [] = [] take' n (x:xs) = x : take' (n-1) xs zip' :: [a] -> [b] -> [(a,b)] zip' _ [] = [] zip' [] _ = [] zip' (x:xs) (y:ys) = (x,y):zip' xs ys quicksort :: (Ord a) => [a] -> [a] quicksort [] = [] quicksort (x:xs) = let smallerSorted = quicksort [a | a <- xs, a <= x] biggerSorted = quicksort [a | a <- xs, a > x] in smallerSorted ++ [x] ++ biggerSorted Thanks, Caitlin

3 2

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