July 2007 - Haskell-Cafe

Converting CTime -> Int
by Rob Hoelz 26 Aug '07

26 Aug '07

Hello everyone, I'm writing an interface to C code, and one of the functions I'm wrapping returns time_t. I see that this maps to CTime in Foreign.C.Types, but I can't figure out how to convert it to an Int (or any other useful Haskell type, for that matter) for the life of me. I've poured over the standard library docs, but to no avail. Could someone give me a hint? Thanks, Rob Hoelz

6 6

Re: Hints for Euler Problem 11
by ronguida＠mindspring.com 18 Aug '07

18 Aug '07

Thank you for all the hints. Here's how I ended up solving it: > module Main > where > > import Data.List > import Data.Maybe > > gridText = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\ > \49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\ > \81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\ > \52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\ > \22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\ > \24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\ > \32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\ > \67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\ > \24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\ > \21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\ > \78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\ > \16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\ > \86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\ > \19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\ > \04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\ > \88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\ > \04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\ > \20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\ > \20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\ > \01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" > type Grid a = [[a]] > readGrid :: (Read a) => String -> Grid a > readGrid = (map ((map read) . words)) . lines > grid :: Grid Integer > grid = readGrid gridText takeExactly - extract the first "n" elements of a list; there must be at least "n" elements, n > 0 > takeExactly :: (Monad m) => Int -> [a] -> m [a] > takeExactly n xs | n > 0 = > let ys = take n xs in > if length ys == n > then return ys > else fail "takeExactly: list is too short" > | otherwise = fail "takeExactly: empty list" > extractGroups :: Int -> [[a]] -> [[a]] > extractGroups n = catMaybes . map (takeExactly n) > gridExtractGroups :: Int -> Grid [a] -> Grid [a] > gridExtractGroups n = filter (not . null) . map (extractGroups n) gridTails - generate a list of grids with sequential starting places Parameters a and b determine the offset bewteen successive grids, as follows: (note that a, b may not be negative) Grid x_{0,1.., 0,1..} -> [ Grid x_{ 0, 1 .., 0, 1 ..} , Grid x_{ a, a+1 .., b, b+1 ..} , Grid x_{2*a, 2*a+1 .., 2*b, 2*b+1 ..} etc. ] > gridTails :: (Int, Int) -> Grid a -> [Grid a] > gridTails (a,b) xs = > if not $ null $ concat xs > then xs : gridTails (a,b) ((drop a) $ map (drop b) xs) > else [] transpose3d - converts x_{i,j,k} to x_{j,k,i} using sequence is x_{i,j,k} -> x_{j,i,k} -> x_{j,k,i} > transpose3d :: [Grid a] -> Grid [a] > transpose3d = map transpose . transpose reorient - transform a direction vector so that both components are non-negative > reorient :: (Int, Int) -> (Grid a -> Grid a, (Int, Int), Grid b -> Grid b) > reorient (a,b) > | a>=0 && b>=0 = (id , ( a, b), id) > | a< 0 && b>=0 = (reverse , (-a, b), reverse) > | a>=0 && b< 0 = (map reverse , ( a,-b), map reverse) > | a< 0 && b< 0 = (reverse . map reverse, (-a,-b), reverse . map reverse) makeEls - convert a grid to grid of Equidistant Letter Sequences > makeEls :: (Int, Int) -> Grid a -> Grid [a] > makeEls vec = let (reflect2, rvec, reflect1) = reorient vec in > reflect2 . transpose3d . gridTails rvec . reflect1 > getGroups :: Int -> (Int, Int) -> Grid a -> [[a]] > getGroups n (a,b) = concat . gridExtractGroups n . makeEls (a,b) > findMaxProduct :: (Ord a, Num a) => Int -> (Int, Int) -> Grid a -> a > findMaxProduct n (a,b) = maximum . map product . getGroups n (a,b) > main :: IO() > main = do > print $ findMaxProduct 4 (1,0) grid > print $ findMaxProduct 4 (0,1) grid > print $ findMaxProduct 4 (1,1) grid > print $ findMaxProduct 4 (1,-1) grid -- Ron

