- Haskell-Cafe - Haskell.org

Re: "listProduct" -- is this a standard function?
by K. Fritz Ruehr 17 Oct '03

17 Oct '03

I don't know of a type-based search tool for Haskell libraries, but I vaguely recall someone pursuing this idea using type isomorphisms to provide more robust results. This actually came up at lunch the other day*, where someone pointed out that you'd want to allow not only for type isomorphisms (e.g., argument order), but also for functions which might fit your spec. when instantiated with (say) some default argument. I don't know if this latter idea was addressed in any of the "TI" work, eg Di Cosmo's book (see also Rittri, Thatte, and others). Note that much of the TI work mentions library search as a motivation--I thought that someone might actually have implemented something for Haskell, though. In any case, and until someone might fill in my vaque recall, my students have found the reference tool at zvon.org quite helpful: there is a type-based index of the standard libraries at: <http://zvon.org/other/haskell/Outputglobal/index.html> (but note that the class qualifiers are missing, so that sequence looks more general than it really is). They also have nice indices tied to the library structure, e.g., the Prelude index at: <http://zvon.org/other/haskell/Outputprelude/index.html> -- Fritz * Type isomorphisms don't often come up over lunch in my regular venue, but I am fortunate enough to be spending some sabbatical time with the PacSoft group at the Oregon Graduate Institute (highly recommended). PS: A quick googling suggests that perhaps I was remembering a paper by Rittri in JFP vol. 1, #1, which I don't have handy. Does anyone know if a practical tool was ever released? ----------------- Graham Klyne wrote: > At 22:04 15/10/03 -0500, Matt Harden wrote: >>On Wednesday 15 October 2003 11:07 am, Graham Klyne wrote: >> > I've constructed a "listProduct" function that I think I've seen >> somewhere >> > else... is it a standard function? If so, where is it defined? >> >>Yes. It's called "sequence". It's defined in the prelude. >>It works with arbitrary monads, not just lists. > > That's the one, thanks (both of you). > > I *thought* I'd seen this function before. > > I observe this seems to be a recurring problem for me... there are so many > very generic and useful data handling functions in Haskell, it's difficult > for a jobbing programmer (as opposed to a language expert) to be on top of > them all. And the very generic nature of these function means that it's > not so easy to index them (e.g. in the way that the Java Developers > Almanac > series does for Java). > > Am I overlooking any important developer resources? > > #g > > > ------------ > Graham Klyne > For email: > http://www.ninebynine.org/#Contact

1 0

parsing a file line by line
by Anagha 16 Oct '03

16 Oct '03

