- Haskell - Haskell.org

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 19 Oct '00

19 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

Mutually recursive structures
by Timothy Docker 17 Oct '00

17 Oct '00

The following problem has been taxing me.... I have a list of pairs that I have parsed from a input file, which represent a hiirarchy, where the first element is the name of the object, and the second is the name of the parent if there is one: type ParseOutput = [(String,Maybe String)] I wish to convert this to a list of "objects", where from each object I can navigate to the parent object (if any), or the children (if any): data Obj = Obj { name::String, parent::(Maybe Obj), children::[Obj] } type Result = [Obj] convert:: ParseOutput -> Result In a language with mutable references, this would be a relatively straightforward. I would just create a dictionary mapping from name to Obj, and then iterate over them, filling in the parents and children where appropriate. odict = {} for (name,parent) in parseOutput: odict[name] = Obj() for (name,parent) in parseOutput: if parent: parent = odict[parent] child = odict[name] child.parent = parent parent.children.append( child ) This gives away my background! How can I do this in Haskell? If I don't have mutable references, I figure that I must need to use laziness in some way, perhaps similar to how I would build an infinite structure. A hint or two would be great. Tim

2 2

Haskell function with String arguments in DLL
by Christian Lescher 17 Oct '00

17 Oct '00

I'm trying to build a DLL with a Haskell function of type String -> String, that should be called from outside (e.g. VBA), but it still doesn't work. I'm afraid I need an example or some kind of 'step by step instruction'. Who can help me? (I use GHC 4.08.1.) Christian

1 0

Haskell puzzle
by Rishiyur S. Nikhil 16 Oct '00

16 Oct '00

In Haskell, is the following transformation always legal? \x->\y->e transforms to \x y->e After answering this question, please scroll down about 75 lines for a follow-up question. What if the two lambda-bound variables are the same? I.e., the lhs is \x->\x->e Please refer to Section 3.3 of the Haskell 98 Report, para 3 (one line para).

1 0