- Haskell-Cafe - Haskell.org

RE: Using "type"
by Simon Peyton-Jones 09 May '02

09 May '02

GHC currently takes the following (non-Haskell 98) attitude to type synonyms: first expand type synonyms only then check for partial applications of type synonyms then perform type checking So in his case type for f expands to: f :: m () -> m () test :: Int -> Int You can see how the type for test comes out: Thing (Const Int) = Const Int () = Int Now GHC tries to unify m () with Int and fails, as it should. The error message is phrased in terms of the original un-expanded types, which is usually a good thing but on this occasion gives a rather odd looking error message. GHC shouldn't really do this lazy checking unless you say -fglasgow-exts Simon | -----Original Message----- | From: Samuel E. Moelius III [mailto:usmoeliu@mcs.drexel.edu] | Sent: 04 May 2002 20:45 | To: haskell-cafe(a)haskell.org | Subject: Using "type" | | | I apologize if this question has been asked before... | | It seems to me the following code should be legal: | | type Thing m = m () | | type Const a b = a | | f :: Thing m -> Thing m | f x = x | | test :: Thing (Const Int) -> Thing (Const Int) | test = f | | However, GHC gives the following error: | | Couldn't match `Thing m' against `Thing (Const Int)' | Expected type: Thing m | Inferred type: Thing (Const Int) | Expected type: Thing (Const Int) -> Thing (Const Int) | Inferred type: Thing m -> Thing m | | But if you change the definition of Const | | newtype Const a b = MakeConst a | | the code compiles fine. | | Is this the desired behavior? | | Is it the case that when you have quantification of a type | variable of | kind * -> * (in this case, m), that variable may only become | bound to a | type constructor? | | Sam Moelius | | _______________________________________________ | Haskell-Cafe mailing list | Haskell-Cafe(a)haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe |

1 0

RE: Deforestration harmful?
by Simon Marlow 08 May '02

08 May '02

> I will be a bit more precise. Let f and g have type: > > g :: Seed -> [Tree] > f :: Tree -> [Expr] > > where Tree1 is a tip-valued binary tree, and Tree2 is also a > binary tree but the forks are arithmetic operators: > > data Tree = Tip Int | Bin Tree1 Tree1 > data Expr = Val Int | Add Tree2 Tree2 | Sub Tree2 Tree2 | Mul .... These don't make sense. Perhaps for Tree1 you mean Tree, and Tree2 you mean Expr? > The function g is defined like: > > g seed = [ z | (s1, s2) <- split seed, > x <- g s1, y <- g s2, z <- Bin x y ] There's a type error in that definition: 'Bin x y' is not a list. > The function f converts a Tree to many Exprs by replacing > Bin with one of Add, Sub, Mul or Div: > > f (Tip i) = [Val i] > f (Bin x y) = [op x' y' | x' <- f x, y' <- f y, op <- join x y] > > The program before fusion looks like: > > concat . map f . g > > while the fused program simply: > > fg seed = [ z | (s1, s2) <- split seed, > x <- fg s1, y <- fg s2, z <- join x y ] > join x y = [op x y | op <- [Add, Sub, ... ]] > > And the surprise was the fused program ran slower than the > naive one before fusion. > > The time profiling showed that, in one run, the naive > program itself took 2.00 sec to finish, with 9% extra GC time. The > fused program itself, on the other hand, took only 1.84 sec but > spent an extra 67% of time on GC (the heap size is the default > 64M). > > Considering their heap profiles, both of them look like several > steep, slanted triangles standing next to each other. The highest peak > in the heap profile of the naive program reaches only 50K of memory, > while that for the fused program reaches as much as 1500K. In > the former case, the heap is mostly occupied by chunks created > by g. In the latter case, the heap is mostly occupied by join. > > > Furthermore, deforestation itself does not reduce runtime very much. > > Indeed. Looks like it helps to speed up the mutator a bit but > end up spending more time on GC, due to increased heap demand. I think this is a misleading generalisation - in most cases deforestation doesn't affect the heap residency behaviour of the program. As Olaf said, deforestation tends to result in small constant factor speedups, but can be particularly beneficial if it enables further optimisations to take place. In your case it looks like the transformation you made by hand had the side-effect of introducing a space leak, but it's quite hard to tell from the code you've shown us. (space leaks are particularly hard to identify by eye, using the profiling tools is the only way to really understand what's happening). > Monday, May 6, 2002, 12:02 PM, Simon Marlow wrote： > > It is entirely plausible that as you increase the heap > size the mutator > > time increases: this is because you get fewer cache hits > with a larger > > heap. GHC starts off with a small heap size so as to try > to make the > > most of the cache. However, on most examples we've seen > the benefits of > > reducing garbage collections by increasing the heap size tend to > > outweigh the benefits from staying in the cache. > > Did you try heap profiling to discover what structure was > filling up > > the heap? > > Thanks for the explanation. :) > > More info. about the heap was given above. By the way, could there be > situations where increasing the heap size also increases the GC time? Yes, again because of increased cache misses. Cheers, Simon

