- Haskell-Cafe - Haskell.org

Solving a geometry problem with Haskell
by Rafael Almeida 14 Jan '08

14 Jan '08

Hello, I have been browsing through the problems at projecteuler.net and I found one that seemed interesting. It's the problem 176, I'll state it here: The four rectangular triangles with sides (9,12,15), (12,16,20), (5,12,13) and (12,35,37) all have one of the shorter sides (catheti) equal to 12. It can be shown that no other integer sided rectangular triangle exists with one of the catheti equal to 12. Find the smallest integer that can be the length of a cathetus of exactly 47547 different integer sided rectangular triangles. I thought I've solved it nicely, only to find later on that my solution was too slow (it has been running for almost three days now). While I was creating my solution I used literate haskell, which I think helped me a bunch to think about the problem. I wrote it originally in portuguese -- the portuguese literate version has all the attempts I've made until getting to the final one. For posting it here I've translated the reasoning around the attempt that solved the problem -- although it does it very slow -- into a new .lhs file: http://www.dcc.ufmg.br/~rafaelc/problem176.lhs After some profiling I found out that about 94% of the execution time is spent in the ``isPerfectSquare'' function. So I began researching about better ways to write that functio. Someone pointed to me on #haskell that the C library gmp has such a function. So I went ahead and wrote a C version of the program using gmp: http://www.dcc.ufmg.br/~rafaelc/problem176.c It's not the prettiest C code, as I did it really quickly, simply translating haskell code into C, but I believe it works. That C solution has been running for more than one hour now and no solution has come up yet. So I don't think it's worthed even writing a faster isPerfectSquare in haskell. As I was translating from Portuguese to English I revisited my logic and I can't see any problems with it. I think the problem is only of slowness, really. Does anyone have a better idea for how I should try to solve this problem? I'm all out of ideas. []'s Rafael

11 18

Re: All equations must have the same arity - why?
by Jonathan Cast 14 Jan '08

14 Jan '08

On 13 Jan 2008, at 4:56 PM, jerzy.karczmarczuk(a)info.unicaen.fr wrote: > Jonathan Cast writes: >> On 13 Jan 2008, at 4:15 PM, Achim Schneider wrote: > ... never mind... >> I'm glad you are capable of ever so nobly assigning the purest >> imaginable motives to the designers of Haskell. You are an >> inspiration to us all. jcc > > Jonathan, please... > You see as well as anybody else what is the point of this discussion. > Perhaps it is not as bad as discussing with Cristian Baboi, but still. Very well, I'll be good. jcc (Meant to send this to the list first time...)

1 0

Add "number of downloads" to hackageDB page?
by Hugh Perkins 13 Jan '08

13 Jan '08

I seem to remember a thread about this a while back actually, but... Any chance of adding the number of downloads to the hackageDB page? For those packages that are included in ghc, hugs etc, perhaps add a green tick with "included in ghc", "included in hugs", etc? That way it should be relatively easier to know for newbies which packages are more or less mature/stable. Optional: perhaps include a tick-box/dropdown to only show packages with more than a certain (configurable) number of downloads?

2 1

Possibilities for website construction using Haskell?
by Hugh Perkins 13 Jan '08

13 Jan '08

What are the possibilities for website construction using Haskell?

5 8

hash-cons
by Tony Finch 13 Jan '08

13 Jan '08

I've been thinking about hashlife recently. I've written part of a fairly didactic C implementation <http://dotat.at/prog/misc/hashlife.c> but I there are more interesting things that can be done with it. In particular, the core calc2() function is essentially implementing lazy evaluation, so it ought to be possible to write it even more nicely in Haskell. However it relies crucially on a hash-cons aka intern aka memoized constructor find(). How can one implement this in Haskell? Google doesn't turn up anything very helpful. If I can solve the hash cons problem, then it ought to be fairly straightforward to use Parallel Haskell to speed up the algorithm on multicore machines. Tony. -- f.a.n.finch <dot(a)dotat.at> http://dotat.at/ PORTLAND: SOUTH 7 TO SEVERE GALE 9 VEERING SOUTHWEST 5 TO 7. ROUGH OR VERY ROUGH. RAIN AT FIRST, THEN SQUALLY SHOWERS. MODERATE OR GOOD.

1 0

Patterns overlapped?
by Fernando Rodriguez 13 Jan '08

13 Jan '08

Hi, When I compile this code, ghc complains about some overlapped patterns in function depth. What on Earth is ghc talking about? O:-) data BinTree a = EmptyTree | NodeBT a (BinTree a) (BinTree a) deriving Show emptyBT = EmptyTree depth emptyBT = 0 depth (NodeBT _ left right) = max (1 + depth left) (1 + depth right)

3 6

Access to list
by Fernando Rodriguez 13 Jan '08

13 Jan '08