Hi , I am a new bie to haskell. I need to read a file and get it contents line by line and then eventually word by word. I have written the code to read a file , but the returned value is all the lines in the file. How do I parse this whole text message ( contents of the file) into individual lines ( that is parsing / splitting the whole text to get me one line at a time. Also once I get the individual line, I o parse it word by word. I have a start on this thing. by using the line function in haskell, but I have not managed to write it successfully. Can anyone help me in this. Below is the code to read a file. fileFun :: IO () fileFun = do putStr "Please input a file name: " fname <- getLine contents <- readFile fname How do I split the data returned in contents( Contents contains all the text in the file, which is given as input) Thanks Anagha

2 1

Cgi Library
by Mark Espinoza 16 Oct '03

16 Oct '03

Hello, I have ghc 5 and 6 installed on my redhat 7.3 system. I have downloaded and unpacked the cgi library, which wants to have hugs installed. Is there an easy way to make this work with ghc (including the examples, I think I'll need them), or should I just try to install hugs. Thank you. Sincerely, Mark

3 2

Efficient Matrix Library
by Shawn P. Garbett 15 Oct '03

15 Oct '03

I'm looking for an efficient matrix library for Haskell. Suggestions? Shawn

1 0

Proper Etiquette
by Mark Espinoza 15 Oct '03

15 Oct '03

Hello: A couple of days ago I posted a question about the cgi library, which was not answered. What are appropriate courses of action for me in a case like this? Thanks. Mark

3 2

fold{l|r} and short-circuit evaluation
by Graham Klyne 15 Oct '03

15 Oct '03

I'm trying to use foldl or foldr to run a computation over a list, in such a way that only as much of the list as may be needed is actually examined. I believe the 'and' function behaves like this (e.g. see testand below), but when I use a function that performs pairwise operations on the list elementsa, it seems that I always end up constructing the entire list, even if I don't need to examine the value of each element. I guess I could try and figure out my own 2-place folding function, but this seems as if there should be a common solution. My test code is below. The tests are evaluated as: test allSame1 or test allSame2 to use a foldl- or foldr-versions of the function respectively If I comment out the indefinitely long list case (test7) in the definition of 'test', the foldl version will pass all these test cases and foldr throws an error on test6. But if I include test7, using Hugs the foldr test case returns a C stack overflow, and the foldl case silently disappears. Is there a standard method for dealing with cases like this? (I ask out of curiosity rather than need: for my real application, I am using relatively short list with quite expensive combining operations, so I think the 'foldl' variant which doesn't actually examine list elements once the result is known, will work quite well for me.) #g -- -- Spike-allsame.hs -- -- Test use of folding functions to evaluate whether all members -- of a list are the same. -- -- What I'm really interested in is whether the list gets evaluated -- beyond what is needed to obtain the desired result. -- import Maybe ( Maybe(..), isJust ) test allSame = and [ test1 allSame , test2 allSame , test3 allSame , test4 allSame , test5 allSame , test6 allSame , test7 allSame ] test1 allSame = allSame [1,1,1,1] == True test2 allSame = allSame [1,2,3,4] == False test3 allSame = allSame [1,2,undefined,4] == False test4 allSame = allSame [1] == True test5 allSame = allSame [] == True test6 allSame = allSame [1,2,undefined] == False test7 allSame = allSame (1:2:repeat 3) == False testand = and (True:True:False:repeat True) longList :: [Int] longList = (1:2:repeat 3) allSame1 :: (Eq a) => [a] -> Bool allSame1 [] = True allSame1 [_] = True allSame1 (a:as) = isJust $ foldr nextSame1 (Just a) as nextSame1 :: (Eq a) => a -> Maybe a -> Maybe a nextSame1 _ Nothing = Nothing nextSame1 a1 (Just a) | a1 == a = Just a | otherwise = Nothing {- foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) foldr nextSame (Just 1) [2,undefined,4] ..> nextSame 2 (foldr nextSame (Just 1) [undefined,4]) ..> nextSame 2 (nextSame undefined (foldr nextSame (Just 1) [4])) ..> nextSame 2 (nextSame undefined (nextSame 4 (foldr nextSame (Just 1) []))) ..> nextSame 2 (nextSame undefined (nextSame 4 ((Just 1)))) -} allSame2 :: (Eq a) => [a] -> Bool allSame2 [] = True allSame2 [_] = True allSame2 (a:as) = isJust $ foldl nextSame2 (Just a) as nextSame2 :: (Eq a) => Maybe a -> a -> Maybe a nextSame2 Nothing _ = Nothing nextSame2 (Just a) a1 | a1 == a = Just a | otherwise = Nothing {- foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs foldl nextSame (Just 1) [2,undefined,4] ..> foldl nextSame (nextSame (Just 1) 2) [undefined,4] ..> foldl nextSame (nextSame (nextSame (Just 1) 2) undefined) [4] ..> foldl nextSame (nextSame (nextSame (nextSame (Just 1) 2) undefined) 4) [] ..> (nextSame (nextSame (nextSame (Just 1) 2) undefined) 4) -} ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 5

Using field selectors in a type constructor
by Graham Klyne 15 Oct '03

15 Oct '03

I've run across a minor coding niggle on a couple opf accosions when using a type constructor with field selectors. The full code of my test case is below. The value 'test2' evaluates to True. The function that niggles me is this: [[ joinVarBindings :: (Eq a) => VarBinding a b -> VarBinding a b -> VarBinding a b joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = mv12 , vbEnum = map (\v -> (v,fromJust (mv12 v))) $ boundVars vb1 `union` boundVars vb2 , vbNull = False } where mv12 = headOrNothing . filter isJust . flist [ vbMap vb1, vbMap vb2 ] ]] Is it really necessary to define mv12 as a separate "where" clause here? What I'd really like to do is assign it to field vbMap, and reference that from the definition of vbEnum, but I can't figure out if there's a way to do so. Writing this: [[ joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = head . filter isJust . flist [ vbMap vb1, vbMap vb2 ] , vbEnum = map (\v -> (v,fromJust (vbMap v))) $ -- error here ^^^^^^^ boundVars vb1 `union` boundVars vb2 , vbNull = False } ]] Results in a fairly obvious type error: I'd need to have a way to say that vbMap is applied to the value under construction. Experience with Java would suggest maybe something like this: [[ , vbEnum = map (\v -> (v,fromJust (vbMap this v))) $ ]] but of course Haskell isn't Java. Does Haskell provide a way to do this, other than the use of a 'where' clause to factor out the common subexpression, as in my working code? #g -- -- spike-constructorfields.hs import Maybe ( isJust, fromJust ) import List ( union, find ) -- |VarBinding is the type of an arbitrary variable bindings -- value, where the type of the bound values is not specified. data VarBinding a b = VarBinding { vbMap :: a -> Maybe b , vbEnum :: [(a,b)] , vbNull :: Bool } -- |nullVarBinding: maps no query variables. nullVarBinding :: VarBinding a b nullVarBinding = VarBinding { vbMap = const Nothing , vbEnum = [] , vbNull = True } -- |Return a list of the variables bound by a supplied variable binding boundVars :: VarBinding a b -> [a] boundVars = map fst . vbEnum -- |Join a pair of query bindings, returning a new binding that -- maps all variables recognized by either of the input bindings. -- If the bindings should overlap, such overlap is not detected and -- the value from the first binding provided is used arbitrarily. joinVarBindings :: (Eq a) => VarBinding a b -> VarBinding a b -> VarBinding a b joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = mv12 , vbEnum = map (\v -> (v,fromJust (mv12 v))) $ boundVars vb1 `union` boundVars vb2 , vbNull = False } where mv12 = headOrNothing . filter isJust . flist [ vbMap vb1, vbMap vb2 ] flist fs a = map ($ a) fs -- see also monad function 'ap' headOrNothing :: [Maybe a] -> Maybe a headOrNothing [] = Nothing headOrNothing (a:_) = a {- NOT this: -- |Join a pair of query bindings, returning a new binding that -- maps all variables recognized by either of the input bindings. -- If the bindings should overlap, such overlap is not detected and -- the value from the first binding provided is used arbitrarily. joinVarBindings :: (Eq a) => VarBinding a b -> VarBinding a b -> VarBinding a b joinVarBindings vb1 vb2 | vbNull vb1 = vb2 | vbNull vb2 = vb1 | otherwise = VarBinding { vbMap = head . filter isJust . flist [ vbMap vb1, vbMap vb2 ] , vbEnum = map (\v -> (v,fromJust (vbMap v))) $ boundVars vb1 `union` boundVars vb2 , vbNull = False } -} -- |Function to make a variable binding from a list of -- pairs of variable and corresponding assigned value. makeVarBinding :: (Eq a, Show a, Eq b, Show b) => [(a,b)] -> VarBinding a b makeVarBinding vrbs = if null vrbs then nullVarBinding else VarBinding { vbMap = selectFrom vrbs , vbEnum = vrbs , vbNull = null vrbs } where -- selectFrom bs is the VarBinding lookup function selectFrom :: (Eq a) => [(a,b)] -> a -> Maybe b selectFrom [] _ = Nothing selectFrom ((v,r):bs) l = if l == v then Just r else selectFrom bs l vb1 :: VarBinding Int String vb1 = makeVarBinding [(1,"a"),(2,"b"),(3,"c")] vb2 :: VarBinding Int String vb2 = makeVarBinding [(3,"cc"),(4,"dd"),(5,"ee")] vb12 = joinVarBindings vb1 vb2 test1 = vbEnum $ vb12 test2 = test1 == [(1,"a"),(2,"b"),(3,"c"),(4,"dd"),(5,"ee")] test3 = [test31,test32,test33,test34] test31 = vbMap vb12 1 -- Just "a" test32 = vbMap vb12 3 -- Just "c" test33 = vbMap vb12 5 -- Just "ee" test34 = vbMap vb12 0 -- Nothing ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

4 4

putStr
by Jose Morais 14 Oct '03

14 Oct '03

Hi, I am trying to something like f1 :: Int -> Int f1 x = f2 x f2 :: Int -> Int f2 x = 2 * x but before f2 returns its result I'd like it to print something like "The initial value is " ++ show x. How could I do this? Thank you

5 6

RE: Using existential types
by oleg＠pobox.com 14 Oct '03

14 Oct '03

Tim Docker wrote: > I wish to define a flexible report, consisting of a set of columns. > The contents of each column can be defined by mapping a function to a > row descriptor, generating a value, and then converting each value > to a string. I also wish to present an aggregate value at the bottom > of the column defined by another function. > It seems that existential types are required to get this sort of > thing to work. Is there another way? It seems there is. Here's your code: > data ColDesc rowv = forall a. ColDesc (rowv -> a) ([a] -> a) (a -> > String) > calculate :: [rowv] -> ColDesc rowv -> ([String],String) > calculate rs (ColDesc valf sumf fmtf) = let vals = map valf rs in (map > fmtf vals, (fmtf.sumf) vals) Here's the new code: > data ColDesc rowv = ColDesc (rowv -> String) ([rowv] -> String) > calculate :: [rowv] -> ColDesc rowv -> ([String],String) > calculate rs (ColDesc fmtf sumf) = (map fmtf rs, sumf rs) > rows = ["I","wish","to","define","a","report"] > mapp g f = g . (map f) > cols = [ > ColDesc (id.id) $ id.(\_ -> ""), > ColDesc (show.length) $ show.(mapp sum length), > let valf = (\s -> length s * length s) in ColDesc (show.valf) $ show.(mapp maximum valf) > ] > values = [ calculate rows col | col <- cols ] It was derived with a simple transformation: composing (rowv -> a) with (a->String) to eliminate the existential type a. It seems there is a pattern here. When we write data Foo a b = forall ex. Foo <something1> <something2> <something3> with ex unconstrained, then one of <something> must be a function F(a,b) -> ex and another something is a function ex -> G(a,b). Here F(a,b) is some expression that includes ground types, a, b -- but not ex. Indeed, otherwise we have no way to convert something into ex and to get anything out. The third something is perhaps a transformer ex -> H(a,b) -> ex. It seems therefore we are guaranteed that there is always a composition of <something>s that does not include ex. Therefore, instead of carrying original <something>, we can carry the compositions, and get rid of the existential quantification. It seems that (g.f) :: i -> o is equivalent to stating exists c. f:: (i->c) ^ g::(c->o) or, in the Haskell type language data P i o = forall c. P (i->c) (c->o) P f g I also have a nagging feeling that this approach relates to Skolemization. Indeed, Mike Gunter's transformation from > data Stat i o = -- aggregate function taking i's on input and producing o > forall s. Stat > s -- init > (s -> i -> s) -- update > (s -> o) -- result to > data Stat i o = Stat { update :: i -> Stat i o > , result :: o } looks awfully like a Skolemization, with 'Stat i o' being the Skolem function.

4 8

putStr
by Jose Morais 13 Oct '03

13 Oct '03

Hi, What I needed was actualy something more like f3 :: Int -> String f3 x = show x ++ f4 x f4 :: Int -> IO String f4 x = do putStr ("initial value is " ++ show x) return (show x) but this gives the error Type checking ERROR "teste.hs":11 - Type error in application *** Expression : show x ++ f4 x *** Term : f4 x *** Type : IO String *** Does not match : [a] Can you help me? Thank you

2 1

Re: AW: Using existential types
by Graham Klyne 13 Oct '03

13 Oct '03

At 11:25 10/10/03 +0200, Markus.Schnell(a)infineon.com wrote: >Hi Graham, > > > Instead, I replace the class instances by a single algebraic > > data type, > > whose members are functions corresponding to OO-style class methods. > >could you give an example? The code in a previous message of mine [1] was an example of sorts, though complicated by some other issues. Look for type 'DatatypeVal'. [1] http://haskell.org/pipermail/haskell-cafe/2003-October/005231.html A simpler example might be: Consider a class of values called shape, for which the following operations are defined: draw :: Shape -> Canvas -> Canvas flip :: Shape -> Shape move :: Shape -> Displacement -> Shape etc. One can imagine defining a Haskell type class with these methods, but then you get the type mixing problem noted previously. What I have found can work in situations like this is to define a type, thus: data Shape = Shape { draw :: Canvas -> Canvas , flip :: Shape , move :: Displacement -> Shape etc } then one would also need methods to create different kinds of shape, e.g.: makeSquare :: Point -> Displacement -> Shape makeCircle :: Point -> Length -> Shape etc. (Assuming appropriate type definitions for Point, Displacement, Length, etc.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact

1 0

RE: Using existential types
by Tim Docker 13 Oct '03

13 Oct '03

oleg wrote: > Sorry I didn't know of that requirement. The desired sharing > can easily be introduced: That's always a risk with posting a toy example - which bits are important can be hard to tell. You are right of course about being able to introduce the sharing. FWIW, after the suggestions that I've had (thanks!), my "existential-free" example is as below. Tim type ColumnFn rowv = [rowv] -> ([String],String) column :: (rowv->a) -> ([a]->a) -> (a->String) -> ColumnFn column valf sumf fmtf rows = (map fmtf vals, (fmtf.sumf) vals) where vals = map valf rows calculate :: [ColumnFn rowv] -> [rowv] -> ([String],String) calculate cfs rows = [ cf rows | cf <- cfs ] ---- rows = ["I","wish","to","define","a","report"] cols = [ column id (\_ -> "") id, column length sum show, column (\s -> length s * length s) maximum show ] :r values = [ calculate rows col | col <- cols ]

1 0

Re: global variable
by Jose Morais 13 Oct '03

13 Oct '03

Sorry the newbie question and the insistence, but how exactly do I use map or fold applied to the infinite list to get successive integers at each time? Thank you

4 3

global variable
by Jose Morais 13 Oct '03

13 Oct '03

Hello, I need a function called, say, newItem, that when first called returns 1, the next time it is called it would return 2, then 3 and so on. How can I achieve this? Thank you

3 2

tuple sections?
by John Meacham 11 Oct '03

11 Oct '03

I vaugly remember using tuple sections at some point, but perhaps I was dreaming because they don't seem to actually exist. I mean something like (,3) meaning \x -> (x,3) (4,,,3) meaning \x y -> (4,x,y,3) were these supported at one point? if they don't exist, is there some reason why not? they seem like an obvious generalization of sections for binary operators like inc = (1 +) John -- --------------------------------------------------------------------------- John Meacham - California Institute of Technology, Alum. - john(a)foo.net ---------------------------------------------------------------------------

2 1

RE: Using existential types
by Tim Docker 10 Oct '03

10 Oct '03

Thanks for the comments. I think your solution misses one point in my original example... I wrote: > data ColDesc rowv = forall a. > ColDesc (rowv -> a) ([a] -> a) (a -> String) > > calculate :: [rowv] -> ColDesc rowv -> ([String],String) > calculate rs (ColDesc valf sumf fmtf) = > let vals = map valf rs in > (map fmtf vals, (fmtf.sumf) vals) This code only does the (rowv -> a) evaluation once, whereas olegs version: > calculate :: [rowv] -> ColDesc rowv -> ([String],String) > calculate rs (ColDesc fmtf sumf) = (map fmtf rs, sumf rs) does the evaluation (rowv -> a) for each element twice, I think. In a real system, as opposed to my toy example, this computation is expensive, and I don't want to do it more that necessary. Tim

2 1

compiling GHC with MS .Net 2003
by Andreas.Schroeder＠gillardon.de 10 Oct '03

10 Oct '03

Hi all, is it possible to compile ghc with the MS .Net 2003 c compiler? I assume some problems, since the compiling of ghc uses autoconf/configure/make Any idea IF it is possible? Regards, Andreas Schroeder

1 0

AW: Using existential types
by Markus.Schnell＠infineon.com 10 Oct '03

10 Oct '03

Hi Graham, > Instead, I replace the class instances by a single algebraic > data type, > whose members are functions corresponding to OO-style class methods. could you give an example? Thanks, Markus

1 0

Re: constructor name clashes
by Brandon Michael Moore 09 Oct '03

09 Oct '03

On Wed, 8 Oct 2003 Ben_Yu(a)asc.aon.com wrote: > Hi, all. > > I'm a newbie to Haskell so please bear with me if my questions sound silly. > > In coding Haskell, I feel very inconvenient that the name of data > constructors for different types have to be different. > > Also, when declaring named fields of a type, such as > data Data1 = Data1{ok1::Bool} > data Data2 = Data2{ok2::Bool} > the field names for different type also have to be unique. > > Isn't that annoying? Keeping all the names unique is no easy task in my > opinion. Wouldn't it be nice if we can have something similar to structure > fields in C? Or maybe this is already present and I'm just being ignorant? There has been a lot of work on a real record system, but none has made it into GHC. HUGS has TREX, which is based on row variable polymorphism and seems fairly powerful. O'Haskell does something based on subtyping IIRC. The big problem is being expressing functions that add or remove fields from a record. If you are just interested in fetching or setting fields you can use type classes: data A = A Int String --A {foo::Int, bar::String} data B = B Bool --B {foo::Bool} class HasFooField t a | t -> a where foo :: t -> a updateFoo :: t -> a -> t instance HasFooField A Int where foo (A f _) = f updateFoo (A _ b) v = A v b instance HasFooField B Bool where foo (B b) = b updateFoo (B _) v = B v You could probably do something with template haskell that would generate all the instances for you, but you would still need to import the classes from somewhere. $(struct [d[data A = A1 {foo::Int, bar::String} | A2 {foo::Int} ]]) $(struct [d[data B = B {foo::Bool} ]]) There was talk about compiler support for a system like this, and I think the main obstacle is convincing somebody to do it, which mostly means demonstrating that it's useful, because there's no interesting theory here. It also makes code a bit slower, but fields are not that common so it shouldn't be much of an issue. Do we really lose that much to the name overloading restrictions? The only use I can think of for records used as big bags of tagged values is for passing configuration options to complicated libaries, or getting back a bunch of values from something like parsec's token parser generator. This isn't very common, because usually any powerful function in Haskell is build from a layer of smaller functions that made the final function ridiculously easy to write. If this is true for some library, the author can either write gobs of boring option handling code that tries to expose some fraction of this power, or just extend their export list a bit and give the user the primitives to play with themselves. I don't think constructor name clashes come up that often either. There are a few names like Leaf or Empty that you want to use all the time if you are defining trees and things, but that's more playing around with trivial data structures than writing real code. Two cases I've run into are successive program representations in a compiler (everything from raw tokens though Core has an "if"), and using having an exploded representation of a type as the fixpoint of a functior for interesting recursion scheme uses, and a normal version so I can avoid the tagging. It would probably be feasible to figure out which constructor you mean in a function like desugar :: ASTSyntax -> M IntermediateSyntax desugar (IF c t e) = If (f c) (f t) (f e) desugar (ListComprehension head gens) = desugarListComp head gens ... ... But other cases are much harder (and probably much less sensible). How do you infer a type for something like this? f (C x) = case x of (C x) -> case x of (C x) -> case x (C x) -> x I think the typing rules would have to be based on something other than unification and generalization like the rest of the type system, and would probably introduce all sorts of annoying restrictions about how you are allowed to use constructors, or how to resolve the type. Brandon > I know that we can use modules to introduce name spaces. But still, this is > quite cumbersome. > > Thanks! > > Ben. > > > > This message is intended only for the addressee and may contain information > that is confidential or privileged. Unauthorized use is strictly prohibited > and may be unlawful. If you are not the intended recipient, or the person > responsible for delivering to the intended recipient, you should not read, > copy, disclose or otherwise use this message, except for the purpose of > delivery to the addressee. If you have received this email in error, please > delete and advise us immediately. > > > _______________________________________________ > Haskell mailing list > Haskell(a)haskell.org > http://www.haskell.org/mailman/listinfo/haskell > >

1 0

RE: Using existential types
by Tim Docker 08 Oct '03

08 Oct '03

Whilst on existential types, perhaps someone can tell me if this is a valid use: I wish to define a flexible report, consisting of a set of columns. The contents of each column can be defined by mapping a function to a row descriptor, generating a value, and then converting each value to a string. I also wish to present an aggregate value at the bottom of the column defined by another function. It seems that exisistential types are required to get this sort of thing to work. Is there another way? Tim -------------------- data ColDesc rowv = forall a. ColDesc (rowv -> a) ([a] -> a) (a -> String) calculate :: [rowv] -> ColDesc rowv -> ([String],String) calculate rs (ColDesc valf sumf fmtf) = let vals = map valf rs in (map fmtf vals, (fmtf.sumf) vals) rows = ["I","wish","to","define","a","report"] cols = [ ColDesc id (\_ -> "") id, ColDesc length sum show, ColDesc (\s -> length s * length s) maximum show ] values = [ calculate rows col | col <- cols ]

1 0

Using existential types
by Graham Klyne 08 Oct '03

08 Oct '03

I've been trying to use existential types [*] in my code. [*] cf. Glasgow Haskell Compiler (GHC) user guide, section 7.3.12 My experiments have thrown up a couple of questions: 1. forall x introduces x as existential when it appears immediately preceding a datatype constructor declaration, e.g. at -1- below. In position -2-, it appears to signal a universal quantifier. Is this a correct reading of the situation? 2. I have been trying to use existential types to allow an auxiliary type to appear in the implementation of a datatype, and have ended up using one datatype to "wrap" another. Is there a cleaner way? The code below has been adapted from my development code to provide a stand-alone example of the kind of thing I'm trying to do. It runs OK under Hugs. #g -- -- spike-existential.hs -- -- experimenting with existential types -- -- Questions: -- -- 1. forall x introduces x as existential when it appears immediately -- preceding a datatype constructor declaration, e.g. at -1- below. -- In position -2-, it appears to be a universal quantifier. -- ? -- -- 2. Is there cleaner way to hide the datatype vt in the declaration -- of DatatypeVal below, on the basis that I don't really want it to -- be visible outside the inference rules that are specific to this -- datatype, referenced by typeRules If I apply the existential at -- position -1-, an error is reported by Hugs: -- "cannot use selectors with existentially typed components". -- -- The approach I have adopted is to define two datatypes, -- DatatypeVal which is parameterized by expression type and value -- type, and Datatype which wraps a DatatypeVal with the value -- type being an existential. I've yet to work out implementation -- details for the stuff that uses the value type, but I anticipate -- using a constructor function that takes the DatatypeMap value -- as an argument. -- data Expr = Expr String -- Dummy expression type for spike deriving Eq data Ruleset ex = Ruleset ex String -- Dummy ruleset type for spike deriving Eq -- Type Datatype wraps DatatypeVal with an existential, thus -- hiding the value type. Also define access methods for those -- components that don't reference the value type. data Datatype ex = forall vt . Datatype (DatatypeVal ex vt) typeName (Datatype dtv) = tvalName dtv typeSuper (Datatype dtv) = tvalSuper dtv typeRules (Datatype dtv) = tvalRules dtv -- Type DatatypeVal uses a value type (vt) in its implementation. -- See tvalMap; the intent is that an implemenatation of tvalRules, -- and other code may make use of this component. data DatatypeVal ex vt = DatatypeVal {-1- data DatatypeVal ex = forall vt . Datatype -1-} { tvalName :: String , tvalSuper :: [Datatype ex] -- ^ List of datatypes that are each a supertype -- of the current datatype. The value space -- of the current datatype is a subset of the -- value space of each of these datatypes. -- NOTE: these supertypes may be implemented -- using a different value type; e.g. a -- supertype of xsd:integer is xsd:decimal , tvalMap :: {-2- forall vt. -2-} DatatypeMap vt -- ^ Lexical to value mapping, where 'vt' is -- a datatype used within a Haskell program -- to represent and manipulate values in -- the datatype's value space , tvalRules :: Ruleset ex -- ^ A set of named expressions and rules -- that are valid in in any theory that -- recognizes the current datatype. } data DatatypeMap vt = DatatypeMap { mapL2V :: String -> Maybe vt -- ^ Function to map lexical string to -- datatype value. This effectively -- defines the lexical space of the -- datatype to be all strings for which -- yield a value other than Nothing. , mapV2L :: vt -> Maybe String -- ^ Function to map a value to its canonical -- lexical form, if it has such. } datatypevalXsdInteger :: DatatypeVal Expr Integer datatypevalXsdInteger = DatatypeVal { tvalName = "http://www.w3.org/2001/XMLSchema#integer" , tvalSuper = [datatypeXsdInteger] , tvalMap = mapXsdInteger , tvalRules = rulesetXsdInteger } datatypeXsdInteger :: Datatype Expr datatypeXsdInteger = Datatype datatypevalXsdInteger -- |mapXsdInteger contains functions that perform lexical-to-value -- and value-to-canonical-lexical mappings for xsd:integer values -- mapXsdInteger :: DatatypeMap Integer mapXsdInteger = DatatypeMap { -- mapL2V :: String -> Maybe Integer mapL2V = \ s -> case [ x | (x,t) <- reads s, ("","") <- lex t ] of [] -> Nothing is -> Just $ head is -- mapV2L :: Integer -> Maybe String , mapV2L = Just . show } rulesetXsdInteger = Ruleset (Expr "expr") "rules" -- Checkout test1 = typeName datatypeXsdInteger == "http://www.w3.org/2001/XMLSchema#integer" test2 = typeName (head $ typeSuper datatypeXsdInteger) == typeName datatypeXsdInteger test3 = typeRules datatypeXsdInteger == rulesetXsdInteger ------------ Graham Klyne GK(a)NineByNine.org

6 9

Lazy IO and 'safe' uses of 'unsafePerformIO'
by Matthias Mann 08 Oct '03

08 Oct '03

Recently, there has been some discussion on this list about ongoing research on the role of unsafePerformIO, lazy IO and evaluation strategies. Within our research group at JWG-University Frankfurt some work has been done concerning the development of a non-deterministic call-by-need lambda calculus FUNDIO as a semantic basis for HasFuse, a modified implementation of the Glasgow Haskell Compiler which compiles Haskell programs using 'unsafePerformIO' in a 'safe' way, i.e. deploys only those optimizations that have been proven correct w.r.t. FUNDIO. In this context, experience with GHC's implementation has shown up that if compiled with ghc -O0 -fno-do-lambda-eta-expansion while avoiding INLINE-pragmas, 'most' uses of unsafePerfomIO are 'safe' in the sense of FUNDIO's contextual equivalence. For further details, downloads of papers and sources, please refer to the project WWW page http://www.ki.informatik.uni-frankfurt.de/research/diamond The results of FUNDIO show how evaluation may be interleaved with direct-call IO. In particular not only (\xs -> let z = length xs in "Hello World\n") _|_ = "Hello World\n" is a valid equation in FUNDIO, but also for an arbitrary expression t which may involve direct-call IO the equation (\xs -> let z = length xs in "Hello World\n") t = "Hello World\n" holds. Furthermore, the investigations indicate that some kind of optimistic evaluation is possible, i.e. the expression t above could be evaluated as long as no IO in t is executed. Hence, a demand-driven style for IO could be achieved. Matthias Mann JWG-University Frankfurt

1 0

odd interactions (was: IO behaves oddly if used nested)
by C.Reinke 07 Oct '03

07 Oct '03

[moved to haskell-cafe] > The odd is in the conceptual explanation. If I give a description > of some f x = y function in Haskell I expect that some program f x > is reduced to y and the result is given back (possibly printed). A > good story to sell to students. > > This is almost everywhere the case except for the IO monad. indeed. Although, for the benefit of your students, you'll want to separate printing and reduction, even in the first case. The important thing to realise here (and to pass on to your students) is that input/output-interactions and functional program reductions are two conceptually very different things, and that this difference is independent of which of the many functional I/O systems you use. So you can not use the functional reduction explanation for I/O as well. Once upon a long ago, I had to add IO to a purely functional reduction system as part of my PhD work, and to clarify things for myself, I tried to express the various available functional I/O systems in the common framework of transformation rules (program reduces to program, state transforms into state). The difference then simply became one of context-free versus context-sensitive transformations. [summarised in chapter 3 of my old thesis http://www.cs.kent.ac.uk/people/staff/cr3/publications/phd.html perhaps you can find some useful suggestions there?] The differences between character streams, request/response streams, result continuations, monadic I/O, or even uniqueness-typed environment passing are merely differences in how the context-free functional program reductions are embedded in a context-sensitive environment of I/O devices. They each have their pros&cons (the chapter tries to outline a logical development between the systems), and they all try to embed functional reductions into their I/O context in such a way that doing I/O does not look too foreign. So, each of the functional I/O systems lets you play down the difference between context-sensitive input/output and functional reductions to some extent, but in each of the systems, you quickly run into trouble if you try to take the similarities too far. > 3* Hmm, feels like math, looks like math, ahah! is math! > (designers and thinkers) Making the distinction between context-free and context-sensitive transformations explicit should help your group 3, as it gives them an operational semantics view of what their programs mean, and what they are supposed to do. > from what they expect. The usual questions of group 3: > > * Why is an IO a evaluated if I am not interested in it's result? > (opposite to the f x = y lazy behavior) main is evaluated because you asked the system to run its value (the whole IO a, not the a-typed result returned by running it). > * Why is in the putStr "hello world" example Hello World not shown? > (opposite to expected f x = y eval-first-then-show behavior) implementation deficiency. a more complete implementation might permit you to show intermediate steps in the program+device state transformation: program || device context =============================================== putStr ("hello "++"world") || <nothing here> -context-free reductions-->* putStr "hello world" || <nothing here> -context-sensitive interaction--> return () || "hello world" Just before the interaction, "hello world" is part of the program, so a step-by-step implementation might show it (you couldn't show it without implementation help, as the IO type is abstract), but after the interaction, the string has moved from the program to the device context in which it the program is running. The string appears on some output device, the implementation could show you return () as the final value of your program (the reduction system I was working with did so). > * Why is in the IO (IO ()) example the inner IO () not evaluated? (somewhat > opposite to expected f (f x) behavior - I personally wonder if it is even > sound in a category theoretical setting) urgh,please.. categories do not need a theory about everything [ducks quickly;] first: in an expression of type IO (IO ()), there is not necessarily an inner IO (). Evaluating the expression, and running the result, will fail or return an IO (), but that might not even exist beforehand (that's just the good old no String in IO String). second: the inner IO () returned by running the outer IO (IO ()) is not evaluated unless needed, and it won't be needed unless run. To run any IO a-typed expression, the current monadic I/O system requires it to be placed at the boundary between your functional program and the I/O context it is running in, i.e., it has to be part of the sequence of IO-operations that make up the value of main. Until it gets run this way, it's just an expression that could evaluate to an IO-script that could be run. > * ...Lots of other questions... better than individual answers is a simple conceptual model that allows the students to answer such questions (and any others they might run into). > Hmm, have to finish this email now - time constraints. I guess the short > story just is: IO monads == sometimes bad conceptual story to sell. no. and especially not to that group of students. but for this group, you can't brush the difficulties under the carpet, as you can with the other groups (and Haskell's I/O system and sugar were designed to be easy on the first two groups). you have to give them something more to wrap their minds around. > A nice (old) idea would be to represent IO as programs which are > interpreted by some _outside_ RTS in a given manner, and leave the > Haskell language clean. That is a valid operational semantics, if you get the interleaving right. That it isn't the most efficient implementation shouldn't matter in a functional programming introduction. > (It might even be a good idea with respect to the compiler > implementation since it removes checking against unsafe IO > behavior from the compiler -- just a thought) Simpler implementation is often not more efficient implementation. Hth, Claus

