June 2007 - Haskell-Cafe

Existentials and type var escaping
by Roberto Zunino 23 Jun '07

23 Jun '07

In this function data C = C Int foo :: C -> C foo ~(C x) = C x foo is _not_ the identity: its result must be non bottom, i.e. the constructor C is "forced" to its argument. I wonder if a similar function is definable for existential types: data E = forall a . E a foo :: E -> E foo, as defined above does not work (lazy patterns not allowed), and in foo y = E (case y of E x -> x) a variable escapes. I also tried with CPS with no success. Is foo definable at all? I'm starting to think that it is not, and that there must be a very good reason for that... Thank you, Zun.

4 5

Lambdabot
by Daniel Fischer 23 Jun '07

23 Jun '07

Greetings, now I have a working plugins package, I can refocus on my lambdabot problem. Let me recap: In Lib/Parser.hs, as_name &c are defined #if __GLASGOW_HASKELL__ > 606, however ghc-6.6.1 defines that as 606, so to go through the build, I had to change the '>' to '>='. Is that a bad idea? (otherwise that should be changed in Parser.ly/.hs) Next, in scripts/ShowQ.hs, there is defined an instance (Arbitrary a) => Arbitrary (Maybe a), but such an instance already is defined in Test.QuickCheck, so I commented the one in ShowQ out (after the build died there once). That probably should be fixed in the darcs repo. As anything of the above stupid/dangerous? Okay, so building succeeds without complaints, but then $ ./lambdabot Initialising plugins ................Speicherzugriffsfehler Changing BotPP so that it created a persisting copy of its output, I found out what modulesInfo does, then, letting ircInstallModule produce debugging output, I located the evildoers. lambdabot segfaulted when installing Fact Haddock Quote Source Todo Where What's special about them? I.e., why did they cause a segfault and the others not? And, how could I build a lambdabot _with_ them (though I'm not sure, I'll actually want them, but I might). Without these, I now have an apparently working lambdabot, well, not properly working. First time I started it, all seemed well, but from then on: $ ./lambdabot Initialising plugins ..................................sending message to bogus server: IrcMessage {msgServer = "freenode", msgLBName = "urk!<outputmessage>", msgPrefix = "", msgCommand = "NAMES", msgParams = [""]} ............... done. Main: caught (and ignoring) IRCRaised Data.ByteString.index: index too large: 0, length = 0 lambdabot> > 3+7 Main: caught (and ignoring) IRCRaised Data.ByteString.index: index too large: 0, length = 0 10 lambdabot> The bogus message thing also appeared the first time, I hope this is meant to be so. But what about the ByteString.index exception? Where might that come from? How to get rid of it? Finally, is there a tutorial/manual for using lambdabot? Thanks for any help, Daniel

5 7

Odd lack of laziness
by Jefferson Heard 23 Jun '07

23 Jun '07

Alright, I've been hacking away at what I posted the other day, and I have something that works for files that will fit entirely into memory. And then I figured out why I've been restricted to files that fit entirely into memory... One of my functions is causing the entire thing to be read in, when, in the way I analyze the program, only a very small portion of the file should be read in. Here are the functions I've used to test this problem... import Data.Bits import qualified Data.ByteString.Lazy as BS import Foreign.C.Types ... {-# INLINE decodeLengthBits #-} decodeLengthBits :: BS.ByteString -> CInt decodeLengthBits doc = (shift (pieces !! 3) 24) .|. (shift (pieces !! 2) 16) .|. (shift (pieces !! 1) 8) .|. (pieces !! 0) where pieces::[CInt] = map fromIntegral . BS.unpack . BS.take 4 $ doc breakIntoDocuments :: RawDocument -> [RawDocument] breakIntoDocuments f | BS.length f > 0 = if len > 0 then (BS.take bytes f) : (breakIntoDocuments (BS.drop bytes f)) else (breakIntoDocuments (BS.drop bytes f)) | otherwise = [] where len = decodeLengthBits f bytes = fromIntegral (len * 2 + len * 4 + 4) and a main function of: main = do f <- B.readFile "Documents.bin" print (take 1 (breakIntoDocuments f)) Shouldn't the program only read in enough of the lazy byte-string to create the first return value of breakIntoDocuments? The return value of decodeLengthBits is only 277. I watched it, and it's reading in my whole 2gb file... -- Jeff

9 9

"Graphical Haskell"
by peterv 23 Jun '07

23 Jun '07

