- Haskell-Cafe - Haskell.org

happy + alex parsing question
by Roman Dzvinkovsky 17 Feb '11

17 Feb '11

Hi, using alex+happy, how could I parse lines like these? > "mr <username> says <message>\n" where both <username> and <message> may contain arbitrary characters (except eol)? If I make lexer tokens > "mr " { T_Mr } > " says " { T_Says } > \r?\n { T_Eol } > . { T_Char $$ } and parser > 'mr ' { T_Mr } > ' says ' { T_Says } > eol { T_Eol } > char { T_Char } ... > line :: { (String, String) } > : 'mr ' string ' says ' string eol { ($2, $4) } > string :: { String } > : char { [ $1 ] } > | char string { $1 : $2 } then I get error when <username> or <message> contain "mr " substrings, because parser encounters T_Mr token. Workaround is mention all small tokens in my <string> definition: > string :: { String } > : { [] } > | 'mr ' string { "mr " ++ $2 } > | ' says ' string { " says " ++ $2 } > | char string { $1 : $2 } but that is weird and I'm sure there is a better way. Thanks for advance, Roman.

3 3

Using MonadFix to tie the knot with STM
by Sebastiaan Visser 17 Feb '11

17 Feb '11

Hi all, During a little experiment I discovered there is no MonadFix instance available for the STM monad. Is this absence the consequence of some deep restriction of how STM works or 'just accidental'? Is there some way I could derive this instance? For those who are interested and may know other ways to solve my problem, I'm trying to tie the knot in a graph by using transactional variables as the edges between nodes. I'm trying to do this in a rather generic way: > {-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable, StandaloneDeriving, DoRec #-} > module Graph where > > import Control.Applicative > import Control.Concurrent.STM > import Control.Monad.Fix > import Data.Maybe > import Data.Foldable > import Data.Traversable > import Prelude hiding (mapM) > import qualified Data.Map as M > > instance MonadFix STM where > mfix = error "I need this instance!" -- What to do? > > -- A single node is a graph, has a list of both incoming and outgoing edges. > > data Node edge = Node > { nodeId :: NodeId > , payload :: String > , incoming :: [edge] > , ougoing :: [edge] > } deriving (Functor, Foldable, Traversable) > > type NodeId = String > > -- A graph with an index on the nodes by NodeId, parametrized with the type we > -- want to used as the edge pointer. > > type Graph edge = M.Map NodeId (Node edge) > > -- Type level fixed point combinator with a TVar annotation. > > newtype TFix f = TIn { tout :: TVar (f (TFix f)) } > > -- Take a graph that uses NodeIds as edges and recursively transform it into a > -- graph with TVars to the neighbouring nodes in the edges. > > tieTheKnot :: Graph NodeId -> STM (Graph (TFix Node)) > tieTheKnot untied = > do rec tied <- (mapM . mapM) (\nodeid -> TIn <$> newTVar (tryLookup nodeid tied)) untied > return tied > > -- Helper function to lookup a pre-tied node from a graph, throws an error when > -- the edge could not be resolved. This should, of course, not happen! > > tryLookup :: NodeId -> Graph (TFix Node) -> Node (TFix Node) > tryLookup i = fromJust (error msg) . M.lookup i > where msg = "tieTheKnot: Lookup error, input is an incomplete graph." Thanks in advance, -- Sebastiaan Visser http://www.silkapp.com

3 3

Alex monadUserState question
by Mihai Maruseac 17 Feb '11

17 Feb '11

Hi, Just downloaded the latest Alex package from Hackage (different from the one in Ubuntu's repositories by 2 minor versions) and found that the monadUserState wrapper still misses 2 functions for dealing with changes in the user supplied state. Is this intended or it was an unwanted omission? Thanks, Mihai

1 0

Haskell Weekly News: Issue 169
by Daniel Santa Cruz 17 Feb '11

17 Feb '11

Welcome to issue 169 of the HWN, a newsletter covering developments in the [1]Haskell community. This release covers the week of February 6 - 12, 2011. Congrats to Bryan O'Sullivan and Mark Lentczner for pulling off a successfull [2]BayHac 2011! Announcements Joao Fernandes [3]sent out a call for papers for the 4th International Conference on Software Language Engineering to be held in Braga, Portugal, 3-6 July 2011. Bas van Dijk annouced [4]version 0.1 and [5]version 0.2 of his monad-control library. "monad-control is a rewrite of monad-peel than uses CPS style operations and exploits RankNTypes language extensions to simplify and speed up most functions." Gregory Collins and the Snap team [6]proudly announced the release of Snap 0.4 "containing a whole bunch of nifty new features." Peter Scott [7]announced pwstore, a library that aims to "handle all the details of password storage for you, in a way that should be so easy to use that there's no reason not to use it." Bas van Dijk [8]released case-insensitive 0.1. "The package provides the module Data.CaseInsensitive which exports the CI type constructor which can be parameterised by a string-like type... Comparisons of values of the resulting type are then insensitive to cases." Ryan Newton [9]released a package to do accelerated AES and RNG. Brent Yorgey [10]sent in a second call for submissions to the Monad.Reader -- special poetry and fiction edition. John Lato [11]released version 3.0.1 of ListLike, which "provides polymorphic functions with Data.List-style api for many different data types, including list, arrays, and bytestrings. John also [12]released version 0.7.0.2 and 0.8.0.1 of iteratee, after discovering a memory leak which affects all current versions of iteratee. He states that he would "strongly encourage all users of earlier versions to upgrade to one of these releases." Ganesh Sittampalam and the darcs team are [13]pleased to announce version 2.5.1, a minor upgrade for the 2.5 release. "The main focus of this release is support for the GHC 7.0 series and the upcoming February 2011 Haskell Platform, but the release also includes bug fixes and minor usability improvements." Trystan Spangler [14]announced the release of hspec: Behavior Driven Development for Haskell. "hspec ties together requirements and code that verifies the requirements are met. The verifying code can be a boolean expression, a QuickCheck property, or an explination of why it's pending. The requirements can then be turned into documentation of what the code does and what remains to be implemented." Wren Ng Thornton [15]announce bytestring-trie 0.2.3, a "long awaited release for efficient finite maps from (byte)strings to values." Brent Yorgey would like to invite you to [16]save the date for the Haskell hackathon in Philadelphia, July 29-31. Quotes of the Week * smerdyakov: Some might argue that you can derive False from a sentence containing both "dependent types" and "contract programming." * Einstein: Make everything as simple as possible, but not simpler. * Einskell: Make everything as monad as possible, but not monadder. * kmc: it's important to show that Haskell is usable not just for useless maths, but also for real-world tasks such as rendering teapots * ddarius: Attempting to join #not-not-math sent me to #math. Freakin' Boole. * gwern: [quoting a hypothetical edwardk] 'I HAVE CONSUMED YOUR KNOWLEDGE; LEAVE ME LEST I CONSUME YOUR FLESH AS WELL' * monochrom: @let germanize = concat . words Top Reddit Stories * Announcing: Snap Framework v0.4 Domain: snapframework.com, Score: 40, Comments: 3 On Reddit: http://www.reddit.com/r/haskell/comments/fgc38/announcing_snap_framework_v0… Original: http://snapframework.com/blog/2011/02/05/snap-0.4-released * Haskell Summers of Code retrospective (updated for 2010) Domain: gwern.net, Score: 31, Comments: 7 On Reddit: http://www.reddit.com/r/haskell/comments/fid5w/haskell_summers_of_code_retr… Original: http://www.gwern.net/Haskell%20Summer%20of%20Code.html * How to write type-level lambda-abstractions at the value level Domain: haskell.org, Score: 26, Comments: 7 On Reddit: http://www.reddit.com/r/haskell/comments/fjbxw/how_to_write_typelevel_lambd… Original: http://www.haskell.org/pipermail/haskell-cafe/2011-February/089184.html * Storing passwords securely: don't roll your own Domain: finger-tree.blogspot.com, Score: 25, Comments: 22 On Reddit: http://www.reddit.com/r/haskell/comments/fgm26/storing_passwords_securely_d… Original: http://finger-tree.blogspot.com/2011/02/storing-passwords-securely-in-haske… * #haskell-game & Haskellers Game Interest Group Domain: self.haskell, Score: 25, Comments: 3 On Reddit: http://www.reddit.com/r/haskell/comments/fjzz0/haskellgame_haskellers_game_… Original: /r/haskell/comments/fjzz0/haskellgame_haskellers_game_interest_group/ * Type class generics to be replaced in GHC 7.2 or 7.4 Domain: haskell.org, Score: 24, Comments: 2 On Reddit: http://www.reddit.com/r/haskell/comments/fiq7o/type_class_generics_to_be_re… Original: http://www.haskell.org/pipermail/glasgow-haskell-users/2011-February/020006… * What can I do with Haskell? Domain: self.haskell, Score: 22, Comments: 33 On Reddit: http://www.reddit.com/r/haskell/comments/fgfh9/what_can_i_do_with_haskell/ Original: /r/haskell/comments/fgfh9/what_can_i_do_with_haskell/ * There seems to be lots of interest in SMT solvers in the Haskell community these days, so I started ##smt on freenode Domain: self.haskell, Score: 20, Comments: 6 On Reddit: http://www.reddit.com/r/haskell/comments/fh2zw/there_seems_to_be_lots_of_in… Original: /r/haskell/comments/fh2zw/there_seems_to_be_lots_of_interest_in_smt_solvers/ * darcs 2.5.1 released Domain: lists.osuosl.org, Score: 16, Comments: 0 On Reddit: http://www.reddit.com/r/haskell/comments/fj46y/darcs_251_released/ Original: http://lists.osuosl.org/pipermail/darcs-users/2011-February/026018.html * monad-control Domain: mail-archive.com, Score: 11, Comments: 2 On Reddit: http://www.reddit.com/r/haskell/comments/fgbao/monadcontrol/ Original: http://www.mail-archive.com/haskell@haskell.org/msg23278.html Top StackOverflow Answers * How does Data.MemoCombinators work? votes: 20 Read on SO: http://stackoverflow.com/questions/4980102/how-does-data-memocombinators-wo… This library is a straightforward combinatorization of the well-known technique of memoization. Let's start with the canonical example: fib = (map fib' [0..] !!) where fib' 0 = 0 fib' 1 = 1 fib' n = fib (n-1) + fib (n-2) I interpret what you said to mean that you know how and why this works. So I'll focus on the combinatorization. We ... * What's similar to fmap for monadic values? votes: 16 Read on SO: http://stackoverflow.com/questions/4927014/whats-similar-to-fmap-for-monadi… pelotom's answer is the straightforward one. But not the fun one! sequence is the Haskell function that one can think of as flipping the order of type constructors between a list and a monad. sequence :: (Monad m) => [m a] -> m [a] Now what you want is, so to speak, to flip the order of type constructors between a Maybe and a monad. Data.Traversable ... * Does there exist a monad instance for Data.Map / Data.IntMap? votes: 15 Read on SO: http://stackoverflow.com/questions/4973335/does-there-exist-a-monad-instanc… Is there any particular reason you want to avoid using monad transformers? if you get the MaybeT package from Hackage you can achieve what you want like this: import Control.Monad import Control.Monad.Maybe import Control.Monad.State import qualified Data.Map as Map type MapM k v a = MaybeT (State (Map.Map k v)) a lookupM k = MaybeT $ Map.lookup k `liftM` ... * How to split a string in Haskell? votes: 11 Read on SO: http://stackoverflow.com/questions/4978578/how-to-split-a-string-in-haskell… There is a package for this called split. cabal install split Use it like this: ghci> splitOn "," "my,comma,separated,list" ["my","comma","separated","list"] It comes with a lot of other functions for splitting on matching delimiters or having several delimiters. * Haskell (n+1) in pattern matching votes: 10 Read on SO: http://stackoverflow.com/questions/4913588/haskell-n1-in-pattern-matching/4… It's a specific case of what is called "n+k patterns", which is generally disliked, and will be has been removed from the language. See here for more information. Here is a good note on n+k patterns, which quotes the following from the Haskell 98 Report (emphasis mine): Matching an n+k pattern (where n is a variable and k is a positive integer ... * Setting upper limit to the input set according to the output function votes: 10 Read on SO: http://stackoverflow.com/questions/4927387/setting-upper-limit-to-the-input… The check fib x < 1000000 in the list comprehension filters away the fib x values that are less than 1000000; but the list comprehension has no way of knowing that greater values of x imply greater value of fib x and hence must continue until all x have been checked. Use takeWhile instead: takeWhile (< 1000000) [ fib x | x <- [0..35]] Top StackOverflow Questions * How does Data.MemoCombinators work? votes: 13, answers: 4 Read on SO: http://stackoverflow.com/questions/4980102/how-does-data-memocombinators-wo… * How to best synchronize game engine and network server in Haskell? votes: 10, answers: 3 Read on SO: http://stackoverflow.com/questions/4973401/how-to-best-synchronize-game-eng… * How to choose right Haskell C type? votes: 9, answers: 1 Read on SO: http://stackoverflow.com/questions/4924994/how-to-choose-right-haskell-c-ty… * How to split a string in Haskell? votes: 9, answers: 5 Read on SO: http://stackoverflow.com/questions/4978578/how-to-split-a-string-in-haskell * Haskell (n+1) in pattern matching votes: 7, answers: 1 Read on SO: http://stackoverflow.com/questions/4913588/haskell-n1-in-pattern-matching About the Haskell Weekly News You can find an html version of this newsletter at: http://bit.ly/h1ICad To help create new editions of this newsletter, please send stories to dstcruz(a)gmail.com. I'm in dire need of finding good "quotes of the week". If you happen to come across any, please don't hesitate to send it along. Until next time, Daniel Santa Cruz References 1. http://haskell.org/ 2. http://mtnviewmark.wordpress.com/2011/02/13/bayhac-2011-wrap-up/ 3. http://article.gmane.org/gmane.comp.lang.haskell.general/18473/match=call+p… 4. http://article.gmane.org/gmane.comp.lang.haskell.general/18474 5. http://article.gmane.org/gmane.comp.lang.haskell.general/18485 6. http://article.gmane.org/gmane.comp.lang.haskell.cafe/86087 7. http://article.gmane.org/gmane.comp.lang.haskell.general/18476 8. http://article.gmane.org/gmane.comp.lang.haskell.general/18475 9. http://article.gmane.org/gmane.comp.lang.haskell.general/18481 10. http://themonadreader.wordpress.com/2011/01/19/call-for-copy-special-poetry… 11. http://article.gmane.org/gmane.comp.lang.haskell.general/18486 12. http://article.gmane.org/gmane.comp.lang.haskell.general/18490 13. http://article.gmane.org/gmane.comp.version-control.darcs.user/25902 14. http://article.gmane.org/gmane.comp.lang.haskell.general/18493 15. http://article.gmane.org/gmane.comp.lang.haskell.libraries/15294 16. http://article.gmane.org/gmane.comp.lang.haskell.general/18501

1 0

open datatypes
by rodrigo.bonifacio 16 Feb '11

16 Feb '11

2 1

How to use http-enumerator with hoauth?
by Jeremy Fitzhardinge 16 Feb '11

16 Feb '11

Hi, I'm trying to use http-enumerator with Twitter's streaming API, which requires OAuth authentication. I was hoping to use the hoauth package for this, but it seems that combining with with http-enumerator is pretty awkward. In principle, it should be straightforward since hoauth defines a HttpClient typeclass, and so I would just need to write an instance for http-enumerator. But in practice it is pretty awkward for a few reasons. One is that both packages define their own Request and Response types - however they are semantically identical, so writing conversion functions is tedious but possible. However, I can't work out how to implement error handling; http-enumerator uses the Control.Failure exception mechanism for returning errors, but I can't work out how to fit that into HttpClient's runClient function. If I use "http" rather than "httpRedirect", I can avoid this to some extent (since http doesn't use Failure HttpException m), but I still can't get it to typecheck. I can get a simple non-streaming instance to typecheck using httpLbs (but again, not httpLbsRedirect): data HttpOAuth = HttpOAuth { } instance O.HttpClient HttpOAuth where runClient c r = (HE.httpLbs . http_cvt_request) r >>= return . cvt where cvt :: HE.Response -> Either String O.Response cvt r@(HE.Response st _ b) | 200 <= st && st < 300 = Right $ http_cvt_response r | otherwise = Left $ "HTTP status" ++ show st However, I can't get the streaming version to type check at all: newtype HttpOAuthStream a m b = HttpOAuthStream { iter :: W.Status -> W.ResponseHeaders -> DE.Iteratee a m b } instance O.HttpClient (HttpOAuthStream a m b) where -- runClient :: (MonadIO m) => c -> Request -> m (Either String Response) runClient c r = liftM cvt $ DE.run $ HE.http (http_cvt_request r) (iter c) cvt :: Show a => Either a HE.Response -> Either String O.Response cvt (Left a) = Left $ show a cvt (Right r) = Right $ http_cvt_response r (Full code below) And since I'm still trying to get my head around enumerators, I may have that aspect of things completely wrong. I haven't even tried running any of this yet, so I don't know if I've made any non-type errors. Am I even barking up the right tree at all? Should I try to be using hoauth this way at all, or should I just hack it up to work within http-enumerator? That seems counter-productive. A general comment: There are many partially functional http packages in hackage. It seems to me that rather than requiring one package be a complete http library, we would get further by allowing different packages to implement different aspects of http, so long as they can all be composed in a reasonable way. At the very least, is it really necessary for hoauth to define its own Request/Response types? Would it be worthwhile trying to define general types which all http packages could use? Is that the goal of Network.Wai? What about the HTTP package? Should I just use that instead? What about Network.Curl? Thanks, J import qualified Data.Enumerator as DE import qualified Data.ByteString.Char8 as C8 import Control.Monad (liftM) import Control.Applicative ((<$>), (<*>), (<|>), empty, pure) import Control.Arrow (first, second, (***)) import qualified Network.OAuth.Consumer as O import qualified Network.OAuth.Http.HttpClient as O import qualified Network.OAuth.Http.Request as O import qualified Network.OAuth.Http.Response as O import qualified Network.HTTP.Enumerator as HE import qualified Network.Wai as W import Data.List (intercalate) import Control.Failure import Control.Exception (SomeException) -- Convert a Network.OAuth.Http.Request into a Network.HTTP.Enumerator.Request -- What. A. Pain. http_cvt_request :: O.Request -> HE.Request http_cvt_request oar = HE.Request method secure host port path query headers body where method = C8.pack . show . O.method $ oar secure = O.ssl oar host = C8.pack . O.host $ oar port = O.port oar path = C8.pack . intercalate "/" $ O.pathComps oar query = packpair <$> (O.toList . O.qString $ oar) headers = (first W.mkCIByteString) . packpair <$> (O.toList . O.reqHeaders $ oar) body = O.reqPayload oar -- Convert a Network.HTTP.Enumerator.Response into a Network.OAuth.Http.Response -- See above. http_cvt_response :: HE.Response -> O.Response http_cvt_response her = O.RspHttp status reason headers payload where status = HE.statusCode her reason = "" -- ? headers = O.fromList $ (unpackpair . first W.ciOriginal) <$> HE.responseHeaders her payload = HE.responseBody her mappair f (a,b) = (f a, f b) packpair = mappair C8.pack unpackpair = mappair C8.unpack newtype HttpOAuthStream a m b = HttpOAuthStream { iter :: W.Status -> W.ResponseHeaders -> DE.Iteratee a m b } instance O.HttpClient (HttpOAuthStream a m b) where -- runClient :: (MonadIO m) => c -> Request -> m (Either String Response) runClient c r = liftM cvt $ DE.run $ HE.http (http_cvt_request r) (iter c) cvt :: Show a => Either a HE.Response -> Either String O.Response cvt (Left a) = Left $ show a cvt (Right r) = Right $ http_cvt_response r data HttpOAuth = HttpOAuth { } instance O.HttpClient HttpOAuth where runClient c r = (HE.httpLbs . http_cvt_request) r >>= return . cvt where cvt :: HE.Response -> Either String O.Response cvt r@(HE.Response st _ b) | 200 <= st && st < 300 = Right $ http_cvt_response r | otherwise = Left $ "HTTP status" ++ show st

4 14

Cabal && license combinations
by Vivian McPhail 16 Feb '11

16 Feb '11

Dear All, There was recently a discussion on haskell-cafe ( http://www.mail-archive.com/haskell-cafe@haskell.org/msg86472.html) about licenses of libraries such as hmatrix and the combination of various different licences. One question was about per-package versus by-file licenses: In Haskell the compilation unit is the module, and the per-file cabal header allows for a license field. It seems then that a package should be the least restrictive combination of all the licenses in all the contained modules. If this has to become a hand-coded fancy function of various GPLx, BSDy, OpenSource, and other licenses then so be it. That is the legal reality. And use of a BSD3 module in hmatrix that does not depend upon GPL'd GSL modules would be acceptable. In short, I argue for a per-file(module) license regime. Vivian

11 15

Alex question
by Mihai Maruseac 16 Feb '11

16 Feb '11

Hi, I want to make Alex to parse a file using states. I wrote a simple basic wrapped .x file but it complaints that it doesn't know the "begin" symbol. As listed here[1], my code does something like this: <0> \/{2} { begin italic } Am I doing something wrong? Should I manage myself the states? Should I use another parser generator? [1]: http://www.haskell.org/alex/doc/html/alex-files.html#startcodes Thanks, -- Mihai

1 2

Unit propagation
by PatrickM 16 Feb '11

16 Feb '11

This is my last part from a project and I need some help with the following function: "If a clause in a propositional formula contains only one literal, then that literal must be true (so that the particular clause can be satisfied). When this happens, we remove the unit clauses (the ones that contain only one literal), all the clauses where the literal appears and also, from the remaining clauses, we delete the negation of the literal (because if P is true, -P will be false). For example, in the formula (P v Q v R) ^ (-P v Q v-R) ^ (P) we have one unit clause (the third clause (P) ). Because this one has to be true for the whole formula to be true we assign True to P and try to find a satisfying assignment for the remaining formula. Finally because -P cannot be true (given the assigned value of P) then the second clause is reduced by eliminating the symbol -P . This simplification results in the revised formula (Q v -R). The resulting simplification can create other unit clauses. For example in the formula (-P v Q) ^ (P) is simplified to (Q) when the unit clause (P) is propagated. This makes (Q) a unit clause which can now also be simplified to give a satisfying assignment to the formula. Your function should apply unit propagation until it can no longer make any further simplifications. Note that if both P and -P are unit clauses then the formula is unsatisfiable. In this case the function" type Atom = String type Literal = (Bool,Atom) type Clause = [Literal] type Formula = [Clause] type Model = [(Atom, Bool)] type Node = (Formula, ([Atom], Model)) ropagateUnits :: Formula -> Formula propagateUnits = filter.something---here I need help Thanks in advance -- View this message in context: http://haskell.1045720.n5.nabble.com/Unit-propagation-tp3384635p3384635.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

2 4

Haskell GUI
by Mihai Maruseac 16 Feb '11

16 Feb '11

Hi, I'd like to start a new project in Haskell, this time using an user interface. Looking at [1] I found that there are several of them listed there. However, the list there is very long. Right now, I am unsure on what is best to use. Can someone give me any hints on which is the most kept-to-date and most supported GUI library? Basically, I want to display some graphs in a dynamic way, reacting to user input, nothing fancy right now. Thanks, -- Mihai

5 6