9 18

Hints for Euler Problem 11
by Ronald Guida 17 Aug '07

17 Aug '07

Hi, again. I started looking at the Euler problems [1]. I had no trouble with problems 1 through 10, but I'm stuck on problem 11. I am aware that the solutions are available ([2]), but I would rather not look just yet. In Problem 11, a 20x20 grid of numbers is given, and the problem is to find the largest product of four numbers along a straight line in the grid. The line can be horizontal, vertical, or diagonal. I figured out how to handle the horizontal and vertical products, but I'm stuck on how to approach the problem of extracting the diagonals. Here is what I have so far; it does the horizontal and vertical cases: > module Main > where > > import Data.List > > gridText = "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08\n\ > \49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00\n\ > \81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65\n\ > \52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91\n\ > \22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80\n\ > \24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50\n\ > \32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70\n\ > \67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21\n\ > \24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72\n\ > \21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95\n\ > \78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92\n\ > \16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57\n\ > \86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58\n\ > \19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40\n\ > \04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66\n\ > \88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69\n\ > \04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36\n\ > \20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16\n\ > \20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54\n\ > \01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" > > readGrid :: (Read a) => String -> [[a]] > readGrid = (map ((map read) . words)) . lines > > grid :: [[Integer]] > grid = readGrid gridText > > makeGroups :: Int -> [a] -> [[a]] > makeGroups 0 _ = [] > makeGroups n xs = let ys = take n xs in > if n == length ys > then ys : (makeGroups n $ tail xs) > else [] > > maxHorizontal :: (Ord a, Num a) => Int -> [[a]] -> a > maxHorizontal length = maximum . map product . concat . map (makeGroups length) > > maxVertical :: (Ord a, Num a) => Int -> [[a]] -> a > maxVertical length = maxHorizontal length . transpose > > main :: IO() > main = do > print $ maxHorizontal 4 grid > print $ maxVertical 4 grid To handle the diagonals, my plan is to try to extract each diagonal as a list of elements and put all the diagonals into a list; then I can use maxHorizontal. I came up with this function to try to extract the main diagonal. > getDiag :: [[a]] -> [a] > getDiag = map (head . head) . iterate (tail . map tail) The problem is, this function doesn't work unless I have an infinite grid. Could anyone provide me with some hints to lead me in the right direction? Thank you -- Ron References: [1] http://projecteuler.net/index.php?section=view [2] http://www.haskell.org/haskellwiki/Euler_problems

7 7

Polymorphic variants
by Jon Harrop 10 Aug '07

10 Aug '07

Does Haskell have anything similar to OCaml's polymorphic variants? They act as inferred sum types: # let rec eval = function | `Int n -> n | `Add(f, g) -> eval f + eval g | `Mul(f, g) -> eval f * eval g;; val eval : ([< `Add of 'a * 'a | `Int of int | `Mul of 'a * 'a ] as 'a) -> int = <fun> -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e

4 4

In-place modification
by Andrew Coppin 10 Aug '07

10 Aug '07