1 0

Re: Proper scaling of randoms
by Dylan Thurston 07 May '02

07 May '02

(Redirected to haskell-cafe.) On Mon, May 06, 2002 at 04:49:55PM -0700, oleg(a)pobox.com wrote: > Problem: given an integer n within [0..maxn], design a scaling > function sc(n) that returns an integer within [s..t], t>=s. > The function sc(n) must be 'monotonic': > 0<=a < b ==> sc(a) <= sc(b) > and it must map the ends of the interval: > sc(0) -> s and sc(maxn) -> t. Just an aside (which Oleg surely knows): for actual random number generation, you often don't care about the monotonicity, and only care about uniform generation. In this case, there is a very simple algorithm: work modulo (s-t+1). scm(n) = (n `rem` (s-t+1)) + s Warning: some, broken, random number generators do not behave well when used like this. Also, although this is as uniform as possible, there is a systematic skew towards the lower end of the range [s..t]. --Dylan Thurston

1 0

administrative question
by Matthias 07 May '02

07 May '02

dear haskell-o-tronics, >From time to time i get emails from haskell-cafe, with the subject "RE: <some topic>" but since i am only subscribe since some days i dont have the original message and thus would be habby if anybody could bounce me the list-mails from the last year? Matthias

1 0

Re: Bug in the scaling of randoms ...
by Ronny Wichers Schreur 07 May '02

07 May '02

Dimitre Novatchev writes (to the Haskell mailing list): > In his excellent book Simon Thompson defines scaling of the elements of > a sequence of random numbers from the interval [0, 65535] to an > interval [s,t] in the following way (top of page 368): > > scaleSequence :: Int -> Int -> [Int] -> [Int] > > scaleSequence s t > > = map scale > > where > > scale n = n `div` denom + s > > range = t - s + 1 > > denom = modulus `div` range > > where modulus = 65536 > However, the following expression: > > e4000 = (scaleSequence 1 966 ([65231] ++ [1..965]))!!0 > evaluates to 974 -- clearly outside of the specified interval. The function fails in this case because the range doesn't divide the modulus. In the book (I checked the Miranda version), there's a remark after the function that "[The] range of numbers 0 to modulus-1 is split into range blocks, each of the same length." When the range doesn't divide the modulus, it's not possible to get a uniform distribution if you scale each value individually. I assume this is acceptable, otherwise you'll have to discard or combine values from the original sequence. Oleg answers: >We aim to find a function sc(n) defined over integers 0 <= n <= M so >that > sc(0) -> s (given integral number) > sc(M) -> t (given integral number), t>=s >and > 0<=a < b ==> sc(a) <= sc(b) > >Such a function sc(n) is given by the following expression: > sc(n) = (n*(t-s)) `div` M + s (M = modulus - 1) I think a more natural function would be sc(n) = (n * (t-s+1)) `div` modulus + s This satifies the conditions (assuming range = t-s+1 <= modulus), and distributes the values more evenly, in particular when the range divides the modulus. Cheers, Ronny Wichers Schreur

