- Haskell-Cafe - Haskell.org

Draw K-ary forest in dot script
by larry.liuxinyu 10 Jan '11

10 Jan '11

Hi, I wrote a Haskell program to parse K-ary forest and convert it to dot script (Graphviz). Here is the literate program. -- First is some stuff imported: module Main where import System.Environment (getArgs) import Text.ParserCombinators.Parsec import Control.Monad (mapM_) import Data.List (concatMap, intercalate) import System.IO (writeFile) import Data.Char (isSpace) -- For each tree in the forest, it is described in pre-order. -- Example description string of a forest of CLRS[1] Figure 19.5(a): -- (12), (7, (25)), (15, (28, (41)), (33)) -- Definition of K-ary node data Node a = Node { root :: a , children :: [Node a]} deriving (Eq, Show) -- Definition of Forest type Forest a = [Node a] -- parsers -- a forest is a list of trees separate by ',' forest = do ts <- node `sepBy` (char ',') return ts -- a node contains a key then followed by a children forest or nothing (leaf case) node = do char '(' elem <- key ts <- (try (char ',')>>forest) <|> return [] char ')' return (Node elem ts) -- a key is just a plain literate string. key = many (noneOf ",()") -- Command line arguments handling parseArgs :: [String] -> (String, String) parseArgs [fname, s] = (fname, s) parseArgs _ = error "wrong usage\nexample:\nfr2dot output.dot \"(12), (7, (25)), (15, ((28, (41)), 33))\"" -- A simplified function to generate dot script from parsed result. toDot f = forestToDot f "t" True -- a handy function to convert children of a K-ary tree to dot script treesToDot ts prefix = forestToDot ts prefix False -- convert a forest to dot script forestToDot [] _ _ = "" forestToDot [t] prefix _ = nodeToDot t prefix forestToDot ts@(_:_:_) prefix lnk = (concatMap (\t->nodeToDot t prefix) ts) ++ consRoot where consRoot = "{rank=same " ++ ns ++ vis ++ "}\n" ns = intercalate "->" $ map (\t -> prefix ++ root t) ts vis = if lnk then "" else "[style=invis]" -- convert a node to dot script nodeToDot (Node x ts) prefix = prefix'++"[label=\""++x++"\"];\n" ++ (treesToDot ts prefix') ++ (defCons ts prefix') where prefix' = prefix ++ x -- define connections among nodes in dot format defCons ts prefix = concatMap f ts where f (Node x _) = prefix++"->"++prefix++x++";\n" -- generate dot script from a parsed forest genDot fname (Right f) = writeFile fname dots >> putStrLn dots where dots = "digraph G{\n\tnode[shape=circle]\n"++(addTab $ toDot f)++"}" addTab s = unlines $ map ("\t"++) (lines s) main = do args <- getArgs let (fname, s) = parseArgs args genDot fname (parse forest "unknown" (filter (not.isSpace) s)) -- END I tested with the following simple cases: ./fr2dot foo.dot "(12), (7, (25)), (15, (28, (41)), (33))" ./fr2dot bar.dot "(18), (3, (37)), (6, (8, (30, (45, (55)), (32)), (23, (24)), (22)), (29, (48, (50)), (31)), (10, (17)), (44))" Run the following commands can convert to PNG files: ./dot -Tpng -o foo.png foo.dot ./dot -Tpng -o bar.png bar.dot Reference: [1]. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. ``Introduction to Algorithms, Second Edition''. The MIT Press, 2001. ISBN: 0262032937. Best regards. -- Larry, LIU https://sites.google.com/site/algoxy/home

2 1

Ratification for my understanding of functors
by C K Kashyap 10 Jan '11

10 Jan '11

Hi, Thanks to Luke Palmer's explanation. I got a better idea of functors. I just want to ratify my understanding of what a functor is - according to category theory, functors are arrows between categories ... these arrows map objets and arrows from one category into another. So, would it be right to say that the list type constructor + the map function form the functor? Saying "list is a functor then is a convenient approximation right? In this context, could someone please point me to some writeup on co-variant/contravariant type constructors? Googling for it seems to only give a lot of C++/Java/C# hits. Regards, Kashyap

3 3

GHC.Ptr, Foreign.Storable, Data.Storable.Endian, looking for good examples of usage
by Aaron Gray 10 Jan '11

10 Jan '11

Hi, I am trying to work out how to use GHC.Ptr, Foreign.Storable, Data.Storable.Endian, and am looking for good examples of usage. Many thanks in advance, Aaron

4 7

ANNOUNCE: Monad.Reader Issue 17
by Brent Yorgey 09 Jan '11

09 Jan '11

I am pleased to announce that Issue 17 of The Monad.Reader is now available [1]. Issue 17 consists of the following three articles: * List Leads Off with the Letter Lambda by Douglas M. Auclair * The InterleaveT Abstraction: Alternative with Flexible Ordering by Neil Brown * The Reader Monad and Abstraction Elimination by Petr Pudlak Feel free to browse the source files [2]. You can check out the entire repository using darcs: darcs get http://code.haskell.org/~byorgey/TMR/Issue17 Watch for a special announcement regarding Issue 18 soon! [1] http://themonadreader.files.wordpress.com/2011/01/issue17.pdf [2] http://code.haskell.org/~byorgey/TMR/Issue17

1 0

Re: [Haskell-cafe] [Haskell-beginners] theStdGen unsafePerformIO
by Antoine Latter 09 Jan '11

09 Jan '11

You might get more answers to this sort of question on the haskell-cafe list. Even there, I think you might need to ask whoever the authors were for a question like this :-) On Sun, Jan 9, 2011 at 9:55 AM, John Smith <voldermort(a)hotmail.com> wrote: > Why does theStdGen require unsafePerformIO? I recompiled the Random module > with > > theStdGen :: IO (IORef StdGen) > theStdGen = do > rng <- mkStdRNG 0 > newIORef rng > > The implementations of a few functions needed to change slightly (to extract > the IORef from IO), but no other type signatures needed changing, and > nothing blew up. > > > _______________________________________________ > Beginners mailing list > Beginners(a)haskell.org > http://www.haskell.org/mailman/listinfo/beginners >

