April 2008 - Haskell-Cafe

Re: [Haskell-cafe] Memory allocation in extractor function (newbie question)
by Alexander Kireyev 07 Apr '08

07 Apr '08

On Mon, Apr 7, 2008 at 4:16 PM, Yitzchak Gale <gale(a)sefer.org> wrote: > You didn't show us the code for countForPoints. I'll bet you wrote > something like > > countForPoints area ls count points = > sum $ map (countPathsFrom area (count + 1) ls) points > > Unfortunately, the standard sum function is too lazy in many situations. > And if you wrote out the recursion for countForPoints by hand, you > may have run into the same problem. In either case, you'll be accumulating > huge amounts of unevaluated (+) thunks instead of adding up the > count as you go along. > > If this is the problem, you can fix it by using foldl', a strict version > of foldl from Data.List, instead of sum: > > countForPoints area ls count points = > foldl' (+) 0 $ map (countPathsFrom area (count + 1) ls) points Thanks for the pointer. In fact my version was already using the fold function, albeit the lazy version of it: countForPoints :: Area -> String -> Int -> [Point] -> Int countForPoints area goal count points = let newCount = foldl (countSubPaths area goal) count points in if countExceeded newCount then -1 else newCount countExceeded :: Int -> Bool countExceeded count = (count < 0) || (count > countLimit) countSubPaths :: Area -> String -> Int -> Point -> Int countSubPaths area goal count point = if (countExceeded count) then -1 else countPathsFrom area count goal point Switching to the strict version reduced the amount of garbage in that function and in countSubPaths, but the problem with 'letterAt' still shines. I was thinking that adding strictness to that function might help, but no amount of exclamation marks helped it so far. -Alexander // copying to the mailing list, because first reply didn't get through.

1 0

Re: [Haskell-cafe] The range operator
by PR Stanley 07 Apr '08

07 Apr '08

At 12:28 07/04/2008, you wrote: >On Fri, Apr 4, 2008 at 10:49 PM, Andrew Coppin ><andrewcoppin(a)btinternet.com> wrote: > > More to the point, the range y..z goes in steps of y-z. ;-) >[x,y..z] goes in steps of y-x ;-), [y..z] goes in steps of 1 >(depending on the type). Could you elaborate please? >_______________________________________________ >Haskell-Cafe mailing list >Haskell-Cafe(a)haskell.org >http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Memory allocation in extractor function (newbie question)
by Alexander Kireyev 07 Apr '08

07 Apr '08

Hello, While trying to write a program for the countPaths Code Jam problem I ran into what seems to me as a weird behaviour in terms of memory allocation. The task is to count the number of way you can spell a certain "word" by walking some path on a board of letters. Being a newbie I started with a very straightforward recursive approach, which is not effective, but still helps to improve understanding of Haskell basics. Quite naturally I quickly hit the point where the program becomes too slow, so I tried to profile and optimize the code. I used 3 data types: data GridEntry = GridEntry {letter :: Char, neighbors :: [Point]} data Area = Area {letters :: (Array (Int, Int) GridEntry), width :: Int, height :: Int} data Point = Point { x :: Int, y :: Int} deriving (Show, Eq) With the recursive approach I had to retrieve GridEntries (a letter in a certain point of grid together with the list of its neighbours on the grid) a lot. Quite surprisingly I saw that this operation was overly expensive in my program. The most time was spent in these 2 functions: countPathsFrom :: Area -> Int -> String -> Point -> Int countPathsFrom _ count [] _ = count countPathsFrom area count (l:[]) point = count + if (letter (letterAt area point) == l) then 1 else 0 countPathsFrom area count (l:ls) point = let gridPt = letterAt area point points = neighbors gridPt in if (letter gridPt == l) then countForPoints area ls count points else count letterAt :: Area -> Point -> GridEntry letterAt area (Point x y) = letters area ! (x, y) The profiling log (./paths +RTS -P) shows the following time/space behaviour for them: countPathsFrom Main 181 11830476 37.8 52.3 59.5 82.2 28 1325013312 letterAt Main 184 11830476 21.6 29.9 21.6 29.9 16 757150464 What puzzles me here is how the function letterAt generates 64 bytes of garbage per call. Since there are no side-effects in this section of program - and noone can damage the 'area' structure - I would expect the compiler/runtime to use a reference to the data in the 'area' structure when returning values from letterAt. Instead it seems to make a copy of GridEntry and return that. The question here is whether (why?) this behaviour is normal and if it is possible to optimize the code in such cases. Thanks in advance, -Alexander

