March 2009 - Haskell-Cafe

Applicative combinators from Parsec
by Martijn van Steenbergen 13 Mar '09

13 Mar '09

Hello, Looking at Parsec 3 I see: > chainr1 :: (Stream s m t) => ParsecT s u m a -> > ParsecT s u m (a -> a -> a) -> ParsecT s u m a > chainr1 p op = scan where > scan = do x <- p; rest x > rest x = (do f <- op; y <- scan; return (f x y)) <|> return x > But if I remove the type signature and let GHC infer it for me, I get a much more generic type: > chainr1 :: (Alternative m, Monad m) => m a -> m (a -> a -> a) -> m a But we don't really need m to be a monad since we're only doing applicative operations, so after some rewriting we get: > chainr1 :: Alternative f => f a -> f (a -> a -> a) -> f a > chainr1 p op = scan where > scan = flip id <$> p <*> rest > rest = (flip <$> op <*> scan) <|> pure id Would it be a good idea to: 1) make the Parsec combinators as generic as possible and 2) move the really generic applicative ones to Control.Applicative? Thanks, Martijn.

3 2

Re: [Haskell-cafe] Natural Numbers: Best implementation?
by Brandon S. Allbery KF8NH 13 Mar '09

13 Mar '09

On 2009 Mar 12, at 22:54, Mark Spezzano wrote: > I was wondering what the best way to implement Natural number would > be. Is there a package which already does this? type-level on Hackage. > 2. Use the type > data Natural = Zero | Succ !Natural One of the reasons people use type-level naturals is to get laziness; you've made this strict. Is there a reason? -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allbery(a)kf8nh.com system administrator [openafs,heimdal,too many hats] allbery(a)ece.cmu.edu electrical and computer engineering, carnegie mellon university KF8NH

2 2

Re: [Haskell-cafe] ANNOUNCE: Vintage BASIC 1.0
by Lyle Kopnicky 13 Mar '09

13 Mar '09

On Fri, Mar 13, 2009 at 1:31 AM, Wolfgang Jeltsch < jeltsch(a)informatik.tu-cottbus.de> wrote: > When running the executable, nothing happens. The executable should show a > usage message instead. Where are the BASIC programs? I think, you have to > grab them from the source. They should be installed, too. > Thanks for your feedback, and for checking out Vintage BASIC! I will add a usage message, as you suggested. Currently the usage is only described in the User's Guide. There are no options; you just give it the name of one or more BASIC source files. (Naturally this extends to doing nothing when supplied with zero source files.) The BASIC games are at http://www.vintage-basic.net/games.html. There is a tarball of all the games (bcg.tar.gz<http://www.vintage-basic.net/downloads/bcg.tar.gz>) as well. These are separated from the Vintage BASIC distribution for legal reasons. Vintage BASIC is copyrighted by me under a BSD license. The games were written by many authors and compiled into a book copyrighted by Creative Computing. I have secured permission from the editor to post the games. I do not wish to imply that they are covered by the same license as the interpreter. If anyone has any suggestions as to how to make the process simpler, I'd be happy to hear it. Thanks, Lyle P.S. I need to get my other e-mail account subscribed to this list....

1 0

Sugestion for a Haskell mascot
by Maurício 13 Mar '09

13 Mar '09

Hi, Here in Brazil we have a forest animal we name 'preguiça' -- literally, lazyness. What better mascot we could have for Haskell? It lives (and sleeps) in trees, and if you see the main picture in wikipedia articles you can easily imagine the tree branch beeing replaced by a lambda: http://en.wikipedia.org/wiki/Sloth http://pt.wikipedia.org/wiki/Bicho-pregui%C3%A7a Best, Maurício

26 33

Against cuteness
by Gregg Reynolds 13 Mar '09

13 Mar '09

Regarding logos/mascots: nothing personal folks, but I would like to cast a loud firm vote against all forms of cuteness, especially small furry animal cuteness. It's been done half to death, and we are not O'Reilly. Of all the billions of images from all the cultures in the world available to us we can surely find something that is witty or charming without being cute. -g

