- Haskell-Cafe - Haskell.org

c_open and c_close signatures in the unix package
by Galchin Vasili 09 Mar '08

09 Mar '08

Hello, I need to find the c_open and c_close signatures that are referenced in unix/System/Posix/IO.hsc. Thanks, Vasya

2 1

reply to vincent foley's question about poker
by Thomas Hartman 09 Mar '08

09 Mar '08

Weirdly, I came across a question Vincent Foley asked in FA Haskell when I read it in the googlegroups interface, http://groups.google.com/group/fa.haskell/browse_thread/thread/8298c4d838c9… but I don't seem to have his question in my inbox where I get haskell cafe. Maybe it got filtered somehow? I notice nobody else from Haskell Cafe seems to have answered, and this is usually a pretty helpful place so I am thinking maybe it really did get filtered. Oh well, I will answer it anyway now.. The question had to do with writing Arbitrary instances for datatypes useful for playing poker, and using quickCheck with them. I like my solution because I get Arbitrary instances for basically every datatype that's involved, from a single definition that gives you Arbitrary for any type a that is both Enum and Bounded. instance (Enum a, Bounded a) => Arbitrary a where arbitrary = do n <- choose (fromEnum (minBound :: a), fromEnum (maxBound :: a) ) return $ toEnum n Here's the code. (Note: For the code to compile you need the EnumInstances .hs module. I posted this a few minutes ago on haskell cafe.) {-# OPTIONS -fglasgow-exts -fallow-undecidable-instances #-} module Cards where import Test.QuickCheck import Control.Arrow import Debug.Trace import EnumInstances -- Types data Suit = Clubs | Diamond | Heart | Spade deriving (Show, Eq, Bounded, Enum, Ord) data Rank = Ace | Two | Three | Four | Five | Six | Seven | Eight | Nine | Ten | Jack | Queen | King deriving (Show, Eq, Bounded, Enum,Ord) --instance Arbitrary Rank where -- arbitrary = return $ choose data Card = Card (Rank, Suit) deriving (Eq,Show,Bounded, Ord) instance Enum Card where fromEnum (Card (r,s)) = fromEnum (r,s) toEnum i = Card (toEnum i) -- to check a new instance with quickCheck -- quickCheck (pEnum :: SomeType -> Bool) pEnum x = x == (toEnum . fromEnum) x -- type Hand = [Card] -- a hand is five cards data Hand = Hand Card Card Card Card Card deriving (Eq,Show, Bounded) instance Enum Hand where fromEnum (Hand a b c d e) = fromEnum (a,b,c,d,e) toEnum i = Hand a b c d e where (a,b,c,d,e) = toEnum i instance (Enum a, Bounded a) => Arbitrary a where arbitrary = do n <- choose (fromEnum (minBound :: a), fromEnum (maxBound :: a) ) return $ toEnum n -- not a very useful property, and certainly fails -- but it proves we have a working Arbitrary instance for Hand. pHandIsAlwaysAceOfClubs h = h == (Hand c c c c c) where c = Card (Ace, Clubs) t1 = do quickCheck (pEnum :: Rank -> Bool) quickCheck (pEnum :: Suit -> Bool) quickCheck (pEnum :: Card -> Bool) quickCheck (pEnum :: Hand -> Bool) quickCheck pHandIsAlwaysAceOfClubs -- of course this fails traceIt x = trace (show x) x

2 1

Difficulties implementing an incremental parser using Oleg-style left fold enumerator
by Johan Tibell 08 Mar '08

08 Mar '08