2 1

The range operator
by PR Stanley 07 Apr '08

07 Apr '08

Hi folks [x, y..z] What's the role of x? Cheers, Paul

5 4

REMINDER: Next Hackathon (Hac4) starts in 4 days
by Thomas Schilling 06 Apr '08

06 Apr '08

Hi Haskell Hackers! There are only 4 days left until the fourth Hackathon (http:// www.haskell.org/haskellwiki/Hac4) at Chalmers University in Gothenburg, Sweden. If you haven't registered, yet, please do so now! Registration deadline: Tuesday, April 8, 2008 To register, go to http://www.haskell.org/haskellwiki/Hac4/Register and follow the steps. For all those already registered, here's a short (not nearly complete) checklist: * Make sure you have an account on code.haskell.org. (See http:// www.haskell.org/haskellwiki/Hac4/Projects for how to do that.) * Decide what to work on if you haven't yet. (See http:// www.haskell.org/haskellwiki/Hac4/Projects for ideas.) * Make sure your laptop is working and that you take all required extra equipment. (If your wireless driver sucks, we can probably find some cables and a switch here.) * It would be good to have all the code you want to work on already on your computer. Also make sure it builds with your compiler version. If your distro doesn't have binaries, maybe install some software in advance, like Gobby or profiled versions of GHC, newest version of gtk2hs or whatever seems appropriate. It would just be a shame to waste hours of precious hacking time. * Make a backup. Just in case. ;) * Many hostels want a confirmation a few days before arrival, don't forget. * If you need some phone numbers of locals, check the wiki site, if you need some more help from us locals, you can ask us at our IRC channel #haskell-hac4. We're looking forward to a fun weekend! / The Hac4 Team

1 0

Re: [Haskell-cafe] ANN: Hayoo! beta 0.1
by Timo B. Hübel 06 Apr '08

06 Apr '08

On Sunday 06 April 2008 20:31:09 you wrote: > Overall feedback: Cool! So far, I like Hayoo!, and I'm therefore > interested in Holumbus. Is there some technical overview available? Currently, only what you can find on http://holumbus.fh-wedel.de but we will try to extend the site in the near future. > transcript of my short test of hayoo, including nitty-picky feedback: > [...] Thanks for this extensive feedback, some of these are known issues we're already working on which will be fixed soon. The others are on my TODO list now :) Regards, Timo

1 0

Role based access control via monads or arrows or... something
by porrifolius 06 Apr '08

06 Apr '08

Hello. I've been playing around trying to write a framework to support/enforce access control to resources. So far my efforts have yielded little but bruised forehead and compressed plaster-board. What I'd like is a solution that: (1) prevents access to resources except via a fine-grained permissions checking gateway (2) supports on-the-fly permissions eg Bob can see Fred's salary (3) supports dynamic role constraints eg Bob can't be both appointor and appointee of secret agent status (4) allows lack of permission to optionally act as a filter rather than cause an abort, eg Bob viewing all salaries returns Fred's but doesn't return Tom's rather than aborting altogether because Bob lacks the permission over Tom (5) well defined behaviour when checking permissions for actions that change permissions (6) it must be pure, no need for IO. (7) ideally required permissions would appear (and accumulate) in type signatures via inference so application code knows which are required and type checker can reject static/dynamic role constraint violations I've attempted a solution using arrows based loosely upon ideas in [1] and [2]. I can't figure out how to make it work, even if I did get it working I now suspect it can be done far more simply, and I don't think it could ever provide feature (7). For what it's worth it's attached. Ideally you kind folk could help me come up with a type-level solution to satisfy (7), so you could have something like: deptAveSal :: (HasPerms subject? Read Salary [person]?, HasPerm subject? Read Employees dept?, HasRole subject? Manager dept?) => Department -> Salary Failing that how to do it in a more simple fashion? I now think that a State-like monad exposing only functions taking values in a wrapper type that carries required permissions may be sufficient, but still probably couldn't satisfy (7). Failing that my existing attempt has me stumped for a few reasons: how do I get hold of the subject and resource so I can build the correct permission in Test? eg the Person whose Salary is needed in salary, and who's trying to get it where do I get the System from in Test? eg fakeSystem in personByName how to implement the filter functionality in RBAC? Parametric over container types? I think that perhaps the Validator would need to be a monad that holds the initial state of the System to provide a stable set of permissions/roles and that the subject and System should also be threaded through the arrows for use/modification. Any help you can offer for my aching cranium will be _much_ appreciated. Thanks. [1] Encoding Information Flow in Haskell - Peng Li, Steve Zdancewic. http://www.seas.upenn.edu/~lipeng/homepage/flowarrow.html [2] A Library for Secure Multi-threaded Information Flow in Haskell - Alejandro Russo, Tsa-chung Tsai, John Hughes. http://www.cs.chalmers.se/~russo/publications.html