9 15

Re: [Haskell-cafe] DSLs with {in,}equalities
by Alberto G. Corona 13 Mar '09

13 Mar '09

even at the level of expressions you can be sure that inequalities hold. So you can create an instance of Ord. for example: (Sum x z) < y | x== y && z>0 = True | .... here x and y can be expressions and == can have its own rules with this you can compute symbolically, because you don´t need to reduce the expression to a numerical value. It´s a matter of finding rules. 2009/3/13 Alberto G. Corona <agocorona(a)gmail.com> > >(<) :: (Ord a) => a -> a -> Bool > > what´s the problem? > > make your Expr an instance of Ord. > > By the way > > > instance Num Expr where > > fromInterger = Const > > (+) = Plus > > (*) = Times > > does not work. you have not defined (+) and (*) for Const Integer. > > (+) (Const a) (Const b)= Const (a+b) > > With this you have an evaluator. > > In the same way: > > (Const a) < (Const b) = Const (a < b) > > > > > 2009/3/12 Adam Vogt <vogt.adam(a)gmail.com> > > This seems to be in ghc for those reasons: >> http://www.haskell.org/haskellwiki/Quasiquotation >> >> * On Monday, March 02 2009, Andrew Hunter wrote: >> >> >Several times now I've had to define an EDSL for working with >> >(vaguely) numeric expressions. For stuff like 2*X+Y, this is easy, >> >looking pretty much like: >> > >> >> data Expr = Const Integer | Plus Expr Expr | Times Expr Expr >> >> >> >> instance Num Expr where >> >> fromInterger = Const >> >> (+) = Plus >> >> (*) = Times >> > >> >&c. This lets me get a perfectly nice AST, which is what I want. >> >When I want to be able to express and work with inequalities and >> >equalities, this breaks. Suppose I want to write 2*X + Y < 3. I >> >either have to: >> > >> >a) Hide Prelude.(<) and define a simple < that builds the AST term I >> want. >> >b) Come up with a new symbol for it that doesn't look totally awful. >> > >> >Neither of these work decently well. Hiding Eq and Ord operators, >> >which is what I effectively have to do for a), is pretty much a >> >nonstarter--we'll have to use them too much for that to be practical. >> > >> >On the other hand, b) works...but is about as ugly as it gets. We >> >have lots and lots of symbols that are already taken for important >> >purposes that are syntactically "near" <,<=,==, and the like: << and >> >>> and >>= for monads, >>> for arrows, etc. There...are not good >> >choices that I know of for the symbols that don't defeat the purpose >> >of making a nice clean EDSL for expressions; I might as well use 3*X + >> >Y `lessthan` 3, which is just not cool. >> > >> >Does anyone know of a good solution, here? Are there good >> >substitutions for all the six operators that are important >> >(<,>,>=,<=,==,/=), that are close enough to be pretty-looking but not >> >used for other important modules? >> > >> >Better yet, though a little harder, is there a nice type trick I'm not >> >thinking of? This works for Num methods but not for Ord methods >> >because: >> > >> >(+) :: (Num a) => a -> a -> a >> >(<) :: (Ord a) => a -> a -> Bool >> > >> >i.e. the return type of comparisons is totally fixed. I don't suppose >> >there's a good way to...well, I don't know what the *right* answer is, >> >but maybe define a new typeclass with a more flexible type for < that >> >lets both standard types return Bool and my expressions return Expr? >> >Any good solution would be appreciated. >> > >> >Thanks, >> >AHH >> >_______________________________________________ >> >Haskell-Cafe mailing list >> >Haskell-Cafe(a)haskell.org >> >http://www.haskell.org/mailman/listinfo/haskell-cafe >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe(a)haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > >

1 0

Fwd: [Haskell-cafe] DSLs with {in,}equalities
by Alberto G. Corona 13 Mar '09