Dear haskell-cafe, I'm trying to write a parser combinator library with the following contraints: * Parses LL(1) grammars. * Is incremental i.e. it uses an Oleg style left fold enumerator to receive its input. * Is applicative but not monadic. The problem -- maybe there are others too -- is that when a parser such as many (byte 65) is run it will always return a 'Partial' result waiting for more input even though the enumerator is exhausted. In other words, there's no way to detect end of input. My current implementation of the parser type is newtype Parser r a = Parser { unParser :: S -> (a -> S -> Result r) -> (S -> Result r) -> Result r } where the first parameter is the parse state, the second a success continuation, and the third a failure continuation. The only tricky part (except for the above mentioned problem) is to implement the choice operator. I implement mine as instance Applicative (Parser r) where pure a = ... p <*> p' = Parser $ \s succ fail -> flip (unParser p s) fail $ \f s' -> unParser p' s' (succ . f) fail which I think is correct. Here follows my code. I hope someone has some idea how I could handle the end of input problem correctly. Thanks. -- Johan {-# LANGUAGE DeriveDataTypeable, Rank2Types #-} ----------------------------------------------------------------------------- -- | -- Module : Parsing.IParse -- Copyright : (c) Johan Tibell 2008 -- License : BSD3-style (see LICENSE) -- -- Maintainer : johan.tibell(a)gmail.com -- Stability : experimental -- Portability : portable -- -- An incremental LL(1) parser combinator library. -- ----------------------------------------------------------------------------- module Parsing.IParse ( -- * The 'Parser' type Parser, Enumerator, parse, -- * Primitive parsers satisfy, byte, module Control.Applicative ) where import Control.Applicative (Alternative(..), Applicative(..)) import Control.Monad (Functor(..)) import qualified Data.ByteString as S import Data.Int (Int64) import Data.Typeable (Typeable, showsTypeRep, typeOf) import Data.Word (Word8) import Prelude hiding (fail, succ) -- --------------------------------------------------------------------- -- The Parser type -- | The parse state. data S = S {-# UNPACK #-} !S.ByteString {-# UNPACK #-} !Int64 deriving Show -- | A parse either succeeds, fails or returns a suspension with which -- the parsing can be resumed. data Result a = Finished a S | Failed Int64 | Partial (S.ByteString -> Result a) deriving Typeable -- | For debug output. instance (Show a, Typeable a) => Show (Result a) where showsPrec d (Finished a s) = showParen (d > 10) showStr where showStr = showString "Finished " . showsPrec 11 a . showString " " . showsPrec 11 s showsPrec d (Failed pos) = showParen (d > 10) showStr where showStr = showString "Failed " . showsPrec 11 pos showsPrec d (Partial k) = showParen (d > 10) showStr where showStr = showString "Partial " . showsTypeRep (typeOf k) -- | A parser takes a parse state, a success continuation and a -- failure continuation and returns a 'Result'. newtype Parser r a = Parser { unParser :: S -> (a -> S -> Result r) -> (S -> Result r) -> Result r } -- --------------------------------------------------------------------- -- Instances instance Functor (Parser r) where fmap f p = Parser $ \s succ fail -> unParser p s (succ . f) fail instance Applicative (Parser r) where pure a = Parser $ \s succ _ -> succ a s p <*> p' = Parser $ \s succ fail -> flip (unParser p s) fail $ \f s' -> unParser p' s' (succ . f) fail instance Alternative (Parser r) where empty = Parser $ \s _ fail -> fail s p <|> p' = Parser $ \s@(S _ pos) succ fail -> unParser p s succ $ \s'@(S _ pos') -> if pos == pos' then unParser p' s' succ fail else fail s' -- --------------------------------------------------------------------- -- Running a parser -- | The initial, empty parse state. initState :: S initState = S S.empty 0 -- | This is the final continuation that turns a successful parse into -- a 'Result'. finishedCont :: a -> S -> Result a finishedCont v s = Finished v s -- | This is the final continuation that turns an unsuccessful parse -- into a 'Result'. failedCont :: S -> Result a failedCont (S _ pos) = Failed pos -- | A enumerator is a partially applied left fold over some -- 'S.ByteString' input. The caller supplies an initial seed and an -- iteratee function. The iteratee function returns @Left seed@ if it -- want to terminate the iteration early, otherwise @Right seed@. type Enumerator m s = (s -> S.ByteString -> Either s s) -> s -> m s -- | @parse p enumerator@ runs the parser @p@, pulling in new data -- using @enumerator@ when necessary, and return @Left pos@ on failure -- and @Right val remaining@ on success. parse :: Monad m => Parser r r -> (forall s. Enumerator m s) -> m (Either Int64 (r, S.ByteString)) parse p enumerator = -- First test if the parser can succeed without consuming any -- input. let seed = (unParser p) initState finishedCont failedCont in case seed of Failed pos -> return $ Left pos Finished x (S s _) -> return $ Right (x, s) _ -> -- Otherwise, use the enumerator to feed the parser some -- input. do (result, pos) <- enumerator iter (seed, 0) return $ case result of Failed pos' -> Left pos' Finished x (S s _) -> Right (x, s) Partial _ -> Left pos where iter (Partial k, pos) chunk = let pos' = pos + fromIntegral (S.length chunk) in case k chunk of partial@(Partial _) -> Right (partial, pos') result -> Left (result, pos') iter _ _ = error "Should be partial." -- --------------------------------------------------------------------- -- Primitive parsers -- | The parser @satisfy p@ succeeds for any character for which the -- supplied function @p@ returns 'True'. Returns the character that -- is actually parsed. satisfy :: (Word8 -> Bool) -> Parser r Word8 satisfy p = Parser $ \st@(S s pos) succ fail -> case S.uncons s of Just (b, bs) -> if p b then succ b (S bs (pos + 1)) else fail st Nothing -> Partial $ \s' -> unParser (satisfy p) (S s' pos) succ fail -- | @byte b@ parses a single byte @b@. Returns the parsed byte -- (i.e. @b@). byte :: Word8 -> Parser r Word8 byte b = satisfy (== b)

2 3

[pdxfunc] pdxfunc meeting: Monday, March 10, 7pm, CubeSpace
by Justin Bailey 08 Mar '08

08 Mar '08

The Portland Functional Programming group is meeting again this Monday, March 10, at 7 p.m. Join us! ---------- Forwarded message ---------- From: Igal Koshevoy <igal(a)pragmaticraft.com> Date: Fri, Mar 7, 2008 at 11:26 AM Subject: [pdxfunc] pdxfunc meeting: Monday, March 10, 7pm, CubeSpace To: Igal Koshevoy <igal(a)pragmaticraft.com> Join us at the next meeting of pdxfunc, the Portland Functional Programming Study Group. We'll have presentations, demos and discussions. We welcome programmers interested in all functional languages and our meetings have content for coders of all skill levels. If interested, please also subscribe to our mailing list at http://groups.google.com/group/pdxfunc PRESENTATION * Dr. Bart Massey: Audio Processing With Haskell - Abstract: Dr. Massey will discuss and demonstrate a Haskell implementation of a WAVE file I/O library and compressor-limiter application that he's been working on. He'll also talk about why he chose Haskell to do this. - Speaker: Dr. Bart Massey teaches Computer Science at Portland State University, focusing on open source software engineering and artificial intelligence. He's the current Secretary of the X.org Board of Directors, co-author of the Nickle open source programming language, and spent many years as the faculty advisor the Portland State Aerospace Society that builds open source sounding rockets. REMAINDER We'll spend the rest of the meeting doing open discussion, talking about projects, technical challenges, recent developments, etc. It's a good group with a lot of varied experience, so there won't be any shortage of interesting discussion. NEWS Don Stewart, who gave the group's first presentation, recently announced that the Haskell-based xmonad tiling window manager he helps write is now one year old (http://www.haskell.org/pipermail/xmonad/2008-March/005021.html) and the "Real World Haskell" book that he, Bryan O'Sullivan and John Goerzen are writing has released some new draft chapters for previewing (http://book.realworldhaskell.org/) Congratulations, Don! Anyway, see you at the meeting! --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "pdxfunc" group. To post to this group, send email to pdxfunc(a)googlegroups.com To unsubscribe from this group, send email to pdxfunc-unsubscribe(a)googlegroups.com For more options, visit this group at http://groups.google.com/group/pdxfunc?hl=en -~----------~----~----~----~------~----~------~--~---

1 0

Re: Data.HashTable
by gwern0＠gmail.com 07 Mar '08

07 Mar '08

On 2008.03.06 22:43:53 +0100, Johannes Waldmann <waldmann(a)imn.htwk-leipzig.de> scribbled 1.4K characters: > > In practice, Data.Map outperforms it in essentially all cases > > (Data.HashTable stops working beyond a certain size and so any > > asymptotic benefits, if they exist at all, don't have time to kick > > in). > > What! > > I learned at school, and I teach my students, > * balanced binary tree: costs are log(size) > * hashtable: cost are essentially constant > therefore, hashtable should be preferred in almost all cases > (if you know a reasonable hash function > and except where you need persistency, of course) > > the difference should be visible even for moderate sizes > (e.g. 1000). With a reasonable implementation I expect > log(1000) = 10 comparisons (and dereferencings) for the tree; > while the hashtable should have the computation of the hash value > (ideally, in registers), one memory access, and one comparison. > > ... but indeed some experiments with Data.Map and Data.Hashtable > support the point you made. That's either good for Data.Map > or bad for Data.Hashtable. > > PS: I did not manage to compile HsJudy-1.0 with ghc-6.8.2 > (some hsc file missing - perhaps that should be auto-generated? how?) > > Best regards, Johannes. Oh... I'm terribly sorry about that. It was I who uploaded HsJudy. The problem was, it's maintained by the Pugs project for some reason. The directory structure looks like: pugs/ thirdparty/ HsJudy/ hsregex/ HsSyck/ installed/ judy/ Judy-1.0.3/ Here Judy-1.0.3/ contains the actual C library Judy itself. So what the Cabalized package residing in HsJudy/ was doing was literally linking against stuff like '../judy/Judy-1.0.3/src/JudyL/*.o'. At the time I was packaging, Cabal didn't yet warn about problems like ../, so it would build and install just fine when I ran it with no problems; but I forgot that obviously all the ../ stuff would totally break in an sdist tarball. I think I've fixed it: <http://hackage.haskell.org/cgi-bin/hackage-scripts/package/HsJudy-0.1.1>. -- gwern Air eavesdropping pipe-bomb TSCM Centro ^X JIC TWA USACIL Protection

1 0

Thanks for the help: image of draft visualization
by Jefferson Heard 07 Mar '08

07 Mar '08

Thanks for everyone's help on the list re my Haskell woes with the latest visualization effort. I've been making my code more generic for the last week, and I plan on releasing a visualization framework back to the community at some point. Gotta get approval from my boss before releasing code back to the wild, but here's an image of the draft of the visualization I've been working on: http://vizdata.renci.org/projects/jeff/ProteinViz/ProteinViz.png Basically, what you're seeing is 18,500 genes arranged in a full heirarchical clustering (the clustering technique uses a metric I'm unfamiliar with, and I got the dataset pre-packaged from the guy who's using it). The final visualization is fully interactive and runs fine under Linux, dies a miserable death under windows (runs out of RAM, and I can't figure out why, nor do I particularly care), and primarily runs on our 14 foot by 9 foot (4.5x3 metres for those of us in metric) linux display wall. The full program is about 800 linux of Haskell code using nothing but the standard library under GHC 6.8. Again, thanks for all your help! -- Jeff

2 1

Network.Socket Woes
by Scott Bell 07 Mar '08

07 Mar '08

Hi all, I'm trying to do some standard socket stuff using the Network.Socket library. This example is a UDP server: import Network.Socket proto_udp :: ProtocolNumber proto_udp = 17 port = 10162 main = do s <- socket AF_INET Datagram 17 bindSocket s (SockAddrInet (PortNum port) iNADDR_ANY) putStrLn $ "Listening on port " ++ (show port) ++ "... " (msg, n, addr) <- recvFrom s 1024 putStrLn $ "Received " ++ (show n) ++ " bytes from " ++ (show addr) ++ ": " putStrLn (show msg) Using the equivalent C program (socket, bind, recvfrom) I'm able to successfully receive a 64 byte message from my test program. The Haskell version, however, does not return from recvFrom. I've also tried wrapping this in a withSocketsDo, with no effect. How can I proceed to debug/troubleshoot this program? Thanks, - Scott Bell

7 9

Small displeasure with associated type synonyms
by Stefan Holdermans 07 Mar '08

07 Mar '08

Dear all, I was doing a little experimentation with associated type synonyms and ran into a small but unforeseen annoyance. The following, contrived, example snippets illustrate my pain: First, let us declare some of the simplest classes exhibiting associated type synonyms that I can think of, class C a where type T a val :: T a together with a trivial instance for nullary products: instance C () where type T () = () val = () But then, let us try an instance for binary products: instance (C a, C b) => C (a, b) where type T (a, b) = (T a, T b) val = (val, val) I really thought this would work out nicely, but GHC (version 6.8.2) gracefully gives me Couldn't match expected type `T a2' against inferred type `T a' Expected type: T (a2, b) Inferred type: (T a, T a1) In the expression: (val, val) In the definition of `val': val = (val, val) Couldn't match expected type `T b' against inferred type `T a1' Expected type: T (a2, b) Inferred type: (T a, T a1) In the expression: (val, val) In the definition of `val': val = (val, val) while I think I deserve better than that. Can someone (Tom?) please explain (a) why the required unifications fail, (b) whether or not it is reasonable to expect the unifications to succeed, and (c) how I can overcome problems like these? Surely, I can have val take a dummy argument, but I am hoping for something a bit more elegant here. I tried lexically scoped type variables, but to no avail: instance forall a b. (C a, C b) => C (a, b) where type T (a, b) = (T a, T b) val = (val :: T a, val :: T b) gives me Couldn't match expected type `T a2' against inferred type `T a' In the expression: val :: T a In the expression: (val :: T a, val :: T b) In the definition of `val': val = (val :: T a, val :: T b) etc. Cheers, Stefan

7 10

Analysing Haskell with Graph Theory
by Ivan Miljenovic 07 Mar '08

07 Mar '08

Back in December, I posted that I was thinking about doing a project for my honours year on using graph theory for analysis on Haskell source code, amongst others: http://thread.gmane.org/gmane.comp.lang.haskell.cafe/32912 Well, I've officially started this project, and my supervisor and I have come up with the following functions that would probably be relevant to analysing _any_ piece of source code (the actual code will be tentatively stored as a directed graph with the nodes being functions and the edges being function calls, i.e. if f calls g, there is a directed edge from f to g): * root finding -> find nodes with no incoming edges (in a program, you'd ideally want only main to be such a node) * cycle detection -> find a possibly recursive cycle in your code: if the cycle is too big, then you may wish to consider refactoring * depth analysis -> find leaves that have a depth from the root node that is extremely large compared to the others (if a function is 50 calls down from main compared to an average of 15, you may wish to refactor) * chain detection -> find connected functions that have only one incoming and one outgoing edge, e.g. : f -> g -> h : if g isn't used anywhere else, you may wish to combine it inside either f or g * node popularity -> get a count of how many functions use a particular function and how many other functions it calls (related to chain detection above) * clique detection -> probably not as relevant to source code, but if you have a large number of functions that are all pairwise co-recursive than you may wish to refactor Can anyone think of any other kind of functions that would be useful in this kind of source code analysis? Also, I'm going to be using haskell-src for for the parsing of the Haskell code so that I don't waste my time writing a parser, when my project is technically on the graph-theory side of things. I know that it focuses mainly on H98 with only a few extensions... is this likely to be a problem if I want to try running my eventual program on say ghc or xmonad as test examples? -- Ivan Lazar Miljenovic

4 7

Build dependency problem with bytestring.
by Jon Strait 07 Mar '08

07 Mar '08

Hi all, I'm upgrading HAppS from my 0.9.2 to the current 0.9.2.1 in Hackage. Some HAppS components have built and installed (IxSet and Util). Halfway through the HAppS-State build, the GHC runtime linker gives a fatal error on finding a duplicate definition for symbol fps_minimum while loading bytestring 0.9.0.4 after having already loaded bytestring 0.9.0.1. From trial and error, I'm guessing that HAppS-State needs 0.9.0.1 but one of its build dependencies was built with 0.9.0.4. Using GHC 6.8.2 Linux here. Any suggestions on how best to currently approach this situation? Thanks, Jon

3 3