- Haskell - Haskell.org

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

hugs/ghc + shared mem access
by xander 19 Oct '00

19 Oct '00

Hi, I'm exploring my options to connect 2 programs (1 Haskell, 1 non-Haskell). I could connect both programs by 1 or 2 sockets. I was wondering whether it's feasible to access shared memory from within hugs as an alternative? Any answers? Thanks, xander van wiggen

1 0

Num class
by Koen Claessen 18 Oct '00

18 Oct '00

Hi all, For years I have wondered why the Num class has the Eq class and the Show class as super classes. Because of this, I cannot make functions an instance of Num (becuase they are not in Eq or Show). Or a datatype respresenting an infinite amount of digits (because Eq would not make any sense). Now I have found out the reason! However, it does not make me happy, it makes me even more sad. It is of the defaulting mechanism of course! The defaulting mechanism works as follows: If there is an unresolved overloading error on a type variable a, which has as an *only* constraint (Num a), then we take a to be the suitable default. If Show were not a super class of Num, the following program would generate an error: main = print 42 If Eq were not a super class, the following program would not work: main = print (if 42 == 42 then "koe" else "apa") These programs are all fixed by inserting Show and Eq as super classes of Num. So that one does not even notice! Until now. I am interfacing to an external library that uses double-precision floating points internally for all numbers. This is to be as general as possible. However, I know that when I put for example an Integer in, I get one out too. Thus, I want to give a Haskell interface that can deal with this by any numeric type. So I define a type class: class Num a => Number a where convertToDouble :: a -> Double convertFromDouble :: Double -> a (somehow the Haskell numerical hierarchy does not even let me define general functions that do this! -- but that is besides the point.) instance Number Int instance Number Integer instance Number Float instance Number Double ... All my library functions now have the shape: libraryFunction :: Number a => ... a ... Where as actually: primLibraryFunction :: ... Double ... And now the bad thing... When I use "libraryFunction" on a numeric constant, such as 42, I get the error: ERROR "library.hs" (line 8): Unresolved overloading *** Binding : main *** Outstanding context : Number b This is really annoying, and it is not clear why the default mechanism works this way. So here are my questions. Why does the default mechanism have this restriction? I know that the default mechanism is already broken (some desirable properties are destroyed) -- what properties will be broken by lifting this restriction? /Koen. -- Koen Claessen http://www.cs.chalmers.se/~koen phone:+46-31-772 5424 mailto:koen@cs.chalmers.se ----------------------------------------------------- Chalmers University of Technology, Gothenburg, Sweden

3 2

pronunciation of >>=
by Scott Turner 18 Oct '00

18 Oct '00

Is there a common way to pronounce ">>=" in discussions or when teaching? I've learned all my Haskell from printed/visual documents. -- Scott Turner p.turner(a)computer.org http://www.ma.ultranet.com/~pkturner

2 1