1 0

Generalizing catMaybes
by Tony Morris 08 Jan '11

08 Jan '11

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 I am wondering if it possible to generalise catMaybes: (Something f, SomethingElse t) => t (f a) -> t a I have being doing some gymnastics with Traversable and Foldable and a couple of other things from category-extras to no avail. Perhaps someone else's brain is molded into an appropriate shape to reveal an answer! - -- Tony Morris http://tmorris.net/ -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iEYEARECAAYFAk0n0lwACgkQmnpgrYe6r6155gCeLjYizQ/5w1r2qkecbEqiQqq5 ihIAn1bmmK/qNFxM2sSusqjJu/g2/lH7 =+SdM -----END PGP SIGNATURE-----

6 14

Type System vs Test Driven Development
by Jonathan Geddes 08 Jan '11

08 Jan '11

Cafe, In every language I program in, I try to be as disciplined as possible and use Test-Driven Development. That is, every language except Haskell. There are a few great benefits that come from having a comprehensive test suite with your application: 1. Refactoring is safer/easier 2. You have higher confidence in your code 3. You have a sort of 'beacon' to show where code breakage occurs Admittedly, I don't believe there is any magical benefit that comes from writing your tests before your code. But I find that when I don't write tests first, it is incredibly hard to go back and write them for 'completed' code. But as mentioned, I don't write unit tests in Haskell. Here's why not. When I write Haskell code, I write functions (and monadic actions) that are either a) so trivial that writing any kind of unit/property test seems silly, or are b) composed of other trivial functions using equally-trivial combinators. So, am I missing the benefits of TDD in my Haskell code? Is the refactoring I do in Haskell less safe? I don't think so. I would assert that there is no such thing as refactoring with the style of Haskell I described: the code is already super-factored, so any code reorganization would be better described as "recomposition." When "recomposing" a program, its incredibly rare for the type system to miss an introduced error, in my experience. Am I less confidence in my Haskell code? On the contrary. In general, I feel more confident in Haskell code WITHOUT unit tests than code in other languages WITH unit tests! Finally, am I missing the "error beacon" when things break? Again I feel like the type system has got me covered here. One of the things that immediately appealed to me about Haskell is that the strong type system gives the feeling of writing code against a solid test base. The irony is that the type system (specifically the IO monad) force you to structure code that would be very easy to test because logic code is generally separated from IO code. I explained these thoughts to a fellow programmer who is not familiar with Haskell and his response was essentially that any language that discourages you from writing unit tests is a very poor language. He (mis)quoted: "compilation [is] the weakest form of unit testing" [0]. I vehemently disagreed, stating that invariants embedded in the type system are stronger than any other form of assuring correctness I know of. I know that much of my code could benefit from a property test or two on the more complex parts, but other than that I can't think that unit testing will improve my Haskell code/programming practice. Am I putting too much faith in the type system? [0] http://blog.jayfields.com/2008/02/static-typing-considered-harmful.html

