October 2000 - Haskell

cpp superior to ghc . . .
by George Russell 26 Oct '00

26 Oct '00

Why does the Haskell language not allow "type" declarations to appear in the declaration parts of where and let clauses? I've just been writing a huge functions which requires lots and lots of repetitive internal type annotations (to disambiguate some complicated overloading) but I can't abbreviate them with "type" because they depend on things only in scope inside the function. In the end I abbreviated them with a few #define's but I don't really think it should be that way . . .

4 3

Re: Haskell Programming Environment
by senganb＠ia.nsc.com 25 Oct '00

25 Oct '00

> Hello, > > I'm writing my master thesis. Its subject is 'Haskell Programming > Environment'. It is (or rather will be) an extended text editor working i= > n > graphical (XFree86) environment designed for Haskell programmers. It will= > be > implemented using Fudgets library. > I'm wondering what features would you like to find in such environment. W= > hat > should be neccessary, what would help, what would make writing programs > easier, etc. > I have some concepts, but I would like to hear some suggestions from you. > > Thanks for all answers. a) the ablility to highlight an area of code and get its type (be it a function, or some well-formed chunk of code b) the ability to highlight a function and get its definition in another area (think multiple text editing in vim) c) interaction with hugs/stg-hugs so that just written code can be pasted into a "hugs window" for evaluation. d) Debug mode which automatically adds "deriving show" to all datatypes which are not showable/adds exporting of all Datatypes as non-abstract for use in hugs to just allow things to be tried out. e) Debug mode which invisibly replaces functions such as "fromJust" with error making versions (... fromJust' "the file and line at which I'm invoked" ...) to make it easier to find the cause of the error (fromJust Nothing just comes up with an error telling you that it's fromJust that failed. Last time that happened, I hacked hugs to dump the evaluation stack, from which I guessed which possible fromJusts it could have been). f) Use ghc's .hi file to allow strictness of arguments to appear if you leave the mouse over an argument. g) For bonus points (harder, but really useful when stuck): given an expression, show me (possibly using daVinci) how it gets evaluated: Lazyness behaviour is not always obvious, I'd like to see it. I've been wanting to code one of these myself, but have had no time. Try and see if stg-hugs is useable yet since that would be a much better environment to do it in. Sengan

2 1

group theory. Reply
by S.D.Mechveliani 25 Oct '00

25 Oct '00

Hi, all, To Eric Allen Wohlstadter's (wohlstad(a)cs.ucdavis.edu) : Are there any Haskell libraries or programs related to group theory? I am : taking a class and it seems like Haskell would be a good programming : language for exploring/reasoning about group theory. What I had in mind : was perhaps you could have a function which takes a list(set) and a : function with two arguments(binary operator) and checks to see whether or : not it is a group. I think it might be a fun exercies to write myself but : I'd like to see if it's already been done or what you guys think about it. Marc van Dongen <dongen(a)cs.ucc.ie> writes > I think Sergey Mechveliani's docon (algebraic DOmain CONstructor) > has facilities for that. Have a look at: > > http://www.cs.bell-labs.com/who/wadler/realworld/docon.html Sorry, DoCon (<http://www.botik.ru/pub/local/Mechveliani/docon/2.01/>) really supports the Commutative Rings, but provides almost nothing for the Group theory. For example, for the domain (Integer,Integer) it would set automatically (IsGroup,Yes) for the Additive semigroup and (IsGroup,No) for the Multiplicative semigroup. For the additive case, it would also set the group generator list [(1,0),(0,1)]. In both cases, it would also set cardinality = Infinity. Similar attributes are formed for the constructors of Permutation, Vector, Matrix, Polyninomial, Fraction, ResidueRing. And that is all. It does not provide so far any real algorithmic support for the Group theory, except some operations on permutations. But one may develop the program by adding the needed algorithms and introducing new attributes. : What I had in mind : was perhaps you could have a function which takes a list(set) and a : function with two arguments(binary operator) and checks to see whether or : not it is a group. I think it might be a fun exercies to write myself but : I'd like to see if it's already been done or what you guys think about it. I never programmed this. It looks like some exercise in algorithms. There are also books on the combinatorial group theory, maybe, they say something about efficient procedures for this. Regards, ------------------ Sergey Mechveliani mechvel(a)botik.ru

2 1

Re: mapM/concatMapMy
by John Hughes 24 Oct '00

24 Oct '00

Sengan Baring-Gould writes: >Is >>= not lazy? since no experts have answered yet, this newbie will answer. I think it's strict. Well, it depends. (>>=) is an overloaded operator, with a different implementation for every monad -- when you define a monad, you give the implementation of (>>=). If your implementation is strict (presumably in the first operand), then (>>=) is strict *at that type*. If your implementation is lazy, then it isn't. The same goes for (+): at most types (+) is strict, but if you define your own kind of number with a lazy addition, then on that type (+) will be lazy. For many monads, (>>=) *is* strict, which fits with the intuition that it is a `sequencing' operator. But by no means for all. The simplest counter-example is the identity monad: newtype Id a = Id a instance Monad Id where return = Id Id x >>= f = f x where m>>=f is strict in m only if f is a strict function. A more interesting example is the state transformer monad: newtype ST s a = ST (s -> (a,s)) instance Monad (ST s) where return x = ST (\s -> (x,s)) ST h >>= f = ST (\s -> let (a,s') = h s ST h' = f a in h' s') where once again, the implementation of (>>=) is strict only if f is a strict function. Hence `lazy state' makes sense! John Hughes

3 2

LOOKING FOR B-TREES MODULE
by Franck Delaplace 24 Oct '00

24 Oct '00

I am looking for an haskell module which implements balanced trees ? Can somebdody help me Thank you -- Franck Delaplace @w3:http://taillefer.lami.univ-evry.fr:8090/~delapla/ La.M.I-U.M.R C.N.R.S Université d'Evry Val d'Essonne Cours Monseigneur Roméro 91025 Evry CEDEX (France)

1 0

CFP: Eight International Conference on Computer Aided Systems Theory
by Juan J. Quintela 24 Oct '00

24 Oct '00

The following message is a courtesy copy of an article that has been posted to comp.lang.ml,comp.lang.functional as well. Dear Colleagues, I would be most grateful if you would distribute the appended Call For Papers to your colleagues (and/or any mailing lists you see appropriate). Any help in distributing the Call For Papers would be most appreciated. Kindest regards, Juan Quintela CALL FOR PAPERS --------------- Eight International Conference on Computer Aided Systems Theory Formal Methods and Tools for Computer Science See the webpage at: http://azuaje.ulpgc.es/congresos/eurocast2001/ The topics for the workshop are: Workshop "FP" Contributions addressing to the following and similar issues: 1.Concurrency. Distributed and web applications. 2.Verification:tools and methods. 3.Persistence. 4.Typing and theoretical foundations. You only have to send one extended abstract before the: 31 October. -- In theory, practice and theory are the same, but in practice they are different -- Larry McVoy

1 0

mapM/concatMapM
by senganb＠ia.nsc.com 23 Oct '00

23 Oct '00

mapM seems to be a memory hog (and thus also concatMapM). In the following eg: > main = mapM print ([1..102400] :: [Integer]) memory usage climbs to 1.6M with ghc and needs -K20M, whereas with > main = print ([1..102400] :: [Integer]) memory usage is only 1300 bytes. I instrumented mapM: > main = mapM2 (_scc_ "p" (\x -> print x)) ([1..102400] :: [Integer]) > mapM2 :: Monad m => (a -> m b) -> [a] -> m [b] > mapM2 f [] = return [] > mapM2 f (c:cs) = _scc_ "a" (>>=) (_scc_ "d" f c) (\x -> > _scc_ "b" (>>=) (_scc_ "e" mapM2 f cs) (\xs -> > _scc_ "f" return (x:xs))) and found that a and b were the worst heap users (according to hp2ps), ie the two >>='s Why is this so? What can I do about it? My code uses mapM pretty extensively, and I think its suffering from this problem. I notice that ghc does not seem to use mapM except in 2 modules. Another odd thing is that hp2ps says that a & b are the culprits, but the -p and -px options say p is. Why? Sengan

3 5

Re: Passing an environment around
by José Romildo Malaquias 21 Oct '00

21 Oct '00

The following discussion is been conducted in the Clean mailing list. As the issue is pertinent also to Haskell, I have cross-posted this letter to the Haskell mailing list too. Romildo. On Thu, Oct 19, 2000 at 09:08:16AM -0700, Conal Elliott wrote: > Indeed Fran behaviors are like your alternative #1 (function passing), and > hence sharing loss is a concern. Simon PJ is right that I have a paper > discussing this issue and some others. See "Functional Implementations of > Continuous Modeled Animation" on my pubs page > (http://research.microsoft.com/~conal/papers) > > About alternative #2 (implicit arguments), would it help? Does it eliminate > the non-memoized redundant function applications, or just hide them? For > Fran, Erik Meijer suggested implicit functions to me a couple of years ago. > I hadn't thought of it, and it did indeed seem to be attractive at first as > a way to eliminate the need for overloading in Fran. However, the (Time -> > a) representation of Fran behaviors is not really viable, so I wouldn't > merely want to hide that representation behind implicit arguments. It seems that implicit parameters does not eliminate redundant function applications, as Conal Elliott has commented. Reading the paper Implicit Parameters: Dynamic Scoping with Static Types Jefrrey Lewis, Mark Shields, Erik Meijer, John Launchbury http://www.cse.ogi.edu/~jlewis/ (especially section 5.1) I got this impression. I would like to hear from others as well, as I had some difficulties with the paper. > I don't see how alternative #3 would work. > > Of the three approaches, I think #1 is probably the best way to go. > Functional programming encourages us to program with higher-order functions, > and doing so naturally leads to this loss-of-sharing problem. Memoization > is thus a useful tool. Adding it to Clean would probably help others as > well as you. > > > I recommend that you find out how real computer algebra systems address this > issue. I've used these systems some and have the impression that there is a > default set of simplification rules, plus some strategies for non-standard > "simplifications" like factoring. You could apply the default set in a > bottom-up way, with no need for memoization. This is precisely the approach > used for algebraic simplification in Pan (an Haskell-based image synthesis > library). See the recent paper "Compiling Embedded Languages" on my pubs > page. You can also get the Pan source release to check out the real > details. > > Good luck, and please let me know how it turns out. > > - Conal > > -----Original Message----- > From: Simon Peyton-Jones > Sent: Thursday, October 19, 2000 1:51 AM > To: José Romildo Malaquias; clean-list(a)cs.kun.nl > Cc: Conal Elliott (E-mail); Meurig Sage (E-mail) > Subject: RE: [clean-list] Passing an environment around > > It's interesting that *exactly* this issue came up when Conal > Eliott was implementing Fran in Haskell. His 'behaviours' > are very like your expressions. > type Behaviour a = Time -> a > and he found exactly the loss of sharing that you did. > > For some reason, though, I'd never thought of applying the > implicit-parameter > approach to Fran. (Perhaps because Implicit parameters came along after > Fran.) > But I think it's rather a good idea. > > I think Conal may have a paper describing the implementation choices > he explored; I'm copying him. > > Simon > > | -----Original Message----- > | From: José Romildo Malaquias [mailto:romildo@urano.iceb.ufop.br] > | Sent: 18 October 2000 08:12 > | To: clean-list(a)cs.kun.nl > | Subject: [clean-list] Passing an environment around > | > | > | Hello. > | > | I am implementing a Computer Algebra system (CALG) in Clean, > | and I have a > | problem I would like the opinion of Clean programmers. > | > | The CALG system should be able to simplify (or better, to transform) > | algebraic expressions (from Mathematics) involving integers, > | named constants > | (like "pi" and "e"), variables, arithmetic operations (addition, > | multiplication, exponentiation), and other forms of expressions > | (trigonometric, logarithmic, derivatives, integrals, > | equations, etc.). The > | tansformaations should follow the rules from Algebra and > | other areas of > | Mathematica. But we know that in general an algebraic > | expression can be > | transformed in different ways, depending on the goal of the > | transformation. Thus, the algebraic expression > | > | a^2 + b^2 + 3*a*b - a*b > | > | could result in > | > | a^2 + 2*a*b + b^2 > | > | or in > | > | (a + b)^2 > | > | To control the transformations made with an algebraic > | expression there is a > | set of flags collected in a record. I will call this record > | the environment > | in which the expression should be simplified. The algorithms I am > | implementing may change this environment temporarily for some local > | transformations. So the enviroment should be passed around in > | the function > | calls I am writing. This way the functions that implements the > | transformations will have an extra argument representing the > | environment in > | which the transformation is to be performed. > | > | Let's take an example: the algorithm for addition will have > | two arguments to > | be added and a third argument corresponding to the enviroment: > | > | add :: Expr Expr Env -> Expr > | > | and its result will depend of the flags in the environment. > | But it is highly > | desirable to define functions like add as BINARY INFIX > | OPERATORS. Having 3 > | arguments, add cannot be made a binary operator! > | > | -------------------------------------------------------------------- > | So I am looking for alternative ways to pass the environment around. > | -------------------------------------------------------------------- > | > | 1. Handle the arguments as functions themselves, which, given > | an enviroment, > | returns the simplified algebraic expression in that environment: > | > | add :: (Env -> Expr) (Env -> Expr) -> (Env -> Expr) > | > | Now add can be made a binary infix operator. This solution has the > | disadvantage that we loose sharing when doing local > | simplifications. For > | example: > | > | f :: (Env -> Expr) (Env -> Expr) -> (Env -> Expr) > | f fx fy = (add (add fx fy) fy) > | > | fe1, fe2 :: Env -> Exp > | fe1 e = ... > | fe2 e = ... > | > | initialEnv :: Env > | initialEnv = ... > | > | Start = f fe1 fe2 initialEnv > | > | In this program fragment, fe2 may be applied twice to the same > | environment value, computing its body twice. The resulting > | program would > | be too inneficient. If Clean had a mean of implementing MEMOIZATION > | FUNCTIONS, the computation of a memoized function > | application to the same > | argument would evalute the body of the function only the > | first time the > | function is applied. Subsequent applications of that > | function to the same > | argument would remember the result of the previous > | application and would > | reutilize it. Then this way of handling environment > | passing would be a > | good solution. > | > | For more on memo functions see > | <http://www.cse.ogi.edu/~byron/memo/dispose.ps>. > | > | 2. Extend Clean to support IMPLICIT PARAMETER PASSING (that > | is, a form of > | dynamic scoping), as has been done in some Haskell > | implementations (Hugs, > | GHC). Than the environment could be passed implicitly and > | add could be > | considered to have only 2 arguments > | > | add :: (Env ?env) => Exp Exp -> Exp > | > | Here ?env represents an implicit parameter. It is not > | passed explicitly > | like the two argument parameters. It can be used normally > | in the function > | definition, like any normal parameter. To pass an argument > | implicitly, > | there is 2 additional forms of expression: dlet and with: > | > | dlet ?env = ... in add e1 e2 > | > | add e1 e2 with ?env = ... > | > | I think this could be the best solution to my problem, if Clean had > | such extension implemented. > | > | For more information, see > | <http://www.cse.ogi.edu/~jlewis/implicit.pdf.gz> > | > | 3. Join the algebraic expression and the environment in a single value > | > | add :: (Env,Exp) (Env,Exp) -> (Env,Exp) > | > | The enviroment is then carried around with each expression. > | But now add has two enviroments to consult. Which one should be > | used? > | > | Would be other good alternatives to solve this problem? > | > | Would future versions of Clean support > | > | - memoization functions, or > | - implciit parameter passing? > | > | I am open to discussion on this topics. > | > | Regards, > | > | Romildo > | -- > | Prof. José Romildo Malaquias <romildo(a)iceb.ufop.br> > | Departamento de Computação > | Universidade Federal de Ouro Preto > | Brasil > | > | _______________________________________________ > | clean-list mailing list > | clean-list(a)cs.kun.nl > | http://www.cs.kun.nl/mailman/listinfo/clean-list > | > > _______________________________________________ > clean-list mailing list > clean-list(a)cs.kun.nl > http://www.cs.kun.nl/mailman/listinfo/clean-list -- Prof. José Romildo Malaquias <romildo(a)iceb.ufop.br> Departamento de Computação Universidade Federal de Ouro Preto Brasil

1 0

Re: Extensible data types?
by José Romildo Malaquias 20 Oct '00

20 Oct '00

Hello. I am back with the issue of extensible union types. Basically I want to extend a data type with new value constructors. Some members of the list pointed me to the paper "Monad Transformers and Modular Interpreters" Sheng Liang, Paul Hudak and Mark Jones The authors suggest using a type constructor to express the disjoint union of two other types: data Either a b = Left a | Right b which indeed is part of the Haskell 98 Prelude. Then they introduce a subtype relationship using multiparameter type classes: class SubType sub sup where inj :: sub -> sup -- injection prj :: sup -> Maybe sub -- projection The Either data type consructor is then used to express the desired subtype relationshipe: instance SubType a (Either a b) where inj = Left prj (Left x) = Just x prj _ = Nothing instance SubType a b => SubType a (Either c b) where inj = Right . inj prj (Right x) = prj x prj _ = Nothing The authors implemented their system in Gofer, due to restrictions in the type class system of Haskell. But now that there are Haskell extensions to support multiparametric type classes, that could be implemented in Haskell. The above code fails to type check due to instances overlapping. Hugs gives the following error message: ERROR "SubType.hs" (line 10): Overlapping instances for class "SubType" *** This instance : SubType a (Either b c) *** Overlaps with : SubType a (Either a b) *** Common instance : SubType a (Either a b) (I did not check Gofer, but is there a way to solve these overlapping of instances in it?) So this is scheme is not going to work with Haskell (extended with multiparameter type classes). I would like hear any comments from the Haskell comunity on this subject. Is there a workaround for the overlapping instances? Regards. Romildo -- Prof. José Romildo Malaquias <romildo(a)iceb.ufop.br> Departamento de Computação Universidade Federal de Ouro Preto Brasil

4 3

A question regarding haskell mode for Emacs
by Friedrich Dominicus 20 Oct '00

20 Oct '00

I wonder if there are some known troubles. This mode yesterday nearly drive me nuts. Indentation seem to be ok from the layout, but I got complains about block closed to early, missing ; ... Regards Friedrich -- for e-mail reply remove all after .com

1 0