2 1

Naive instantiation
by Dusan Kolar 07 Oct '03

07 Oct '03

Hello, I've got (maybe a bit naive) question, whether it is possible to have instance of class (already derived from another class) if it uses more concrete type than instances of predecesing classes. Let us assume the following example: class A a where... class (A a) => B a where... class (B a) => C a where... data MyData a = MD Int a instance A (MyData a) where... instance B (MyData a) where... instance C (MyData Int) where... Hugs/GHCi produce errors, of course. Nevertheless, is there any way to obtain such a feature? (In this example, classes A and B represent "abstract" classes providing functions with general algorithms, while class C cannot have a general implementation and requires a concrete data type for MyData.) Thank you for any hints, Dusan

2 1

Read and Write to Same File
by kuq32tr02＠sneakemail.com 07 Oct '03

07 Oct '03

I am writing a program that reads and writes to the same file. I was having some problems with it writing to the file before it read it. I solved it in the following two ways: 1. main = do text <- readFile "test" let something = somefunc text writeFile "test2" something renameFile "test2" "test" 2. main = do text <- readFile "test" let something = somefunc text writeFile "test" $! something Are both of these correct (guaranteed to give the behavior I want)? Which is better (and why)? Thanks!

4 3

how is Haskell pronounced?
by David Roundy 06 Oct '03

