- Haskell-Cafe - Haskell.org

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

Bathroom reading
by Dougal Stanton 18 Aug '07

18 Aug '07

I'm looking for cool but mind-bending examples of functional brilliance. Let us say, hypothetically, you had a bathroom without any reading material. And having read all the Dilbert and Garfield you could seriously stomach, decide you should educate yourself while "on the job". :-) So you decide to print up some "one-liner" style programs into a little booklet. Something between credit-card and postcard sized, with a neat but mind-bending program on it. Don Stewart occasionally swoops in with some fixpoint malarkey to defuse heated discussions. I mean that kind of thing, but with a slightly wider scope than just fibs... Suggestions, please! D.

12 13

Re: [Haskell-cafe] monte carlo trouble
by Chad Scherrer 18 Aug '07

18 Aug '07

I'm using ListT now, trying to do this: type Sample a = ListT (State StdGen) a randomStreamR :: (RandomGen g, Random a) => (a,a) -> g -> ([a], g) randomStreamR bds g =(randomRs bds g1, g2) where (g1,g2) = split g sample :: [a] -> Sample a sample [] = ListT (State f) where f s = case next s of (_,s') -> ([],s') sample xs = do let bds = (1, length xs) xArr = listArray bds xs i <- ListT . State $ randomStreamR bds return $ (xArr ! i) -- Simple example, for testing main = mapM_ print . flip evalState (mkStdGen 1) . runListT $ do x <- sample [1..100] y <- sample [1..x] return (x,y) The abstraction seems much better now, but even the simple little example blows up in memory. Here's a snippet from profiling with -auto-all -caf-all (after I interrupted it): CAF:lvl4 Main 261 1 0.0 0.0 100.0 100.0 main Main 273 0 0.0 0.0 100.0 100.0 sample Main 274 1 100.0 100.0 100.0 100.0 randomStreamR Main 276 1 0.0 0.0 0.0 0.0 I'm wondering if the bind for ListT is still effectively building every possibility behind the scenes, and sampling from that. I could redo the Sample monad by hand, if that could be the problem, but I'm not sure what changes would need to be made. Or maybe it's building lots of different arrays and holding them for too long from the GC. Or maybe it's a strictness/laziness issue I'm missing. Still not so sure when I need case vs let/where. How would you guys going about tracking down the problem? Thanks, Chad On 8/15/07, Paul Johnson <paul(a)cogito.org.uk> wrote: > Chad Scherrer wrote: > > Thanks for your replies. > > > > I actually starting out returning a single element instead. But a > > given lookup might return [], and the only way I could think of to > > handle it in (State StdGen a) would be to fail in the monad. But > > that's not really the effect I want - I'd rather have it ignore that > > element. Another option was to wrap with Maybe, but then since I > > really want a sequence of them anyway, I decided to just wrap in a > > List instead. Is there a way Maybe would work out better? > Ahh. How about using ListT Gen then? That (if I've got it the right > way round) works like the list monad (giving you non-determinism), but > has your random number generator embedded as well. Take a look at "All > About Monads" at http://www.haskell.org/all_about_monads/html/. Each > action in the monad may use a random number and produce zero or more > results. > > Paul. > > >

2 1

defining last using foldr
by Alexteslin 18 Aug '07

18 Aug '07

Hi, I am trying to do the exercise which asks to define built-in functions 'last' and 'init' using 'foldr' function, such as last "Greggery Peccary" = 'y' the type for my function is: myLast :: [Char] -> Char I am not generalizing type so that make it less complicated. But what ever i am trying would not work. The only function type foldr takes as an argument is either (a->a->a) or (a->b->b) and none of the functions i found that would match this type from Char to Char. So in other words should be (Char->Char-Char). I can define the function without foldr but that misses the point of the exercise. Any hint will be appreciated, Thank you -- View this message in context: http://www.nabble.com/defining-last-using-foldr-tf4269357.html#a12151145 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

8 22

What to do about an absent package maintainer?
by Adam Langley 18 Aug '07

18 Aug '07

The HsOpenSSL package[1] is good work, but the author doesn't respond to email(*). I've a bunch of darcs patches to add tests, DSA support and fast Integer <-> BIGNUM functions. Can I use my Hackage account to upload version 0.2 if someone else uploaded 0.1? It is reasonable? I'm guessing that this issue will start to occur more often now that we have Hackage. It's probably good to have some policy. Cheers, (*) It's been > 1 month, with emails from several different addresses. [1] http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsOpenSSL-0.1 -- Adam Langley agl(a)imperialviolet.org http://www.imperialviolet.org

1 0

Re: [Haskell-cafe] Remember the future
by Andrew Coppin 18 Aug '07

18 Aug '07