Hi, If I define the follwoing functions: car (x:_) = x car [] = [] cdr (_:xs) = xs cdr [] = [] and try to apply them to some list, such as car [1,2,3] I get this odd error: <interactive>:1:9: No instance for (Num [a]) arising from the literal `3' at <interactive>:1:9 Possible fix: add an instance declaration for (Num [a]) In the expression: 3 In the first argument of `car', namely `[1, 2, 3]' In the expression: car [1, 2, 3] What am I doing wrong this time? :-P Thanks

5 5

Comments and suggestions on code
by Andre Nathan 13 Jan '08

13 Jan '08

Hello I've just found time to finish writing my first "real world" program, so I thought I'd post it here and ask for insight on general issues such as if there's anything that isn't done "the Haskell way", or if there's something that could be done more efficiently. The code is at the bottom of this message and also at http://hpaste.org/4893. I realize it's a bit long, so if anyone could just skim through it and see if there's anything really ugly or stupid and point it out, it would be of great help :) Just to make it easier to follow the code, its idea is simple: - Build a process tree by reading entries from /proc (represented as a map); - Compare each child of the init process against a whitelist (which comes from a configuration file); - For each child not in the whitelist, send it a KILL signal. The idea here is to run this on webservers and try to catch bad customers who try to run daemons from their accounts, the typical script kiddie stuff. Anyway, there's one specific question I'd like to ask. I'm using "StateT PsTree IO" to keep program state (the process tree). IO is necessary because all information is read from /proc files. Now consider the following function: appendChild :: Pid -> Pid -> StateT PsTree IO Bool appendChild ppid pid = do tree <- get let PsInfo psData children = mapLookup ppid tree put $ Map.insert ppid (PsInfo psData (pid:children)) tree return True It changes the program state by modifying a process tree entry, but it does no I/O at all. The return type is there basically to match the return type of the function which calls it (insertParent), which calls functions that do I/O. Is there anyway to avoid the "IO" in appendChild's signature (other than making it a pure function by passing the process tree as a parameter and returning a modified map)? I would also like to try ways to improve efficiency, maybe trying a hash table instead of a map for the state, and also using bytestrings. I guess I could try making it parallel, since each child of init can be checked independently. Anyway, this is already longer than I thought it would be (I hope I'm not abusing too much :) The code follows. Thanks in advance for any comments or suggestions. Andre module Main where import qualified Data.Map as Map import Directory import Control.Monad.State import Maybe import System.Environment import System.IO import System.Posix.Files import System.Posix.Signals import System.Posix.Unistd import System.Posix.User import Text.Printf import Text.Regex import Text.Regex.Posix type Pid = FilePath type Uid = String type PsData = Map.Map String String type PsChildren = [Pid] type KillFunction = PsTree -> Pid -> IO () data PsInfo = PsInfo PsData PsChildren type PsTree = Map.Map Pid PsInfo type Whitelist = Map.Map FilePath String mapLookup :: (Ord a) => a -> Map.Map a b -> b mapLookup k = fromJust . Map.lookup k -- Process Tree construction parentPid :: PsInfo -> Pid parentPid (PsInfo psData _) = mapLookup "PPid" psData getProcInfo :: String -> PsData -> PsData getProcInfo line psData = do case line =~~ "^([A-Za-z]+):[[:space:]]+(.*)$" of Nothing -> psData Just ([_, key, value]:_) -> Map.insert key value psData getIds :: String -> PsData -> (String, String) getIds id psData = (rId, eId) where (rId:eId:_) = words (mapLookup id psData) processData :: String -> PsData processData procData = addIds psData where psData = foldr getProcInfo Map.empty (lines procData) addIds psData = Map.union psData (idMap psData) idMap psData = Map.fromList [("RUid", rUid), ("EUid", eUid), ("RGid", rGid), ("EGid", eGid)] (rUid, eUid) = getIds "Uid" psData (rGid, eGid) = getIds "Gid" psData readLink :: String -> IO String readLink link = catch (readSymbolicLink link) (\e -> return "?") procInfo :: Pid -> IO PsInfo procInfo pid = do let dir = "/proc/" ++ pid ++ "/" procData <- readFile $ dir ++ "status" exe <- readLink $ dir ++ "exe" cwd <- readLink $ dir ++ "cwd" cmd <- readFile $ dir ++ "cmdline" let cmd' = subRegex (mkRegex "[^a-zA-z[:space:]\\/\\.-]") cmd " " info = processData procData adminInfo = Map.fromList [("Exe", exe), ("Cwd", cwd), ("Cmd", cmd')] return $ PsInfo (Map.union info adminInfo) [] addProc :: Pid -> StateT PsTree IO PsInfo addProc pid = do info <- lift $ procInfo pid modify (Map.insert pid info) return info appendChild :: Pid -> Pid -> StateT PsTree IO Bool appendChild ppid pid = do tree <- get let PsInfo psData children = mapLookup ppid tree put $ Map.insert ppid (PsInfo psData (pid:children)) tree return True insertParent :: Pid -> Pid -> StateT PsTree IO Bool insertParent ppid pid = do tree <- get if Map.member ppid tree then appendChild ppid pid else do built <- insertInTree ppid if built then appendChild ppid pid else return False insertPid :: Pid -> StateT PsTree IO Bool insertPid "1" = do info <- addProc "1" return True insertPid pid = do info <- addProc pid let ppid = parentPid info if ppid == "0" then return False else insertParent ppid pid insertInTree :: Pid -> StateT PsTree IO Bool insertInTree pid = do tree <- get if Map.member pid tree then return True else insertPid pid buildTree :: FilePath -> StateT PsTree IO Bool buildTree entry | entry =~ "^[0-9]+$" = insertInTree entry | otherwise = return False createTree :: IO PsTree createTree = do entries <- getDirectoryContents "/proc" execStateT (mapM_ buildTree entries) Map.empty -- Process Tree pretty-printing treeStr :: PsTree -> PsChildren -> Int -> String -> String treeStr tree children level str = foldr append str children where append pid s = treeStr tree children' (level + 1) newstr where PsInfo _ children' = mapLookup pid tree pad = take (4 * level) [' ', ' ' ..] newstr = s ++ "\n" ++ pad ++ pid printTree :: PsTree -> Pid -> IO () printTree tree pid = putStrLn (treeStr tree children 1 pid) where PsInfo _ children = mapLookup pid tree -- Process killing tryToKill :: PsTree -> KillFunction -> Pid -> Uid -> Uid -> Bool -> IO Bool tryToKill tree killFun pid "0" allowedUid killed = do -- The process may be starting, give it a second chance. sleep 10 -- conservative value. let PsInfo psData _ = mapLookup pid tree if allowedUid /= mapLookup "EUid" psData then killFun tree pid >> return True else return (killed || False) tryToKill tree killFun pid _ _ _ = killFun tree pid >> return True buildWhitelist :: String -> Whitelist -> Whitelist buildWhitelist line whitelist = do case line =~~ "^[ \t]*([^: \t]+)[ \t]*:[ \t]*([^ \t]+)[ \t]*$" of Nothing -> error "Invalid configuration file" Just ([_, exe, user]:_) -> Map.insert exe user whitelist readWhiteList :: FilePath -> IO Whitelist readWhiteList file = do contents <- readFile file return $ foldr buildWhitelist Map.empty (lines contents) allowedUidForExecutable :: Whitelist -> FilePath -> IO Uid allowedUidForExecutable whitelist exe = do case Map.lookup exe whitelist of Nothing -> return "0" Just user -> do entry <- getUserEntryForName user return $ show (userID entry) processBastard :: PsTree -> Whitelist -> KillFunction -> Bool -> Pid -> IO Bool processBastard tree whitelist killFun killed pid = do let PsInfo psData _ = mapLookup pid tree euid = mapLookup "EUid" psData exe = mapLookup "Exe" psData allowedUid <- allowedUidForExecutable whitelist exe if euid /= allowedUid then tryToKill tree killFun pid euid allowedUid killed else return killed withEachBastard :: PsTree -> Whitelist -> KillFunction -> IO Bool withEachBastard tree whitelist killFun = foldM (processBastard tree whitelist killFun) False children where (PsInfo _ children) = mapLookup "1" tree printWarnings :: Pid -> PsData -> IO () printWarnings pid psData = do let exe = mapLookup "Exe" psData let cmd = mapLookup "Cmd" psData let cwd = mapLookup "Cwd" psData let ppid = mapLookup "PPid" psData let euid = mapLookup "EUid" psData let ruid = mapLookup "RUid" psData let egid = mapLookup "EGid" psData if ruid /= euid then hPrintf stderr "PID %s: RUID=%s, EUID=%s\n" pid ruid euid else return () hPrintf stderr "Killing proc %s (%s, UID=%s, GID=%s), child of %s\n" pid exe euid egid ppid hPrintf stderr " Process command line: %s\n" cmd hPrintf stderr " Process working directory: %s\n" cwd killTree :: KillFunction killTree tree pid = do let PsInfo psData children = mapLookup pid tree printWarnings pid psData signalProcess sigKILL (read pid) mapM_ (killTree tree) children killBastards :: PsTree -> Whitelist -> Int -> IO () killBastards tree whitelist n = do runAgain <- withEachBastard tree whitelist killTree if runAgain && n > 1 then do sleep 2 killBastards tree whitelist (n - 1) else return () -- Configuration printConfig :: KillFunction printConfig tree pid = do let PsInfo psData _ = mapLookup pid tree exe = mapLookup "Exe" psData euid = mapLookup "EUid" psData entry <- getUserEntryForID (read euid) putStrLn $ exe ++ ": " ++ (userName entry) -- main helpers config :: PsTree -> IO () config tree = do withEachBastard tree Map.empty printConfig return () pstree :: PsTree -> IO () pstree tree = do printTree tree "1" -- In newer kernels, process 2 is kthreadd, which is not a child -- of init. let info = mapLookup "2" tree if parentPid info /= "1" then printTree tree "2" else return () kill :: PsTree -> IO () kill tree = do whitelist <- readWhiteList "killbastards.conf" killBastards tree whitelist 5 main :: IO () main = do args <- getArgs tree <- createTree case args of ["config"] -> config tree ["pstree"] -> pstree tree [] -> kill tree