06 Oct '03

The subject says it all. I've been using haskell for over a year, but I have no idea how to pronounce it. I tend to oscillate between rhyming with "fell" and rhyming with "full". In the former case the accent goes on the second syllable as in "Pascal", while in the latter case it goes on the first, as in "rascal" or "tattle". I feel silly telling people what a great language it is, when I can't even pronounce its name... :) -- David Roundy http://www.abridgegame.org/darcs

2 1

Why does this work - haskell mysteries?
by Petter Egesund 06 Oct '03

06 Oct '03

Hi; the proof of the pudding does lies in the eating... but I still wonder why this code is working (it is taken from the book "The Craft of functional programming"). The program connects a variable-name to value. The fun initial gives the initial state, update sets a variable & value reads a value). I evaluate value my_store 'b' to 5 and value my_store 'a' to 3 as expected from the text in the book. But I can't see what is happening here. The book has a parallel example where the data is held in a list, and this version is easy to follow, but this trick with storing a lambda-function inside a newtype beats me. The problem is that I do not understand where the accumulated data is stored (not in a list - it seems like something like a chain of functions which can be pattern-matched, but I am not sure). And why does not the lambda-function (\w -> if v==w then n else sto w) start a endless loop? (This is not homework - I am a programmer who is curious about Haskell!) Any clues, anyone? Cheers, Petter -- Var is the type of variables. type Var = Char newtype Store = Sto (Var -> Int) -- initial :: Store initial = Sto (\v -> 0) value :: Store -> Var -> Int value (Sto sto) v = sto v update :: Store -> Var -> Int -> Store update (Sto sto) v n = Sto (\w -> if v==w then n else sto w) -- testit -- my_store = update (update (update initial 'a' 4) 'b' 5) 'a' 3)