Gwern Branwen wrote: > On 0, Andrew Coppin <andrewcoppin(a)btinternet.com> scribbled: > >> I've seen comments in various places that monads allow you to "borrow >> things from the future". >> >> That sounds completely absurd to me... can anybody explain? >> > > Take a look at issue 6 of The Monad Reader; search for time travel. <http://www.haskell.org/haskellwiki/The_Monad.Reader> > Mmm... yes... I've read this before. It didn't make any sense then either. (The example is too big and complicated. It obscures the thing it's trying to illustrate...)

1 0

GHC linking problems
by SevenThunders 18 Aug '07

18 Aug '07

I have a large Haskell/C project that needs to be linked against an even larger set of C libraries and object files (OpNet) on a linux box (Fedora Core 7). So far I have been able to link my Haskell libraries to some C test code containing a main function without incident. However the link flags are very complex having been extracted from ghc. (e.g. it requires a host of -u flags and then a bunch of links to external C libraries including a long list of Haskell libraries.) Unfortunately control over the OpNet compilation and linking process is weak at best. Moreover it is not clear how the linking occurs and there is some suspicion that it ultimately creates a dynamic link library which it loads from some external process (the exact calls to gcc are hidden). During the OpNet build we get the following error /usr/lib/ghc-6.6.1/libHSrts.a(Main.o): In function `main': Main.c:(.text+0x22): undefined reference to `__stginit_ZCMain' Main.c:(.text+0x43): undefined reference to `ZCMain_main_closure' collect2: ld returned 1 exit status I do not get this error when statically linking my libraries to a standalone C function containing a main() function. What should I look for? Are there known work arounds to this problem? It's troubling that exporting Haskell to C should be this problematic. Unfortunately I can not use ghc to compile the OpNet code as you might imagine. -- View this message in context: http://www.nabble.com/GHC-linking-problems-tf4270650.html#a12155220 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

4 5

trouble building regex-base 0.91 on ghc 6.7
by Thomas Hartman 18 Aug '07

18 Aug '07

I'm trying to build the latest regex base, which is required for the other regex packages under ghc 6.7 It complains that it can't find Data.Sequence, because it's in a hidden module containers. I added containers to the cabal depends as can be seen in the grep below. And containers isn't hidden when I do ghc-pkg list. What gives? Still getting used to cabal... thomas. hartthoma@linuxpt:~/installs/regex-base-0.91>runghc Setup.hs build Preprocessing library regex-base-0.91... Building regex-base-0.91... Text/Regex/Base/RegexLike.hs:47:17: Could not find module `Data.Sequence': it is a member of package containers-0.1, which is hidden hartthoma@linuxpt:~/installs/regex-base-0.91>grep -i containers regex-base.cabal Build-Depends: base >= 2.0, mtl, containers hartthoma@linuxpt:~/installs/regex-base-0.91>ghc-pkg list /usr/local/lib/ghc-6.7.20070816/package.conf: Cabal-1.1.7, HUnit-1.1.1, QuickCheck-1.0.1, array-0.1, arrows-0.2.1, base-2.1, bytestring-0.1, cgi-3001.1.5, containers-0.1, directory-1.0, fgl-5.4.1, filepath-1.0, (ghc-6.7.20070816), haskell-src-1.0.1, haskell98-1.0, hpc-0.5, html-1.0.1, mtl-1.0.1, network-2.0.1, old-locale-1.0, old-time-1.0, packedstring-0.1, parallel-1.0, parsec-2.0, pretty-1.0, process-1.0, random-1.0, readline-1.0, regex-base-0.72, rts-1.0, stm-2.1, template-haskell-0.1, unix-2.0, xhtml-3000.0.2 --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

2 2

Basic question....
by rodrigo.bonifacio 18 Aug '07

18 Aug '07

Hi all. I want to create the following polymorphic type (EnvItem) that we can apply two functions (envKey and envValue). I tried the following: > type Key = String > data EnvItem a = EnvItem (Key, a) > envKey :: EnvItem (Key, a) -> String > envKey EnvItem (key, value) = key > envValue :: EnvValue(Key, a) -> a > envValue EnvItem (key, value) = value But this is resulting in the error: [Constructor "EnvItem" must have exactly 1 argument in pattern] I think this is a very basic problem, but I don't know what is wrong. Regards, Rodrigo.

4 3

Looking at program execution
by Ian Duncan 17 Aug '07

17 Aug '07

Is there any way to view the steps that a haskell program goes through step by step? I'm thinking something similar to what I've seen in things I've been reading. For example: foldl (+) 0 [1..10] => (0+1) => ((0+1)+2) => (((0+1)+2)+3) => etc. I've seen these sorts of line-by-line execution steps, but I was curious if there was any way to simply type in a function and its arguments and have ghci or hugs or something print out this sort of visual representation of what's going on. Anyone know of something like this?

3 3