1 0

Re: Using "type"
by Ashley Yakeley 04 May '02

04 May '02

At 2002-05-04 12:45, Samuel E. Moelius III wrote: > type Thing m = m () > > type Const a b = a > > f :: Thing m -> Thing m > f x = x > > test :: Thing (Const Int) -> Thing (Const Int) This is wrong. Type synonyms must be fully applied, whereas you have Const applied only to one argument, not two. 'Const' isn't really a type-constructor, it's more like a macro. Is it something in the air? Spring is here, and everyone wants type-lambda... -- Ashley Yakeley, Seattle WA

1 0

Using "type"
by Samuel E. Moelius III 04 May '02

04 May '02

I apologize if this question has been asked before... It seems to me the following code should be legal: type Thing m = m () type Const a b = a f :: Thing m -> Thing m f x = x test :: Thing (Const Int) -> Thing (Const Int) test = f However, GHC gives the following error: Couldn't match `Thing m' against `Thing (Const Int)' Expected type: Thing m Inferred type: Thing (Const Int) Expected type: Thing (Const Int) -> Thing (Const Int) Inferred type: Thing m -> Thing m But if you change the definition of Const newtype Const a b = MakeConst a the code compiles fine. Is this the desired behavior? Is it the case that when you have quantification of a type variable of kind * -> * (in this case, m), that variable may only become bound to a type constructor? Sam Moelius

1 0

Re: tricky instance declarations
by Ashley Yakeley 03 May '02

03 May '02

At 2002-05-03 03:53, Warrick Gray wrote: >instance Monad (IO (Either ConnError a)) where You do of course mean instance Monad (/\a => IO (Either ConnError a)) where ... ...but you just can't do type-lambdas in Haskell. -- Ashley Yakeley, Seattle WA

1 0

User-Defined Types
by Matthias 01 May '02

01 May '02

Hello, I am a student of computer science at the university of Aachen in Germany and presently do a course about functional programming in haskell. I just wanted to introduce myself, because it is likely to happen that my posting apear frequently in the next couple of month. So my first question is about User-Defined Types. Stating the Gentle Introduction to Haskell 98 (2.2) , i already know that: "Type Constructors and date Constructors are in seperte namespaces. [example]" But according to the chapter (2.2.1) "Recursive Types" i see the polymorphic definition of a tree is: data Tree a = Leaf a | Branch (Tree a) (Tree a) where (Tree a) is obviously the data-constructor out of "the other namespace". I guess that the () is warping Tree a from the "data-constructor-namespace" into the "type-constructor-namespace". Since the gentle-intro implicitly uses (), which i am not used to - i would be happy about some hints about (). That might not be to difficult, i hope. Also i would not regret some hints about "->" which is used in function-type-definitions. I would prefer writing plus :: a,a -> a instead of the ->-variant in order to stress the distinction between arguments and returned type. What is meant that -> is "associating to the right"? Is there a name for '->'? Sincerely Matthias Pfeifer

3 3

Re: Read File
by Jorge Adriano 01 May '02

01 May '02

----------------- [moving to haskell-cafe] > I want to read some data from a text file. I accomplished it but I want to > read data from file as a Integer list for example text file has [1,2,3,5] ----------------- Wait you actually have "[1,2,3,5]" --------------------- > and when I read this data from file I handeled it as string. What can I do > to get it as integer list. Hint: map read ["1","2","3"] ::[Int] ------------------- this would be helpfull if you had "1 2 3 5". It's easier then Hint: read "[1,2,3,5]"::[Int] J.A.

1 0