3 18

ANNOUNCE: pcre-light, a light, portable regular expression library for Haskell
by Don Stewart 13 Jan '08

13 Jan '08

pcre-light A light regular expression library, using Perl 5 compatible regexes I'm pleased to announce the first release of pcre-light. This library provides a simple, efficient interface to PCRE regular expressions, via either strict ByteStrings or classical Strings. Compilation and matching of regular expressions is done via two functions: compile :: ByteString -> [PCREOption] -> Either String Regex match :: Regex -> ByteString -> [PCREExecOption] -> Maybe [ByteString] A convenience interface for 'Char8' Strings is also provided. == Examples == Although the operations by default take ByteStrings, we can avoid unnecessary 'pack' calls using GHC's support for ByteStrings literals, enabled with -XOverloadedStrings: > :m + Text.Regex.PCRE.Light > :m + Data.ByteString.Char8 > :set -XOverloadedStrings > let Right r = compile "the quick brown fox" [] > match r "the quick brown fox" [] Just ["the quick brown fox"] > match r "the quick brown FOX" [] Nothing We can also enable various matching extensions, > let Right r = compile "the quick brown fox" [caseless] > match r "the quick brown FOX" [] Just ["the quick brown FOX"] Subpatterns, and fancy Perl regex extensions are happily supported: > let Right r = compile "^(abc){1,2}zz" [] > match r "abczz" [] Just ["abczz","abc"] Where the subpattern bound by ( ) was returned as the second element of the list. > let Right r = compile "\\w+(?=\t)" [] > match r "the quick brown\t fox" [] Just ["brown"] You can do lots of silly things with this: > let Right r = compile "^(a()+)+" [] > match r "aaaa" Just ["aaaa", "a", ""] The full set of compile and runtime PCRE extensions are supported. == Get it == * Stable tarballs, (on Hackage, of course): http://hackage.haskell.org/cgi-bin/hackage-scripts/package/pcre-light * Cabal install it! Using the new 'cabal-install', you can automatically download, build and install the package: $ cabal update $ cabal install pcre-light Downloading 'pcre-light-0.1'... Configuring pcre-light-0.1... Preprocessing library pcre-light-0.1... Building pcre-light-0.1... Registering pcre-light-0.1.. And off we go! For more information about cabal-install, see the hackage page for this excellent tool. * Darcs repository: http://code.haskell.org/~dons/code/pcre-light/ * Documentation: http://code.haskell.org/~dons/docs/pcre-light/ * Stability The library takes correctness seriously, and comes with a reasonable testsuite (with plans to greatly extend it), and code coverage data for those tests (using GHC's new -fhpc flag). You can see the test coverage results here: http://code.haskell.org/~dons/tests/pcre-light/hpc_index.html Yours in code, Don P.S. I'd like to encourage other authors to distribute code coverage results for their libraries! hpc is an invaluable tool to ensure high quality libraries for the Haskell community. P.P.S. Consider consider contributing your own light bindings to useful C libraries. The more we have, the more certain and sustainable Haskell development will be :) P.P.P.S. Thanks to #haskell for testing and advice.

1 0

the trivial monad- thoughts and a question
by Brian Hurt 13 Jan '08

13 Jan '08

So, I've been playing around with what I call the trivial monad: module TrivialMonad where data TrivialMonad a = M a recover :: TrivialMonad a -> a recover (M x) = x instance Monad TrivialMonad where (M x) >>= f = f x (M x) >> f = f return x = M x fail s = undefined This is actually a surprisingly usefull little sucker- it allows you to "demonadify" code. Which is usefull when you have some places where you want to use the code within a monad, and some places where you don't. You write the base bit of code monadically, and then demonadify it as needed. The first question I have is it is possible to implement this guy without wrapping the value in a constructor? What I'd like to do is replace the: data TrivialMonad a = M a with something like: type TrivialMonad a = a and then be able to junk the recover function. The second question I have is: is there any hope of getting something like this into the standard library? Thanks, Brian

5 4