- Haskell-Cafe - Haskell.org

Short-circuiting a fold
by Kurt Hutchinson 05 Apr '07

05 Apr '07

Here's a bit of Thursday afternoon fun. Mission: Define "ssfold," a short-circuiting fold. It evaluates to the "folded value" that first satisfies the given predicate. > ssfold :: ( a -> Bool ) -> ( a -> b -> a ) -> a -> [b] -> a Here are two of mine. Straightforward: > ssfold p f z = head . dropWhile ( not . p ) . scanl f z Monadic: > data Done a b = Done { undone :: a } | NotDone b > instance Monad ( Done a ) where > ( NotDone i ) >>= f = f i > ( Done r ) >>= _ = Done r > return = NotDone > > ssfold p f z = undone . foldM (\ v e -> if p v then Done v else NotDone ( f v e ) ) z I want to see some real creativity here, so pull out all the stops. Kurt

4 3

Parsing unordered parameter list with Parsec
by Will Newton 05 Apr '07

05 Apr '07

Hi all, I'm new to Haskell and trying to do some parsing with Parsec. It's been extremely good so far. I have run into a problem I can't seem to see the solution to though. I hope someone on the list can help me out! I have a command with a parameter list like this: CMD PARAM1 foo PARAM2 100 PARAM3 200 Which is easy enough to parse, but it turns out the grammar is not particularly well defined, and it's considered acceptable to swap parameter order round pretty much arbitrarily. Is there a simple way to handle this? I would like to only allow one of each parameter, some parameters may also be optional. It feels like I might have to write my own combinator to do this but I'm not sure I'm quite ready of that yet! Thanks,

2 1

Tracking characters and a timestamp ?
by Marc Weber 05 Apr '07

05 Apr '07