I was wittering on about stream fusion and how great it is, and I got a message from Mr C++. (Mr C++ develops commercial games, and is obsessed with performance. For him, the only way to achieve the best performance is to have total control over every minute detail of the implementation. He sees Haskell is a stupid language that can never be fast. It seems he's not alone...) He said two things. The first was "it really perplexes me that Haskell insists that everything must be read-only". Naturally, I have a good answer to that one. (It's like being "perplexed" that relational databases refuse to keep table data in the same order. It's not to be awkward, it is a fundamental and important properly of the underlying theoretical foundation - the relational algebra, et al.) He also said what basically boils down to "being able to swap elements around in O(1) time and O(0) space is the whole thing that makes linked lists useful in the first place; take that away and it's rather pointless". I don't really have an answer to that one. (Lazyness and GC is probably going to kill most of the space cost. There's still a time cost - particularly the extra GC time...) I've asked this before and nobody answered, so I take it that nobody knows the answer... Does GHC *ever* do an in-place update on anything? Does the STG even have a command for that? I always assumed that the compiler tried to find instances where a new structure is created and the old one is no longer referenced, and make that be in-place. But now I'm not so sure...

26 157

Zippers, Random Numbers & Terrain
by Thomas Conway 06 Aug '07

06 Aug '07

Hi All, To amuse myself while waiting for test-runs to complete, I was thinking about random terrain generation. I came across a bunch of nice posts by Torben Mogensen, where he describes a neat way of constructing random terrains by recursively subdividing right angled isosceles triangles. It got me thinking - it's all well and good subdividing to give more detail as you zoom in, but what about when you zoom out? This got me thinking that it would be cool to make an infinite terrain generator using a zipper, so you can zoom in/out infinitely, and by implication, infinitely in any direction. One of the key components that seems to be necessary is a random number generator zipper. In Mogensen's scheme, you have a number associated with each point, and when you subdivide, you create a new RNG seed from the numbers at each end of the hypotenuse which you are bisecting. These numbers are used to generate height variation. The trick, is to make the combination order independent (e.g. xor). This is easy for zooming in, but it's not clear how to do this for zooming out. It's probably sufficient to assume a (parameterizable) hashing/mixing scheme, and to simply number the nodes in some deterministic fashion. The subdivision is binary, so we could number the children deterministically. If we use "decimals", from some arbitrary starting point, we can extend in the "fractional" direction when we zoom in, and extend in the "whole number" direction. I'm only just discovering zippers, so my question to the learned members of this forum is: Am I on the right track? Is a scheme like this going to work? cheers, Tom -- Dr Thomas Conway drtomc(a)gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.

6 8

Knuth Morris Pratt for Lazy Bytestrings implementation
by Justin Bailey 05 Aug '07

05 Aug '07

I've implemented KMP string searching for lazy bytestrings, and I'd like some help improving the performance of the code. I'd also like to know if it doesn't look correct - I've tested it pretty extensively but you never know ... I've been testing on a 7 MB file, where the search sequence is not found. Using strict byestrings, lazy bytestrings, and regular strings, I've found my algorithm is about twice as slow as the strict version. Surprisingly, the strict version is a little bit *slower* than the regular strings version. Thanks for any comments or help! Justin

7 14

how to see operators precedence in GHCi
by Bulat Ziganshin 02 Aug '07

02 Aug '07

Hello , from http://community.livejournal.com/ru_declarative/54566.html Q: how to see operators precedence in GHCi? A: Prelude> let showParen = (undefined::[[[[()]]]]->()) Prelude> showParen $ 2+3*4 <interactive>:1:12: No instance for (Num [[[[()]]]]) arising from use of `+' at <interactive>:1:12 Probable fix: add an instance declaration for (Num [[[[()]]]]) In the second argument of `($)', namely `2 + (3 * 4)' In the definition of `it': it = showParen $ (2 + (3 * 4)) Prelude> -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

4 7

Exiting GLUT application
by Dave Tapley 02 Aug '07

02 Aug '07

Hi everyone, I have the following skeleton GLUT code: > import Graphics.UI.GLUT > main = do > getArgsAndInitialize > createWindow "" > mainLoop It loads into both hugs and ghci fine and when 'main' is evaluated an empty window opens as expected. However when closing the window (clicking the window manager's x button) both hugs and ghci exit with the window, as opposed to returning to the the 'Main>' prompt. I suspect I need some callback to exit the GUI cleanly? Cheers, Dave

3 4

Indentation woes
by anon 01 Aug '07

01 Aug '07

Greetings, I wish to be able to indent my code like so: > longFunctionName various and sundry arguments > | guard1 = body1 > | guard2 = body2 > | ... > where declarations That is, with guards and where clauses indented to the same level as the function name. This seems like a perfectly reasonable indentation style to me. It also happens to be the preferred style in Clean, another layout-sensitive functional language. I believe it is not uncommon in ML dialects as well. So why is it that I'm not allowed to use it in Haskell?

16 25