In the book "Haskell School of Expression", streams are nicely explained using a graphical flow graph. This is also done more or less in http://research.microsoft.com/~simonpj/papers/marktoberdorf/Marktoberdorf.pp t to explain monads and other concepts. I would like to create a program that allows you to create such flow graphs, and then let GHC generate the code and do type inference. I found a paper where Haskell is used to create a GUI application with undo/redo etc for creating graphical Basian networks (http://www.cs.uu.nl/dazzle/f08-schrage.pdf) so this gave me confidence that I could it do all in Haskell. Now, instead of generating Haskell code (which I could do first, would be easier to debug), I would like to directly create an AST, and use an Haskell API to communicate with GHC. I already found out that GHC indeed has such an API, but how possible is this idea? Has this been done before? I only found a very old attempt at this, confusingly also called "Visual Haskell", see http://ptolemy.eecs.berkeley.edu/%7Ejohnr/papers/visual.html, but I can't find any source code for that project. I did a similar project in C# that generated C++ code, so I've done it before, just not in Haskell. Thanks a lot, Peter

7 9

Shouldn't this be lazy???
by Olivier Boudry 23 Jun '07

23 Jun '07

Hi all, I'm playing with the TagSoup library trying to extract links to original pictures from my Flickr Sets page. This programs first loads the Sets page, open links to each set, get links to pictures and then search for original picture link (see steps in main function). It does the job, but for the tests I just wanted to take 10 links to reduce the time the program runs. Just hoping that haskell laziness would magically take the minimum amount of data required to get the first 10 links out of this set of pages. I did this replacing: (putStrLn . unlines . concat) origLinks with (putStrLn . unlines . take 10 . concat) origLinks in the main function. With the last version of that line, I effectively only get 10 links but the runtime is exactly the same for both main functions. As I'm a newbie haskell programmer I certainly missing something. By the way I know Flickr has an api I could use, but the purpose was playing with TagSoup. Thanks for any advice. Olivier. Here's the code: module Main where import Data.Html.TagSoup import Control.Monad (liftM) import Data.List (isPrefixOf, groupBy) import Data.Maybe (mapMaybe) import System (getArgs) import System.Time import IO (hPutStrLn, stderr) base = "http://www.flickr.com" setsUrl name = "/photos/" ++ name ++ "/sets/" main :: IO () main = do args <- getArgs tStart <- getClockTime setLinks <- getLinksByAttr ("class", "Seta") (base ++ setsUrl (args !! 0)) picLinks <- mapM (getLinksByAttr ("class", "image_link")) setLinks origLinks <- mapM (getLinksAfterImgByAttr ("src", "http://l.yimg.com/www.flickr.com/images/icon_download.gif")) $ (mapMaybe linkToOrigSize . concat) picLinks (putStrLn . unlines . concat) origLinks tEnd <- getClockTime hPutStrLn stderr ( timeDiffToString $ diffClockTimes tEnd tStart ) -- | extract all links from "a" tag types having given attribute getLinksByAttr :: (String, String) -> String -> IO [String] getLinksByAttr attr url = do sects <- getSectionsByTypeAndAttr "a" attr url return $ hrefs sects -- | get "a" tags following a "img" having a specific attribute getLinksAfterImgByAttr :: (String, String) -> String -> IO [String] getLinksAfterImgByAttr attr url = do sects <- getSectionsByTypeAndAttr "img" attr url return $ hrefs $ map (dropWhile (not . isTagOpen) . drop 1) sects -- | create sections from tag type and attribute getSectionsByTypeAndAttr :: String -> (String, String) -> String -> IO [[Tag]] getSectionsByTypeAndAttr tagType attr url = do tags <- liftM parseTags $ openURL $ url (return . filterByTypeAndAttr tagType attr) tags where filterByTypeAndAttr :: String -> (String, String) -> [Tag] -> [[Tag]] filterByTypeAndAttr t a = sections (~== TagOpen t [a]) -- | extract href values from sections of "a" tags hrefs :: [[Tag]] -> [String] hrefs = map (addBase . fromAttrib "href" . head) where addBase :: String -> String addBase s | "http://" `isPrefixOf` s = s addBase s | otherwise = base ++ s -- | transform a link to a picture into a link to the original size picture linkToOrigSize :: String -> Maybe String linkToOrigSize link = if parts !! 3 == "photos" then Just $ newUrl parts else Nothing where parts = map tail $ groupBy (const(/='/')) link newUrl p = "http://www.flickr.com/photo_zoom.gne?id=" ++ p !! 5 ++ "&size=o&context=" ++ p !! 7

5 8

A probably-stupid question about a Prelude implementation.
by Michael T. Richter 23 Jun '07

23 Jun '07