13 Mar '09

---------- Forwarded message ---------- From: Alberto G. Corona <agocorona(a)gmail.com> Date: 2009/3/13 Subject: Re: [Haskell-cafe] DSLs with {in,}equalities To: Adam Vogt <vogt.adam(a)gmail.com> You need an expression evaluator: with (+) (Const a) (Const b)= Const (a+b) (*) (Const a) (Const b)= Const (a*b) eval :: Exp -> Integer eval (Const i)= i eval ( Plus e1 e2)= eval e1 + eval e2 .. eval( Mul .... and instance Ord Expr where (<) expr1 expr2 = eval expr1 < eval expr2 by the way: simplify expr= Const (eval expr) ...................................... 2009/3/13 Alberto G. Corona <agocorona(a)gmail.com> > Sorry(Const a) < (Const b) = a < b > > also > > (*) (Const a) (Const b)= Const (a*b) > > > 2009/3/13 Alberto G. Corona <agocorona(a)gmail.com> > > >(<) :: (Ord a) => a -> a -> Bool >> >> what´s the problem? >> >> make your Expr an instance of Ord. >> >> By the way >> >> > instance Num Expr where >> > fromInterger = Const >> > (+) = Plus >> > (*) = Times >> >> does not work. you have not defined (+) and (*) for Const Integer. >> >> (+) (Const a) (Const b)= Const (a+b) >> >> With this you have an evaluator. >> >> In the same way: >> >> (Const a) < (Const b) = Const (a < b) >> >> >> >> >> 2009/3/12 Adam Vogt <vogt.adam(a)gmail.com> >> >> This seems to be in ghc for those reasons: >>> http://www.haskell.org/haskellwiki/Quasiquotation >>> >>> * On Monday, March 02 2009, Andrew Hunter wrote: >>> >>> >Several times now I've had to define an EDSL for working with >>> >(vaguely) numeric expressions. For stuff like 2*X+Y, this is easy, >>> >looking pretty much like: >>> > >>> >> data Expr = Const Integer | Plus Expr Expr | Times Expr Expr >>> >> >>> >> instance Num Expr where >>> >> fromInterger = Const >>> >> (+) = Plus >>> >> (*) = Times >>> > >>> >&c. This lets me get a perfectly nice AST, which is what I want. >>> >When I want to be able to express and work with inequalities and >>> >equalities, this breaks. Suppose I want to write 2*X + Y < 3. I >>> >either have to: >>> > >>> >a) Hide Prelude.(<) and define a simple < that builds the AST term I >>> want. >>> >b) Come up with a new symbol for it that doesn't look totally awful. >>> > >>> >Neither of these work decently well. Hiding Eq and Ord operators, >>> >which is what I effectively have to do for a), is pretty much a >>> >nonstarter--we'll have to use them too much for that to be practical. >>> > >>> >On the other hand, b) works...but is about as ugly as it gets. We >>> >have lots and lots of symbols that are already taken for important >>> >purposes that are syntactically "near" <,<=,==, and the like: << and >>> >>> and >>= for monads, >>> for arrows, etc. There...are not good >>> >choices that I know of for the symbols that don't defeat the purpose >>> >of making a nice clean EDSL for expressions; I might as well use 3*X + >>> >Y `lessthan` 3, which is just not cool. >>> > >>> >Does anyone know of a good solution, here? Are there good >>> >substitutions for all the six operators that are important >>> >(<,>,>=,<=,==,/=), that are close enough to be pretty-looking but not >>> >used for other important modules? >>> > >>> >Better yet, though a little harder, is there a nice type trick I'm not >>> >thinking of? This works for Num methods but not for Ord methods >>> >because: >>> > >>> >(+) :: (Num a) => a -> a -> a >>> >(<) :: (Ord a) => a -> a -> Bool >>> > >>> >i.e. the return type of comparisons is totally fixed. I don't suppose >>> >there's a good way to...well, I don't know what the *right* answer is, >>> >but maybe define a new typeclass with a more flexible type for < that >>> >lets both standard types return Bool and my expressions return Expr? >>> >Any good solution would be appreciated. >>> > >>> >Thanks, >>> >AHH >>> >_______________________________________________ >>> >Haskell-Cafe mailing list >>> >Haskell-Cafe(a)haskell.org >>> >http://www.haskell.org/mailman/listinfo/haskell-cafe >>> _______________________________________________ >>> Haskell-Cafe mailing list >>> Haskell-Cafe(a)haskell.org >>> http://www.haskell.org/mailman/listinfo/haskell-cafe >>> >> >> >

1 0

Typing Dynamic Typing [Was: Dynamically typing TH.Exp at runtime]
by oleg＠okmij.org 13 Mar '09

13 Mar '09

Martin Hofmann asked: > Is there a Haskell implementation of the paper "Typing Dynamic Typing" > by Baars and Swierstra There is a different implementation but in the same spirit http://okmij.org/ftp/tagless-final/IncopeTypecheck.hs http://okmij.org/ftp/Computation/tagless-typed.html#tc-final The first difference between IncopeTypecheck and Baars and Swierstra's one is in the type representation and safe coercions. IncopeTypecheck uses Typeable, and so it needs to define reflection from a type rep to a value of that type. The projection function of Typeable requires a value of a specific type rather than a typerep. The main difference is treating environments and weakening. Baars and Swierstra treat an Identifier, at compile time, as a projection function \env->t. Here env is the run-time env represented as a nested tuple. `Closing the Stage' paper relies on the same idea. To be able to collect those projection functions into a regular list, they wrap them into a Dynamic. IncopeTypecheck, in contrast, represents compile-time variables as functions \x->x, which are weakened as they are embedded into a reacher environment. The functions are wrapped into Dynamic, as this is the result of typechecking. The type environment Gamma in IncopeTypecheck contains only TypeRep but no Dynamics! Here a few examples to illustrate the difference between Baars and Swierstra and IncopeTypecheck: Source expression: Add (Int 2) (Int 3) Baars and Swierstra: \env -> (\_ -> 2) env + (_ -> 3) env IncopeTypecheck: add (int 1) (int 2) Source expression: (Lam "x" Int (x + (Int 1))) Baars and Swierstra: \env -> \x -> (\env -> (\(x,_) ->x) env + (\_ -> 1) env) (x,env) IncopeTypecheck: \x -> (\x -> x) x `add` (\_ -> int 1) x (of course, in IncopeTypecheck, instead of (\x -> ...) there should be lam (\x -> ...) and instead of meta-language application there should be app. I drop them for clarity). For deeply nested functions, IncopeTypecheck probably has to do more redices as it repeatedly applies coercions. Since the environment is known, I could have built the weakening in one step rather than as a sequence of weakening into a progressively richer environment. Each step into this sequence includes an administrative redex. The sequential weakening was easier to implement though.

2 1

Re: [Haskell-cafe] Natural Numbers: Best implementation?
by Sebastian Fischer 13 Mar '09

13 Mar '09

Hi Mark, On Mar 13, 2009, at 3:54 AM, Mark Spezzano wrote: > I was wondering what the best way to implement Natural number would > be. Is there a package which already does this? there are two packages on Hackage that implement natural numbers using algebraic datatypes: 'numbers' has a module Data.Number.Natural that implements them in "unary" notation (zero and successor), 'nat' has Data.Number.Nat that uses a binary encoding. Cheers, Sebastian

1 0

Combining haddock documentation from multiple packages
by Heikki Aitakangas 13 Mar '09

13 Mar '09

Is it possible to generate a "unified" documentation tree similar to http://www.haskell.org/ghc/docs/latest/html/libraries/index.html from packages installed via cabal from hackage? And if so, how does one go about doing it? -- Heikki Aitakangas

2 1