4 5

Re: lexer puzzle
by Brandon Michael Moore 05 Oct '03

05 Oct '03

Note I've replied to haskell-cafe. This post is a bit chatty and low on solid answers. On Thu, 25 Sep 2003, Sean L. Palmer wrote: > > >>A... should be split into "A.." and "." > > >I found a compromise: let's make it a lexing error! :-) > > At least that agrees with what some Haskell compilers implement. No > > current Haskell compiler/interpreter agrees with what the report seems > > to say, that is that "A..." should be lexed as the two tokens "A.." and > > ".", and similarly, "A.where" should be lexed as "A.wher" followed by "e". > > Hi. I'm really new to Haskell, just learning it, and I must say I'm pretty > overwhelmed by the large variety of constructs. (=>, <-, \ to name a few) Would that be \ as in TREX row variable polymorphism? Just remember most operators are just library functions. It's only =, ->, =>, <-, :: that are really part of the language, and {,},; for grouping. Did I miss any? > > But I'm just writing this to let you guys know (surely you know this > already) that anyone from a C/C++/Java/Delphi background is going to > completely misunderstand the meaning of A.anything in Haskell... it's > completely nonintuitive to people with my background. I kinda like dot > notation because it ties together the symbols visually, for instance > "myrec.myfield" is more of a unit than "myrec myfield". It stays together > better when surrounded by other code, and would result in fewer parenthesis > necessary. A Python programmer would understand instantly: Python uses exactly the same syntax for module access, though Python modules are usually in lowercase. It also seems to be very much in the spirit of "access a member of this object" of an OO language. Or was that supposed to be composition of a constructor with a function, A . f? Function composition, and higher order functions in general are likely to confuse an imperative programmer, but I think there isn't much syntax can do there. Or are you talking about the field access syntax? Maybe the problem is that dot has two to five different meanings, function composition, naming module members, building hierarchial module names, being a decimal point, and making elipses, and is commonly used for yet another purpose in OO languages. > Haskell to me seems to be a great language with a syntax problem, and a bad > case of too many ways to do the same thing; thus every programmer does > things their own way and it's difficult to grasp the language by looking at > various programs, since they're all so very different. As a small example, > there's 'let' vs. 'where'. Maybe a bit of pruning would be in order. Do you mean the syntax is bad in places? Haskell is the cleanest language I know of, but I'm sure it has some grungy bits. I've had problems with unary minus (can't slice binary minus), and precedence of with irrefuatble patterns and type ascription. I would be happy for any confusing syntax to be improved. Any good ideas? Syntax change is a possibility: do notation is a relatively recent addition, and arrow syntax is in the works. I think you might instead mean the syntax cuts down our market share because it isn't like common (C derived) languages. I don't think Haskell could borrow any more syntax from C without actually making the language worse. It's a problem, but not with the syntax. If someone is so solidly into a C++/Java/OO mindset that the syntax would be a problem, the semantics would probably be even more of a problem. I would suggest Python if Haskell was too much of a jump for someone. It's still OO, but it encourages more flexible and interesting programs, and you don't have to live in a Java type system. Plus, it has more libraries, bindings, and PR, so it's easier to get permission to use it in a company. If someone is used to Python's layout rule and lack of type signatures, and gets their head around some of the fun you can have dynamically picking which members of an object to access, assigning to __dict__ and so on, then Haskell should be much less of a jump in syntax, and less imposing in semantics. > That said, I still think it looks more promising than any other language > I've looked at that actually is being actively used and maintained and has a > decent installed base and good cross platform support. So I will learn it. > I just wish the transition was easier and that it took less time to learn. > ;) > > Sean I learned Haskell from the "gentle introduction". It seemed gentle enough to me but others disagree, so I'm probably not the best for advice for the raw beginner. If you are interested in learning about monads though, Jeff Newbern's monad tutorial seems accessible and as complete as anything this side of Phil Wadler's paper. I hope learning Haskell goes well. Brandon

7 8

Re: Read and Write to Same File
by kuq32tr02＠sneakemail.com 05 Oct '03

05 Oct '03

> > main = do text <- readFile "test" > > let something = somefunc text > > writeFile "test" $! something > > There is no guarantee that $! will force evaluation of the entire > 'something', so you can start writing to file before you finished > reading from it. Hopefully it will cause an exception (like in GHC), > otherwise you could damage your data (like in Hugs). > > PS. How does it behave in NHC? This is the version I've been using for a while now. It runs perfectly fine in both GHC and Hugs. I've used it many, many times with no noticeable problems. Should I be seeing errors (like exceptions in GHC)? I don't have NHC installed, so I can't test it. Thanks!

1 0

Re: IO behaves oddly if used nested
by Derek Elkins 05 Oct '03

05 Oct '03