6 7

Beginners arrow question
by Paul Johnson 05 Apr '08

05 Apr '08

I'm using arrows for the first time, with HXT. I think I'm getting the hang of it, but one problem has me stumped. I have a function "lookupFormatter" which takes a string and returns an arrow, and I want to use that arrow. Something like this: myProblem :: (ArrowXml a) -> a XmlTree String myProblem = proc xml do name <- getAttrValue "name" -< xml fmt <- arr lookupFormatter -< name fmt -< xml But I can't figure out how to do it. I get "fmt: not in scope". Can anyone help? Thanks, Paul.

5 4

Problems installing OpenAL / compiling an OpenAL program
by Henk-Jan van Tuyl 05 Apr '08

05 Apr '08

L.S., I downloaded OpenAL from Hackage and tried to compile a program that uses it (on a Windows XP computer). I got a long list of messages in the linking phase; I found a related ticket, http://hackage.haskell.org/trac/ghc/ticket/1140 with a patch. I applied the patch manually and removed the package and installed it again. The problem remained. The output from the compiler run: ghc -Wall --make TestOpenAL.hs -i"C:\Programs\Haskell\Libs" -dcore-lint -o TestO penAL.exe [1 of 1] Compiling Main ( TestOpenAL.hs, TestOpenAL.o ) TestOpenAL.hs:57:8: Warning: This binding for `s' shadows an existing binding In a pattern binding in a 'do' expression Linking TestOpenAL.exe ... C:\Program Files\Haskell\OpenAL-1.3.1.1\ghc-6.8.2/libHSOpenAL-1.3.1.1.a(Buffer.o )(.text+0x1de):fake: undefined reference to `alGetBufferi@12' C:\Program Files\Haskell\OpenAL-1.3.1.1\ghc-6.8.2/libHSOpenAL-1.3.1.1.a(Buffer.o )(.text+0x5f7):fake: undefined reference to `alBufferData@20' C:\Program Files\Haskell\OpenAL-1.3.1.1\ghc-6.8.2/libHSOpenAL-1.3.1.1.a(Buffer.o )(.text+0xa4e):fake: undefined reference to `alGetBufferi@12' C:\Program Files\Haskell\OpenAL-1.3.1.1\ghc-6.8.2/libHSOpenAL-1.3.1.1.a(Source.o )(.text+0x1b9):fake: undefined reference to `alSourcei@12' C:\Program Files\Haskell\OpenAL-1.3.1.1\ghc-6.8.2/libHSOpenAL-1.3.1.1.a(Source.o )(.text+0x30d):fake: undefined reference to `alIsSource@4' Etcetera. Then I downloaded OpenAL with the command: darcs get http://darcs.haskell.org/packages/OpenAL/ Trying to install this gives: Libs\OpenAL>runhaskell Setup.hs configure Configuring OpenAL-1.3.1.1... Libs\OpenAL>runhaskell Setup.hs build Preprocessing library OpenAL-1.3.1.1... Building OpenAL-1.3.1.1... Sound/OpenAL/Config.hs:40:0: HsOpenALConfig.h: No such file or directory My questions are: 1) How do I get a proper package installed? 2) How do I find tickets for a certain package? 3) Is there an automatic way of applying patches from the tickets? 4) Is the darcs repository version incomplete? -- Met vriendelijke groet, Henk-Jan van Tuyl -- http://functor.bamikanarie.com http://Van.Tuyl.eu/ --

1 0

lhs2TeX --> html?
by Conal Elliott 05 Apr '08

05 Apr '08

Has anyone fiddled with hooking up lhs2TeX a tex->html tool like jsMath, for lovely code in a web page? - Conal

1 0