So, I'm now going over the code in the 'Report with a fine-toothed comb because a) I'm actually able to read it now pretty fluently and b) I want to know what's there in detail for a project I'm starting. I stumbled across this code: any :: (a -> Bool) -> [a] -> Bool any p = or . map p or :: [Bool] -> Bool or = foldr (||) False Now I see how this works and it's all elegant and clear and all that. But I have two nagging problems with it (that are likely related): 1. Using foldr means I'll be traversing the whole list no matter what. This implies (perhaps for a good reason) that it can only work on a finite list. 2. I don't see any early bale-out semantics. The way I read this it's going to expand a whole list of n and perform n comparisons (including the one with the provided False). Considering that I only need a single True result to make the whole expression true, I'd have expected there to be some clever semantics to allow exactly this. But what I'm seeing, unless I'm really misreading the code, is that if I give it a list of a million boolean expressions, it will cheerfully evaluate these million boolean expressions and perform a million calls to (||) before giving me a result. Please tell me I'm wrong and that I'm missing something? -- Michael T. Richter <ttmrichter(a)gmail.com> (GoogleTalk: ttmrichter(a)gmail.com) There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies. (Charles Hoare)

9 10

copy-on-write monad?
by Greg Meredith 22 Jun '07

22 Jun '07

Fellow Functionally-Caffeinated, i have a few questions regarding copy-on-write semantics. i am working for a client that is stuck with a legacy in-house language that chose copy-on-write as a way to provide aliasing-issue-free semantics to a user population they perceived as not sophisticated in programming. Despite the fact that they are now realizing there are a lot of very sophisticated and performant ways of providing ways to avoid aliasing problems, they are stuck having to support copy-on-write for legacy codes. So, i have two basic questions. First, has anyone worked out a monadic approach to copy-on-write? (And, Is there any analysis of perf characteristics of said monadic schemes?) Second, i have worked out a scheme which is like a version control system. The mutable collection is treated like a source tree. A reference to a mutable collection is like a tag for a branch of the tree. Updates attach deltas to a given branch of the tree. Accesses have to be matched to see if they are impacted by any update-deltas. There is an optimization/memo-ization strategy in which certain events (access or update) trigger a copy to be made, finally, and the updates applied to the copy. This shifts perf characteristics so that access becomes slower and update considerably faster in the common case. Does anyone know if such a scheme has been studied? i'd like to compare implementations, too, if possible. Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

1 0

Telling the time
by Andrew Coppin 22 Jun '07

22 Jun '07

Greetings. Is there a standard library function anywhere which will parse a string into some kind of date/time representation? And, further, is there some function that will tell me how many seconds elapsed between two such times? (I see there's a giant pile of modules to do with dates and times, but I can't make much sense out of them - and in at least one place, the documentation on the Haskell website doesn't actually match what's installed on my computer!) I want to write a program which reads a file of the form 2007-05-26 11:23:16 PM|Begin processing... 2007-05-26 11:23:16 PM|Done stage #1 2007-05-26 11:23:21 PM|Done stage #2 2007-05-26 11:24:05 PM|Done stage #3 and produce a new file of the form 2007-05-26 11:23:16 PM|Begin processing... +0|Done stage #1 +5|Done stage #2 +44|Done stage #3 Ideally I'd like to have it able to parse several slightly differing date/time formats. (It turns out my programs all log using a very subtly different format!) Before I go on an 8-month expedition to reimplement this myself, is there something I can use in the library?

3 3

Type-level Programming
by Vincenz Syntactically 22 Jun '07

22 Jun '07

Dear all, Recently I was playing around with encoding matrices in the type-level system. Thereby one can enable the multiplication of matrices. The general idea (which can be read about at ( http://notvincenz.blogspot.com/2007/06/generalized-matrix-multiplication.ht…) is that there is more than one way to multiplly a matrix. Given two matrices A and B, with M and N dimensions: a_1*...*a_m and b_1*...*b_n then whenever the last L dimensions of A match the first L dimensions of B, they can be multiplied to have a matrix of dimension: a_1*..*a_(m-l)*b_(l+1)*...*b_n What one does is a dot-product on those middle L dimensions. This is what I tried to do in the code in the blogpost. However, I was unable to formulate the constraints for the final multiplication class that does the actual proper cross-multiplication. Is this at all possible, or was I chasing ghosts? Best regards, Christophe

1 0

haskell crypto is reaaaaaaaaaally slow
by Anatoly Yakovenko 22 Jun '07

22 Jun '07

$ time ./md5sum ./md5sum [105,252,52,138,187,192,216,17,225,123,185,3,124,101,86,132] real 0m4.790s user 0m3.688s sys 0m0.492s $ time md5sum ./md5sum 69fc348abbc0d811e17bb9037c655684 ./md5sum real 0m0.023s user 0m0.000s sys 0m0.008s this is my implementation using crypto (http://www.haskell.org/crypto/) Am I doing something wrong? module Main where import System import qualified Data.Digest.MD5 as MD5 import qualified Data.ByteString as BS main = do args <- getArgs dt <- BS.readFile $ head args putStrLn $ show $ MD5.hash . BS.unpack $ dt

12 31