On Sat, 04 Oct 2003 13:13:59 +0200 "blaat blaat" <l4t3r(a)hotmail.com> wrote: [moved to Haskell-Cafe] > > Neither example is odd behavior, unless > >you consider Hugs providing a perfectly reasonable instance of Show > >for IO a odd. > > True, every program behaves exactly as according to the definition of > the run-time behavior of Haskell programs. (Hugs deviates a bit from > ghc but ah well) The odd is not in the run-time behavior. > > The odd is in the conceptual explanation. If I give a description of > some f x = y function in Haskell I expect that some program f x is > reduced to y and the result is given back (possibly printed). A good > story to sell to students. Then use an impure language like Scheme. This is exactly what the IO monad avoids. > This is almost everywhere the case except for the IO monad. This is never the case. You can -only- print things via the IO monad. > In the former example, the inner putStr is _not_ evaluated but a > message is shown (hinting that a IO has some structure we can observe > before evaluation). The message shown doesn't expose any structure, let alone suggest that you can observe it. The message is independent of the actual IO action it only uses the type. You could write the Show instance yourself. instance Show (IO a) where show _ = "<<IO action>>" > In the latter example, it is shown that we are not > interested in a result of a IO program, but only in its (lazily > generated) side-effects. The effects aren't lazily generated. Monads are independent of evalution order. They would work just as well in a strict language. This is what makes them pure. (See Amr Sabry's "What is a Purely Functional Language?") > The monad behaves oddly with respect to the f > x = y behavior. Not really. If f x were, f x = \_ -> unsafePerformIO (putStr "Hello") would you be surprised that f 5 doesn't print "Hello"? > I think I observe the following reactions when I explain IO: Perhaps because you don't explain it properly? > * Why is an IO a evaluated if I am not interested in it's result? > (opposite to the f x = y lazy behavior) It isn't. If you are interested in it's result, then the result is an action which will do whatever -when run-, -not- the side-effects. If you aren't interested in it's result it will never be evaluated in Haskell, but even if it were (by adding a seq or using a strict language) the result would -still- be an action that will do something -when run-, and since you aren't interested in it it will be discarded without ever executing; a good thing as this maintains purity. > * Why is in the putStr "hello world" example Hello World not shown? > (opposite to expected f x = y eval-first-then-show behavior) Because it is never run. > * Why is in the IO (IO ()) example the inner IO () not evaluated? Because it is never run. > (somewhat opposite to expected f (f x) behavior - I personally wonder > if it is even sound in a category theoretical setting) As for the Category Theoretic behavior, it's perfectly sound. The RTS just discards the result, given that in a sense it's type is IO a -> something where 'a' is not free in something, all it -can- do is discard the result by parametricity. It doesn't matter if it 'a' is Int, (), IO FooBar, Char-> Int or anything else, any more than it matters in what type or value the first argument is in f _ = () or the "return" type of the monad action m in do_ <- m;return() (or written another way, m >>= \_ -> return ()). If you think of IO actions as state transformers (which has it's faults but works for this), then the observed behavior makes perfect sense. None of the IO actions -can- execute because they don't have the state of the world to process. It's just like with the State monad, execState (do x <- get;put (x+5);return (put 10)) 0 returns 5 not 10, the state (0 then 5) is never passed to put 10. This can be seen by unfolding this into the standard state-passing definition. If we take out the execState, -nothing- happens and we just get functions that will transform a state once it's provided; they won't and -can't- do anything until that state is provided. So putStr "foo" is IO () is World -> ((),World), it is not surprising that f _ = 10, f (putStr "foo") does not print "foo", anymore than it is surprising that f (\x -> undefined) does not cause an error, or f (put 10) does not change some state somewhere.

2 1

Newbie qustion about monads
by Juanma Barranquero 05 Oct '03

05 Oct '03

I have an extremely-newbie question about monads and how to interpret the monadic laws; I asked that same question yesterday on IRC and the answers were interesting but non-conclusive (to me anyway). I'm trying to learn monads by reading "All About Monads", version 1.0.2. I though of defining a monad like that: data Counted a = Ct Int a instance Monad (Counted) where return x = Ct 1 x Ct n x >>= f = let (Ct n' x') = f x in Ct (n+n') x' -- fail as default The intent is that Counted objects "count" the number of times an operation is applied to them. (For the purpose of the question, that's irrelevant anyway: the problem would be the same if I assigned a random number to the Int on each calling of >>=.) According to "All About Monads", the first monadic law says: (return x) >>= f == f x In my case, let's suppose I define: reverseCounted :: [a] -> Counted [a] reverseCounted x = return (reverse x) so I do: c1 = return "xxx" >>= reverseCounted -- c1 == Ct 2 "xxx" c2 = reverseCounted "xxx" -- c2 == Ct 1 "xxx" Now comes the question: In what sense should I interpret the "==" in the monadic law? Obviously, c1 and c2 are not structurally equal. If I can accept that two Counted things are "equal" even if they are not identical, is enough for me to define: instance Eq a => Eq (Counted a) where Ct _ x == Ct _ y = x == y to satisfy the first law? Yesterday I was said that it'd work if c1 and c2 are mutually substitutable. They are, for the purposes of equality, though evidently not for every purpose. A simple: count (Ct n _) = n allows me to distinguish between them. Juanma

5 13

Why does this work - haskell mysteries?!
by ,,, 05 Oct '03

05 Oct '03

Hi; the proof of the pudding does lies in the eating... but I still wonder why this code is working (it is taken from the book "The Craft of functional programming"). The program connects a variable-name to value. The fun initial gives the initial state, update sets a variable & value reads a value). I evaluate value my_store 'b' to 5 and value my_store 'a' to 3 as expected from the text in the book. But I can't see what is happening here. The book has a parallel example where the data is held in a list, and this version is easy to follow, but this trick with storing a lambda-function inside a newtype beats me. The problem is that I do not understand where the accumulated data is stored (not in a list - it seems like something like a chain of functions which can be pattern-matched, but I am not sure). And why does not the lambda-function (\w -> if v==w then n else sto w) start a endless loop? (This is not homework - I am a programmer who is curious about Haskell!) Any clues, anyone? Cheers, Petter -- Var is the type of variables. type Var = Char newtype Store = Sto (Var -> Int) -- initial :: Store initial = Sto (\v -> 0) value :: Store -> Var -> Int value (Sto sto) v = sto v update :: Store -> Var -> Int -> Store update (Sto sto) v n = Sto (\w -> if v==w then n else sto w) -- testit -- my_store = update (update (update initial 'a' 4) 'b' 5) 'a' 3)

1 0

Haskellsupport in KDevelop
by Peter Robinson 05 Oct '03

05 Oct '03

Hello, I've begun to write a plugin that provides basic support for Haskell in KDevelop 3.0 alpha. (http://www.kdevelop.org) It is already included in the CVS and the latest alpha7 release. Screenshots: http://www.thaldyron.com/snap1.png http://www.thaldyron.com/snap2.png http://www.thaldyron.com/snap3.png At the moment it's only possible to create a new project and to build/run it with GHC. What's really missing is a (primitive) background parser written that reports syntax errors. It can be written in yacc, antlr, etc., anything that produces C/C++ code. The only parsers for Haskell I could find are written themselves in Haskell. Does anyone know about one or must I write it from scratch? Regards, Peter

3 3

RE: "interact" behaves oddly if used interactively
by Simon Marlow 04 Oct '03

04 Oct '03

> Yes, the presence of lazy IO makes optimistic evaluation more > complicated, but I do not see that it compromises the purity of the > language in anyway (whatever purity is ;-). So, we're agreed that the presence of lazy evaluation makes implementing optimistic evaluation (and other evaluation strategies) more complicated. Personally, I find it disturbing that the presence of this family of library functions affects something as low-level as the evaluation strategy of the language. Or, to put it another way, it enforces a particular evaluation strategy on a part of the language, when the rest of Haskell makes no such restrictions. I would expect, in a pure language, that I could reduce any expression in a program to HNF (or _|_) without affecting the meaning of the program. In Haskell, I can only do this so long as the expression doesn't involve any lazy I/O. The real problem is that lazy I/O injects side effects into the pure world of expressions. Haskell has a perfectly good system for encapsulating side effects - the IO monad. So why put these sneaky side effects into pure values? Cheers, Simon

5 4

RE: "interact" behaves oddly if used interactively
by Simon Marlow 03 Oct '03

03 Oct '03

> > The real problem is that lazy I/O injects side effects into the pure > > world of expressions. Haskell has a perfectly good system for > > encapsulating side effects - the IO monad. So why put > these sneaky side > > effects into pure values? > > I fear one problem is that the word "side effect" is not properly > defined. > > Actually both getContents and interact are in the IO monad. Since the > action "interact" is not terminated until the input stream ends, I do > not see any problem there. Yes, it is probably true that you cannot observe any non-referential-transparency using only interact. The side effects are only visible in the IO monad, and since as you say interact doesn't let you back into the IO monad until it has finished, it is probably safe. The unsafety is only visible using the other lazy I/O operations, principally hGetContents. > Evaluation never leaves the IO monad until > termination. getContents is more strange. However, you can just define > its semantics to yield a random string. When you are not > careful you may certainly get something nearly random ;-) So... you agree that getContents in its current form should really be called unsafeGetContents? Unless perhaps we redefine its semantics to either (a) yield a random string or (b) eagerly slurp the entire stream contents? Cheers, Simon

4 3

RE: "interact" behaves oddly if used interactively
by Simon Marlow 03 Oct '03

03 Oct '03

[ taking this one to haskell-café... ] > I still do not quite agree with Simon that 'interact' exposes anything > but non-strictness. Non-strictness means that > > map toUpper _|_ = _|_ > map toUpper ('a':_|_) = ('A':_|_) > map toUpper ('a':'b':_|_) = ('A':'B':_|_) > > and 'interact (map toUpper)' is a great way to experience > this property. > > However, you can also experience the property without 'interact', > evaluating expressions like > > take 2 (map toUpper ('a':'b':undefined)) Certainly you can observe non-strictness, that's not the point. The point is that you can also observe more than just non-strictness using interact, and I don't think that is desirable. For example: interact (\xs -> let z = length xs in "Hello World\n") Now, Haskell is a pure language, so it shouldn't matter whether the implementation evaluates z or not, as long as it is careful not to violate the non-strict semantics by turning a terminating program into a non-terminating one. A parallel Haskell implementation might happily spawn off another thread to evaluate z for example. An optimistic implementation might evaluate z for a fixed amount of time before continuing with the main thread of evaluation. BUT in the presence of lazy I/O this simply isn't true any more. Why? Because z is not pure; evaluating it has a side-effect. And yet it has type Int. Am I the only one who thinks this is wrong? Cheers, Simon