============= ======================================================= {- This program should read characters from stdin, stop on 's' and print the character along with a timestamp You need ghc-6.6 because of Date.Time. When not using mapM addTimeCode I'll get the lines printed on stdout instantly -} import Data.Time.Clock import Data.Time import Control.Monad handleChar :: Show a => (Char, a) -> IO () handleChar ('s', _) = exitWith (ExitFailure 1) handleChar tuple = print tuple addTimeCode a = liftM ( (,) a) getCurrentTime main = do hSetBuffering stdin NoBuffering hGetContents stdin >>= mapM addTimeCode >>= mapM_ handleChar ============= ====================================================== When running and typing a b c it should print ('a', <timestamp>) ('b', <timestamp>) ('c', <timestamp>) It seems to wait till the end of the infinite list. Why? When using a take 10 I'll get those 10 events after having typed the 10th character. Do I need continuation passing style? Would unsafeInterleaveIO help? The final goal is writing a timetracker which sums up the time you've spent on different wmii tags (= you can think of them beeing different screens ) Marc Weber

4 6

`Expect'-like lazy reading/Parsec matching on TCP sockets
by Scott Bell 05 Apr '07

05 Apr '07

Hello all, I'm writing an application to interact with other applications remotely though TCP sockets (primarily), and in the future with local apps also. So far I have a Parsec parser to match the input that I want to see, which works if the remote connection is particularly speedy - but the final goal is to obtain the following behavior: Match the Parsec parser against the input as soon as a match is available, but fail if the match is unavailable after a timeout value if no further data is available on the socket. The parser will be matching some input pattern such as (string "login:"), for example. What's the best approach to take while leveraging laziness if possible? Thanks, - Scott Bell

2 4

Haskell implementation for .NET with performance results
by Monique Monteiro 05 Apr '07

05 Apr '07

Hi all, does anyone know about any Haskell implementation for .NET platform with published performance results? Thanks in advance, -- __________________________________________________________ Monique Monteiro, MSc MCP .NET Framework 2.0 / SCJP / IBM OOAD http://www.cin.ufpe.br/~mlbm http://thespoke.net/blogs/moniquelouise/default.aspx monique(a)qualiti.com.br +55 81 34198137 Project Manager Recife Microsoft Innovation Center

1 0

Type classes to 'reflect' constructor structure
by Jules Bean 05 Apr '07

05 Apr '07

In the thread 'automatic derivation', Joel Reymont is looking for metaprogramming functionality with which he wants to automatically derive a parser and a pretty printer for his ADT (which is an AST for a minilanguage). I replied showing that a significant amount of the boilerplate could be removed anyway just using haskell's built in ability to process parsers as 'data'. I could completely automate the nullary constructions, but I needed type information for n-ary ones. A bit of poking around with typeclasses showed a proof-of-concept for getting the type-checker to extract that information for us: {-# OPTIONS -fglasgow-exts #-} import Data.Typeable -- Stage 1 is just counting the arguments class CountArgs s where numArgs :: s -> Integer data TestType = Nullary | Unary Int | Binary Int String | OtherBinary String Int instance CountArgs TestType where numArgs x = 0 instance CountArgs (a->TestType) where numArgs x = 1 instance CountArgs (a->b->TestType) where numArgs x = 2 -- *Main> numArgs Nullary -- 0 -- *Main> numArgs Unary -- 1 -- *Main> numArgs Binary -- 2 -- Stage 2 actually lists the types of the arguments -- I'll use a seperate ADT to make the types concrete data ArgTypes = JInt | JStr deriving (Show) class ConcreteType t where makeAT :: t -> ArgTypes instance ConcreteType Int where makeAT _ = JInt instance ConcreteType String where makeAT _ = JStr class DescribeArgs s where descArgs :: s -> [ArgTypes] instance DescribeArgs TestType where descArgs _ = [] instance ConcreteType a => DescribeArgs (a->TestType) where descArgs _ = [makeAT (undefined::a)] instance (ConcreteType a, ConcreteType b) => DescribeArgs (a->b->TestType) where descArgs _ = [makeAT (undefined::a), makeAT (undefined::b)] -- *Main> descArgs Nullary -- [] -- *Main> descArgs Unary -- [JInt] -- *Main> descArgs Binary -- [JInt,JStr] -- *Main> descArgs OtherBinary -- [JStr,JInt] -- Stage 3 is just the Data.Typeable version of the stage 2 class DescribeArgs2 s where descArgs2 :: s -> [TypeRep] instance DescribeArgs2 TestType where descArgs2 _ = [] instance Typeable a => DescribeArgs2 (a->TestType) where descArgs2 _ = [typeOf (undefined::a)] instance (Typeable a, Typeable b) => DescribeArgs2 (a->b->TestType) where descArgs2 _ = [typeOf (undefined::a), typeOf (undefined::b)] -- *Main> descArgs2 Nullary -- [] -- *Main> descArgs2 Unary -- [Int] -- *Main> descArgs2 Binary -- [Int,[Char]] -- *Main> descArgs2 OtherBinary -- [[Char],Int] There are still some things this approach fails on: it can't give you a complete list of all constructors of TestType, for example. (Such a list would necessarily an existential type, like [exists x . DescribeArgs x -> x]). I'm sure my thoughts aren't original. Have other people taken this further into interesting directions? Where is the line beyond which you need 'true' metaprogramming? Jules

1 0

25k lines of ASP to 4.2k lines of Haskell, with considerably more functionality
by Adam Peacock 05 Apr '07

05 Apr '07

Haskell in the real world: http://braintreehemp.com.au/ Source available from: darcs get http://braintreehemp.com.au/www.braintreehemp.com.au-WASH/ The site features: - Written in Haskell, using WASH http://www.informatik.uni-freiburg.de/~thiemann/WASH/ - Shopping basket and checkout - Google Maps - Google Analytics - Google Webmaster tools - Template Haskell for HaskellDB description (describe a table or a field in one line) - GPL, execpt where stated otherwise. - Heavyweight Content Management System (CMS) -- Froogle RSS generator -- Configurable help for each page -- Concept of inventory levels -- Concept of users and permissions -- Naive-user management of products, users, and page content -- XML import tool and wizard for inventory level reconciliation between warehouse and site database CMS screen shots at: http://braintreehemp.com.au/screenshots/index.html Why did I write the site in Haskell? First, I was ask to fix the site that was selling products they didn't have in stock. Once I looked at the source code, 25000 lines of ASP, I reckoned it would be easier to rewrite it in a real language. Second, I couldn't find any commercial sites written in Haskell, and I thought this would be a good chance. The new site has considerably more functionality and is a little over 4200 lines of Haskell. The original site could only display and sell products, without any consideration of whether any were currently in stock. Furthermore, the site content could only be maintained by an expert user. See the old site at http://web.archive.org/web/20060503232646/www.braintreehemp.com.au/retail/ . If anyone wants to have a play with the CMS, email me privately, and I'll give you a nobody login. Adam

2 1

Re: [Haskell-cafe] My Unification Sorrows
by Stefan O'Rear 04 Apr '07

04 Apr '07

I seem to have did an accidental reply-to-sender at first: On Wed, Apr 04, 2007 at 01:37:44PM -0700, Paul Berg wrote: > Ok, so I decided to implement an algorithm to build Strongly Typed Genetic > Programming trees in Haskell, in an effort to learn Haskell, > and I'm way over my head on this unification problem. > > The unification seems to work well, as long as I include the occurs check. > growFullTree returns a lazy list of all possible syntax trees in random > order that are well typed. So, with the occurs check: > > head $ growFullTree 4 TInt 0 [] (mkStdGen 5) > > Gives me a nice, random, well typed tree. So far so good, although > I am wary of the efficiency... perhaps I need some applySubst calls > in there somewhere to keep the constraint list down? > > Anyway now, we comment out the occurs check in the unify function and > do the same thing again. Now we get what appears to be an infinite > constraint! The unify is supposed to be terminating without the occurs > check, so something is very wrong here! > > Worse, now we run: > > head $ growFullTree 5 TInt 0 [] (mkStdGen 7) > > This one never even begins printing! Although it appears the bug is > tail recursive in this case. Other random number seeds will cause it > to blow stack. > > I have gone over and over this code and cannot find the issue due to my > lack of experience with both Haskell and Unification algorithms in general. > > I was hoping someone here could give pointers on where the bug might lie, > eg. > what is my algorithm doing wrong that makes it a mostly, but not completely > correct unification algorithm, as well as give me pointers on how this > code could be > made cleaner and/or more concise, as I'm trying very hard to get my brain > around > this language, and this problem. > > Here's the basic code, which should be fully runnable: The problem is with this type: data Type = TInt | TReal | TVar TVName | Type :-> Type Because it is impossible to observe sharing in Haskell values, we are forced to explore the entire type; but without the occurs check the type can be infinite! In my infinite-types unifier, I used this: data Bin = Sum | Fun | Prod deriving (Eq, Show, Ord) data Zen = ZTup deriving (Eq,Show,Ord) data DictElt = EZen Zen | EBin Bin Type Type deriving (Eq, Show, Ord) type Dict = M.Map Int DictElt Changing to use Paul's set of types: data DictElt = TInt | TReal | TVar | Int :-> Int type Dict = M.Map Int DictElt IE, we use Ints explicitly as pointers. However this representation costs a lot in terms of clarity, since everything must be explicitly indirected through the 'heap'. Also fixtypes was a very old project of mine; were I to do it again I would probably use explicit mutable references: data Tinfo s = TInt | TReal | TVar | Type s :-> Type s type Type s = STRef s (Tinfo s) This may conflict with your method of backtracking tree generation; I haven't read that far in the code yet. Stefan ----- End forwarded message -----

2 4

Re: [Haskell] Fixpoint combinator without recursion
by Stefan Holdermans 04 Apr '07

04 Apr '07

Edsko, (Moved to Haskell Cafe.) > It is well-known that negative datatypes can be used to encode > recursion, without actually explicitly using recursion. As a little > exercise, I set out to define the fixpoint combinator using negative > datatypes. I think the result is kinda cool :) Comments are welcome :) Yeah, it's rather cool. IIRC, this style of encoding of recursion operators is attributed to Morris. Before the advent of equality coercions, GHC typically had problems generating code for these kinds of definitions. Did you test this with a release version? If so, how did you get around the code- generation problem? Is it the NOINLINE pragma that does the trick? Cheers, Stefan

3 6

QuickCheck: Arbitrary for a complex type
by Joel Reymont 04 Apr '07

04 Apr '07

Suppose I have a type describing a statement and that I'm trying to make it an instance of arbitrary. The type looks like this: data Statement = InputDecs [InputDecl] | VarDecs [VarDecl] | ArrayDecs [ArrayDecl] | Compound [Statement] | Assign (VarIdent, Expr) | ArrayAssign (VarIdent, [Expr], Expr) Assuming that other types involved were instances of arbitrary, how do I write arbitrary for Statement? Poking around various bits of source code I think that for a type like the following data Style = StyleValue Expr | Solid | Dashed | Dotted | Dashed2 | Dashed3 deriving Show I can write instance Arbitrary Style where arbitrary = oneOf [ StyleValue . arbitrary, elements [ Solid , Dashed , Dotted , Dashed2 , Dashed3 ] ] I'm not sure if this is correct, though, so any help is appreciated! Thanks in advance, Joel -- http://wagerlabs.com/

3 4