17 23

Is this the "right" way to do polymorphism?
by Daryoush Mehrtash 08 Jan '11

08 Jan '11

I am trying to evaluate the polymorphism technique used in Hackage library. I like to know if the approach taken is "right" or not. The code in question is in the Hoaut package http://hackage.haskell.org/package/hoauth/ As far as I can understand the code wants to have polymorphism on HTTP client such that it can use different underlying HTTP. The package comes with Curl and Debug implementation of its HTTPClient class. My question is with how the polymorphism is used. In function such as "serviceRequest" in the Network.OAuth.Consumer module you have: -- | Performs a signed request with the available token. serviceRequest :: (HttpClient c,MonadIO m) => c -> OAuthRequest -> OAuthMonadT m Response serviceRequest c req = do { result <- lift $ runClient c (unpackRq req) ; case (result) of Right rsp -> return rsp Left err -> fail $ "Failure performing the request. [reason=" ++ err ++"]" } The function expects the HTTPClient implementation to be the first argument to the function. Is that the right thing to do? Or should the instance of the client be a type parameter in the computation (in this case OAuthMonadT)? thanks, Daryoush

3 2

Review request for my encoding function
by C K Kashyap 08 Jan '11

08 Jan '11

Hi, I've written a function to encode a color value of type (Int,Int,Int) into 8,16 or 32 byte ByteString depending on the value of bits per pixel. This is for my VNC server implementation. I'd appreciate some feedback on the Haskellism of the implementation. import Data.Bits import Data.ByteString.Lazy import Data.Binary.Put import Data.Word type Red = Int type Green = Int type Blue = Int type Color = (Red,Green,Blue) encode :: Color -> Int-> Int-> Int-> Int-> Int-> Int-> Int -> ByteString encode (r,g,b) bitsPerPixel redMax greenMax blueMax redShift greenShift blueShift = runPut $ do case bitsPerPixel of 8 -> putWord8 z8 16 -> putWord16be z16 32 -> putWord32be z32 where z8 = (fromIntegral $ nr + ng + nb) :: Word8 z16 = (fromIntegral $ nr + ng + nb) :: Word16 z32 = (fromIntegral $ nr + ng + nb) :: Word32 nr = scale r redMax redShift ng = scale g greenMax greenShift nb = scale b blueMax blueShift scale c cm cs = (c * cm `div` 255) `shift` cs Regards, Kashyap

2 4

problem with haskell-mode mailing list?
by Alex Ott 08 Jan '11

08 Jan '11

Hello all Sorry for writing into this mailing list, but I couldn't get answer from support(a)community.haskell.org address because my mails are returned with errors. And I couldn't found The problem is that if I send mail to haskellmode-emacs(a)projects.haskell.org my mails are not delivered to mailing list with error that google mail server couldn't connect to haskell.org's mail server. If somebody could help me with this problem, please contact me - I'll provide more details on this issue -- With best wishes, Alex Ott, MBA http://alexott.blogspot.com/ http://alexott.net/ http://alexott-ru.blogspot.com/ Skype: alex.ott

1 0