8 11

Question about Type Checking
by Clement 02 Oct '03

02 Oct '03

Hi i am doing a type checker. and how can i check if the Expn that i have is a Prim Function = ("f",[([Arg "x"],Simple (Int 2))]) type Function = (Name, [Equation]) type Equation = ([Expn], Body) {- (the body of) either a simple equation: f a1 .. an = e or a conditional equation: f a1 .. an | b1 = e1 ... | bm = em data Body = Simple Expn | Conditional [(Expn, Expn)] deriving (Show, Read) data Expn = Int Int | Char Char | Bool Bool | Arg Name | Prim Name | Func Name | Appn Expn Expn | Tuple [Expn] and how can i group the Expn together for Appn? __________________________________ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com

1 0

Pre-Call for Contributions -- HC&A Report (November 2003 edition)
by C.Reinke 02 Oct '03

02 Oct '03

[apologies for multiple copies - experience has shown that not all Haskellers can be reached via the main Haskell list anymore] An entry for your diaries (no other action required right now): ------------------------------Pre-Call-------------------------------- Your contributions to the November 2003 edition of the Haskell Communities & Activities Report will be invited soon. http://www.haskell.org/communities/ Submissions are welcome between 20th and 31st of October ---------------------------------------------------------------------- The real Call for Contributions will follow closer to the submission window, in about two weeks. This is just an early warning. You will need to plan about 15 minutes for composing your contribution, which would be a brief, ASCII-format, description of your Haskell activities (see earlier editions for plenty of examples). Cheers, Claus (current editor of HC&A Reports)

1 0

Re: ANNOUNCE: HaRe, the Haskell Refactorer, version 0.1
by ketil＠ii.uib.no 02 Oct '03

02 Oct '03

(taken to -cafe) "C.Reinke" <C.Reinke(a)kent.ac.uk> writes: > Dear Haskellers, > > as part of our project on Refactoring Functional Programs > > http://www.cs.kent.ac.uk/projects/refactor-fp/ > > we are pleased to announce the availability of HaRe 0.1 (also > known as HaRe 01/10/2003 ;-), a snapshot of our Haskell Refactorer > prototype. First, let me say that I'm intrigued. This looks like really neat functionality to have available. I'm curious whether you are planning (or have developed) tools to *detect* cases for refactoring? Occasionally, I find myself wishing for a tool to help me clean up a finished program, by e.g. - removing unused items from export/import lists - identifying functions which are only used in one place (and thus candidate for inclusion in 'where' clauses) - identifying functions defined in one module, but only (mainly?) used by/depending on functions in another module, and thus candidate for cross-module migration. - perhaps similarly, identify function transformation that reduces the parameter lists (i.e. exposed function interface) and so on. (Does that make sense at all? :-) -kzm -- If I haven't seen further, it is by standing in the footprints of giants

2 1

AW: Newbie qustion about monads
by Markus.Schnell＠infineon.com 02 Oct '03

02 Oct '03

> I'm not trying to create useful monads (I'm pretty sure they > aren't :), > but understanding the concepts. So, the question remains: > when the monad > laws say that > > (return x) >>= f == f x The Monad class is just called Monad because it is intended to cover a monad. But it doesn't ensure the laws. That is your sole responsibility. > > what is intended in that "=="? Eq."==" for You can define it to your liking as long as it is commutative. HTH, Markus

3 2

RE: swap leak problem
by Simon Marlow 02 Oct '03

02 Oct '03

> This sounds like a good plan (I do have a ghc build around). > How do I go > about compiling a debugging RTS? Add the following to mk/build.mk: GhcRtsHcOpts = -optc-DDEBUG GhcRtsCcOpts = -g then go into ghc/rts and 'make clean && make'. Now rebuild your program using this GHC (or alternatively add a -L flag pointing to this ghc/rts directory). Then run it with +RTS -DS -Sstderr, observe it going very slowly and see if it throws any assertion failures. Cheers, Simon

2 1

Non-blocking keyboard peek
by Adrian May 02 Oct '03

02 Oct '03

Hi folks, I have simulator which should grind away all night but check the keyboard once per iteration to see if I'm trying to view the results, change parameters or terminate it. Therefore I need a non-blocking keyboard peek function. So far, my searching only lead to some stuff about using threads in GHC but that seems far too complicated and messy. I have no reason to open a new thread and would still have to fight over some resource lock at the very position in the program where I would normally have just peeked at the keyboard and maybe called the menu procedure. I don't think such a peek function would affect referential transparency or be considered gauche for any other reason. Does it really not exist? Can I write it for a reasonable amount of effort? Thanks in advance, AM PS. This is the second of these mails I sent 'cos the first one just didnt show up on the list. ______________________________________________________________________________ Zwei Mal Platz 1 mit dem jeweils besten Testergebnis! WEB.DE FreeMail und WEB.DE Club bei Stiftung Warentest! http://f.web.de/?mc=021183

2 1

RE: Haskell-beginners problem with memory consuption
by Simon Marlow 02 Oct '03

02 Oct '03

> Keep in mind that Strings are lists of characters. I think (somebody > correct me if I'm wrong) GHC will store a character inside a cons > cell, but that still leaves 8 bytes per character. Worst case it will > store the 8-byte cons cell pointing to a 32-bit char value, 12 bytes > per character. (Strings as lists-of-char is very useful, but not > terribly efficient). Worst case: 16 bytes per character, usual case (all characters <= '\xff'): 8 bytes per character, because we have static copies of characters 0-255 in the RTS. Using Data.PackedString or UArray Char: 4 bytes per character. Cheers, Simon

1 0

RE: Lazy IO is useful! [Was: "interact" behaves oddly...]
by Simon Marlow 02 Oct '03

02 Oct '03

> main = > do let mylist = [1..10000] > writeFile "myfile.txt" (unlines (map show mylist)) This part does run in O(1) space and isn't problematic. > -- ... > mylist' <- (map read . lines) `fmap` readFile "myfile.txt" > let result = sum mylist' > print result Indeed, this works by interleaving the I/O and the computation of the result. It is a convenient way to program, because you can use ordinary list operations on the I/O stream. We know it is not "safe": a programmer can observe the fact that implicit I/O is going on. It is also not a good way to program: you have no way to catch errors and take appropriate action if the implicit I/O should fail in some way. Should we really be encouraging the writing of programs that have no error checking? > With lazy IO, this program too should run in constant space, and the > functions that consume the large intermediate structure can remain > unchanged! > > So, I think a lazy programming language should support not only lazy > evaluation, but also lazy IO! When it is appropriate to abstract away > from the details of when IO happens, lazy IO is useful. It can > facilitate separation of concerns and modularity, just like lazy > evaluation. Appropriate lazy IO should not compromise the > purity of the language or be an obstacle to optimistic evaluation. I look forward to seeing a form of lazy I/O that doesn't suffer from these problems! (although I suspect I still won't use it :-p) Cheers, Simon

1 0

SV: SV: Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Thanks for the tip - I will give it a try. PE -----Opprinnelig melding----- Fra: Ketil Malde [mailto:ketil+haskell@ii.uib.no] Sendt: 2. oktober 2003 09:02 Til: Petter Egesund Kopi: 'haskell-cafe(a)haskell.org' Emne: Re: SV: Haskell-beginners problem with memory consuption Petter Egesund <petter.egesund(a)kunnskapsforlaget.no> writes: > fun :: String -> String > look for pat1 in string - if found subst with sub1 > look for pat2 in string - if found subst with sub2 > look for pat3 in string - if found subst with sub3 > recurse until no pattern is found I would structure this as replace :: String -> [String] -> String replace input patterns = ... At each position of input, check for the presence of patterns (use isPrefixOf) and conditionally replace it, else output first char of input and recurse on input's tail. This should make the function "online", so that it can be streamed over a large but lazy list (say a file read with "readFile" -- hurry up before Simon takes it away! :-) without explicitly constructing the whole input or output String. -kzm -- If I haven't seen further, it is by standing in the footprints of giants

1 0

SV: Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Hi & thanks for answering; I should have been more precise, my function works like this: fun :: String -> String look for pat1 in string - if found subst with sub1 look for pat2 in string - if found subst with sub2 look for pat3 in string - if found subst with sub3 recurse until no pattern is found Cheers PE -----Opprinnelig melding----- Fra: Wolfgang Jeltsch [mailto:wolfgang@jeltsch.net] Sendt: 1. oktober 2003 15:36 Til: The Haskell Cafe Emne: Re: Haskell-beginners problem with memory consuption Am Mittwoch, 1. Oktober 2003, 15:18 schrieb Petter Egesund: > [...] > The problem is of course that the string is copied each time I do a > substitute, and I wonder if a more experienced haskeller has a better > solution to my problem. It doesn't have to be a problem that the string is copied each time. If you have, e.g., functions f1, f2, ..., fn :: String -> String and do something like f1 (f2 (... (fn string)...)) then string and the intermediate data can be removed by the garbage collector as soon as they are not needed. Unfortunately, from your message it's not very clear to me what exactly you mean, and, unfortunately again, I'm not an expert in Haskell memory management. > I have myself considered these solutions, but they all seems non-elegant; > [...] Indeed, they all look very non-elegant, and I think, there is a better solution. > Cheers, > > Petter Egesund Wolfgang _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe(a)haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

2 1

Haskell-beginners problem with memory consuption
by Petter Egesund 02 Oct '03

02 Oct '03

Hi, I have just started using Haskell, and it has been really fun so far. But I have problems with memory usage when handling large files. What I do is the following; I load my file in one chunk, and does a lot of substitutes on the string - this is quick eating all my memory and the computers start to get really slow. The problem is of course that the string is copied each time I do a substitute, and I wonder if a more experienced haskeller has a better solution to my problem. I have myself considered these solutions, but they all seems non-elegant; 1. Use some IO extensions to fake a mutable variable - but solving a problem like this with a solution which is meant for IO does not seem right? 2. Split the file in smaller parts could be a solution, but then I would have to do a lot of preparsing to make sure I not spilt my file in the middle of a pattern. Sounds to me like developing a lex-like system for such a easy task is overkill? 3. I could maybe use some form of mutable arrays, but doing string regexps on an array...? 4. ? Any clues or opinions? Cheers, Petter Egesund

3 2

Another beginner's memory consumption problem...
by Bayley, Alistair 01 Oct '03

01 Oct '03

I'm trying the add-a-gram challenge from here: http://www.itasoftware.com/careers/programmers-archive.php ... and I'm also experiencing runaway memory consumption. If I load the supplied list of words (a 1.6M file) and search for shorter strings, things are OK. Memory consumption increases dramatically as I search for longer and longer trails. The function searchWord starts with a particular map and searches the maps below it (i.e. those containing shorter words), so when I search for longer trails, a larger number of maps must be examined. When I search for short trails, only a few (2-3 say) of the maps are examined. I think this implies some kind of lazy evaluation problem, but I'm not sure where to go from here. Was it a bad idea to use a Map of Maps as a data structure? Initially I had a list of Maps, but this wouldn't even load the full file (so I suppose lazy evaluation has allowed me to get a bit further...). Maps seemed like the right data structures to use for this problem. Is there some way I could force evaluation of the maps as the file is loaded? (Or is blaming the maps a red herring?) Program below: > module Main where > import Data.FiniteMap > import Data.List > import System.IO Data structure is a Map of Maps. The top-level Map holds Maps indexed by Int (for words of size n). Each of these Maps holds words of that size, where a key is the sorted list of chars for a word, and the value is the list of words whose sorted characters are that key i.e. all words constructed from the same set of characters. > type WordMaps = FiniteMap Int WordMap > type WordMap = FiniteMap String [String] > type MyWord = String ail + s = sail + n = nails + e = aliens + t = salient + r = entrails + c = clarinets + e = interlaces + d = CREDENTIALS (length 11) mar + c = cram + h = march + s = charms + o = chromas + n = monarchs + i = harmonics + a = maraschino + n = ANACHRONISM (length 11) ----------------------------------------------------------- > addWordToMap :: String -> WordMap -> WordMap > addWordToMap word m = > case lookupFM m key of > Just wlist -> addToFM m key (word:wlist) > Nothing -> addToFM m key [word] > where key = sort word > addWord :: String -> WordMaps -> WordMaps > addWord word maps = addToFM maps key newmap > where key = length word > newmap = addWordToMap word oldmap > oldmap = case (lookupFM maps key) of > Just m -> m > Nothing -> emptyFM > populateMaps :: WordMaps -> IO WordMaps > populateMaps maps = do > eof <- isEOF > if eof then return maps else do > word <- getLine > if (length word) > 0 -- test for blank lines > then populateMaps (addWord word maps) > else populateMaps maps ----------------------------------------------------------- > getMap :: WordMaps -> Int -> WordMap > getMap maps key = case (lookupFM maps key) of > Nothing -> emptyFM > Just m -> m > showWordList :: [String] -> String > showWordList = concat . intersperse ", " > printTrail :: WordMaps -> [String] -> String > printTrail _ [] = "" > printTrail maps (w:ws) = (showWordList elts) ++ "\n" ++ (printTrail maps ws) > where m = getMap maps (length w) > elts = lookupWithDefaultFM m [""] w > removeEachChar :: String -> [String] > removeEachChar word = removeEachChar' word (length word) [] > removeEachChar' :: String -> Int -> [String] -> [String] > removeEachChar' [] _ list = list > removeEachChar' _ 0 list = list > removeEachChar' word n list = removeEachChar' word (n-1) (newword:list) > where newword = (take (n-1) word) ++ (drop n word) > unfussyHead :: [[String]] -> [String] > unfussyHead [] = [] > unfussyHead l = head l Given a word (and a trail so far) this will return either an empty trail, or a trail to the first 3-char word that completes the search. A trail is just the list of keys, shortest first. > searchWord :: WordMaps -> [String] -> String -> [String] > searchWord maps trail word > | length word <= 3 = word:trail > | otherwise = > case lookupFM m word of > Nothing -> [] > Just _ -> unfussyHead $ filter ([] /=) $ map cont (removeEachChar word) > where cont = searchWord maps (word:trail) > m = getMap maps (length word) For each word (key) in a level, call searchWord. The first to return a non-empty list is the winner. If the list for this level is empty, then recurse with the next level down. > searchLevel :: WordMaps -> Int -> [String] > searchLevel _ 3 = [] > searchLevel maps level = > case (lookupFM maps level) of > Nothing -> [] > Just m -> let result = filter ([] /= ) $ map (searchWord maps []) (keysFM m) in > if result == [] > then searchLevel maps (level-1) > else head result Kick off search at top-level. > start :: WordMaps -> [String] > start maps = searchLevel maps (last (keysFM maps)) Look for a specific trail. For testing/debugging. > findw :: WordMaps -> [String] > findw maps = searchWord maps [] (sort "entrails") findw maps = searchWord maps [] (sort "nails") findw maps = searchWord maps [] (sort "salient") findw maps = searchWord maps [] (sort "entrails") findw maps = searchWord maps [] (sort "clarinets") > readWords :: IO String > readWords = do > wordMaps <- populateMaps emptyFM > return (printTrail wordMaps (findw wordMaps)) > -- This is how we'd normally start: > --return (printTrail wordMaps (start wordMaps)) > main :: IO () > main = do > s <- readWords > putStrLn s > return () ***************************************************************** The information in this email and in any attachments is confidential and intended solely for the attention and use of the named addressee(s). This information may be subject to legal professional or other privilege or may otherwise be protected by work product immunity or other legal rules. It must not be disclosed to any person without our authority. If you are not the intended recipient, or a person responsible for delivering it to the intended recipient, you are not authorised to and must not disclose, copy, distribute, or retain this message or any part of it. *****************************************************************

1 0

RE: swap leak problem
by Simon Marlow 01 Oct '03

01 Oct '03

> Oh yes, one more datum. If I run hs_perform_gc before each and every > mallocForeignPtrBytes and reallocBytes, the leak goes much > more slowly, and > the code gets much further in the job before getting killed. > But it still > leaks, and still gets killed. It could potentially be a memory leak in the RTS. There are two ways to proceed: if you have a GHC build around, you can compile up a debugging RTS and run with sanity checking enabled (+RTS -DS), which will check for memory leaks. If there are any memory leaks in the RTS, this will throw an assertion failure immediately. Alternatively, you can package up your code and send it to us with instructions on how to reproduce. Cheers, Simon

2 1

swap leak problem
by David Roundy 30 Sep '03

30 Sep '03

Hello. I've got a memory problem that is stumping me, and could use advice in trying to fix it. In brief, the heap of my application keeps increasing with time, until after a few hours it uses up all my swap and gets killed. There is no indication of a true memory leak. Heap profiling indicates that the haskell memory usage (including stacks, via -xt) remains below its initial peak value. Similarly, I've attached a sort of debugging counting finalizer to my foreignPtrs (a static int in C land), and it's clear that all the foreignPtrs I allocate are getting freed. Most of them are allocated with mallocForeignPtrBytes anyways, which should be about as safe an allocation method as one could use. The allocation pattern of my code is as follows. It reads a gzipped patch file into memory, parses it, then reads in a bunch of other files, and writes modified versions of them. Then it reads in the next patch and repeats. So it does large amounts of allocation and deallocation on a periodic basis. About half of the memory used is stored in foreignPtrs. With the exception of the patch files (which I'll get to later), all foreignPtrs are generated by mallocForeignPtrBytes or mallocForeignPtrArray. The patch files are gzip compressed, so I don't know their size until I've read them. I read the patch file one chunk at a time, and use reallocBytes to allocate a bit more memory each time. I don't expect in general to be calling reallocBytes more than four times per patch file. Of course, once I'm done I convert to a foreignPtr via newForeignPtr finalizerFree. My only idea as to the source of the problem is that it could be either a result of memory fragmentation or of not cleaning up before allocating. Neither theory is particularly convincing. Unfortunately, I'm at a loss as to how to track this problem down, so any advise would be appreciated. -- David Roundy http://www.abridgegame.org/darcs

1 1