- Haskell-Cafe - Haskell.org

Re: 'any' and 'all' compared with the rest of the Report
by Iavor Diatchki 24 Jan '01

24 Jan '01

hello i myself am not an experienced Haskell user, so please correct me if i am wrong. it is difficult in general to reason about the performance of lazy programs, so i don't think one can assume much. in particular i dont think 'any' and 'all' will perform in linear space. here is why i think so: take an example when 'any' is applied to some list (x:xs) and someone is actually interested in the result: any p (x:xs) 1. -> (or . map p) (x:xs) 2. -> or (map p (x:xs)) 3. -> foldr (||) False (map p (x:xs)) [at this stage we need to know what what kind of list is (map p (x:xs)) i.e. empty or a cons thing, so we need to do some evaluation] 4. -> foldr (||) False (p x : map p xs) 5. -> p x || (foldr (||) False (map p xs)) [at this stage we need to know what kind of thing is p x, i.e. True or False, so we need to evaluate p x] 6. -> if p x is True we are done (result True) 7. -> if p x is False the result is (foldr (||) False (map p xs)) and we go back to 3. note that p x has become garbage and so it doesnt really take up any space, so one really needs only enough space to process the list one element at a time. what causes problems is the need to create unnecessary cons cells (i.e. the evaluation after 3.). this is bad because it takes time. of course it only adds a constant so the complexity is the same but in practise programs run slower. this is where i would expect a good compiler to do some optimisation, i.e to remove the need for the intermediate list. i like the idea of programming at a higher level, as i believe it produces "better structured" programs. what i mean is that one manages to capture certain aspects of a program, which would be obscured if one always used explicit recursion. i think higher order functions like maps and folds really go a long way toward structuring functional programs. in a way this is simillar to using loops instead of explicit gotos in procedural programs. anyways these are my deep thought on the matter :) bye iavor On Tue, Jan 23, 2001 at 12:35:19PM -0600, Eric Shade wrote: ... > > Then I get to 'any' and 'all', whose specification requires linear > time and *linear* space when it should run in constant space. (By the > way, I checked and GHC does *not* use the Prelude definitions but > rather the obvious recursive ones, and most of its optimizations based > on "good consumers/producers" use meta-linguistic rewrite rules. So > without knowing the specific optimizations that a compiler provides, I > think it's safe to assume that the Prelude 'any' and 'all' *will* > require linear space.) ... -- +---------------------------------+---------------------------------------+ |Iavor S. Diatchki | email: diatchki(a)cse.ogi.edu | |Dept. of Computer Science | web: http://www.cse.ogi.edu/~diatchki | |Oregon Graduate Institute | tel: 5037481631 | +---------------------------------+---------------------------------------+

3 3

Re: Specifications of 'any', 'all', 'findIndices'
by D. Tweed 24 Jan '01

24 Jan '01

On Tue, 23 Jan 2001, Mark Tullsen wrote: > Johannes Waldmann wrote: > > ... > > I'd rather write clear code, than worry about efficiency too early. > > Who said this, "premature optimization is the root of all evil". > > I've always attributed this to Donald Knuth: > > Premature optimization is the root of all evil in programming. In his paper on the errors of TeX (no proper ref but it's reprinted in his book on Literate Programming) he calls it Hoare's dictum (i.e. Tony Hoare) although the context suggests that this isn't an `official name'. Dunno if Hoare heard it from someone else though... ___cheers,_dave________________________________________________________ www.cs.bris.ac.uk/~tweed/pi.htm|tweed's law: however many computers email: tweed(a)cs.bris.ac.uk | you have, half your time is spent work tel: (0117) 954-5250 | waiting for compilations to finish.

1 0

RE: {-# LINE 100 "Foo.hs #-} vs. # 100 "Foo.hs"
by Simon Marlow 19 Jan '01

19 Jan '01

> Indeed. Or do you want to tell me that you are going to > break one of my favourite programs? > > [ code deleted ] > # 111 "Foo.hs" Actually the cpp-style pragma is only recognised if the '#' is in the leftmost column and is followed by optional spaces and a digit. It's quite hard to write one of these in a legal Haskell program, but not impossible. Simon

3 2

Re: A simple problem
by Tom Pledger 19 Jan '01

19 Jan '01

Ashley Yakeley writes: > At 2001-01-18 15:38, I wrote: > > >3 is not always an Integer. It's of type "(Num a) => a". > > Of course, it would be nice if 3 were an Integer, and Integer were a > subtype of Real. I haven't come across a language that does this, where > for instance 3.0 can be cast to Integer (because it is one) but 3.1 > cannot be. A cast in that direction - becoming more specific - would be nicely typed as: Real -> Maybe Integer or with the help of the fail and return methods: Monad m => Real -> m Integer

1 0

Re: A simple problem
by Ashley Yakeley 19 Jan '01

19 Jan '01

At 2001-01-18 15:57, William Lee Irwin III wrote: >class C a where > fun :: a -> Integer > >instance Integral a => C a where > fun = toInteger . succ Gives "syntax error in instance head (constructor expected)" at the 'instance' line in Hugs. Is there a option I need to turn on or something? -- Ashley Yakeley, Seattle WA

2 1

Re: A simple problem
by William Lee Irwin III 19 Jan '01

19 Jan '01

Moving over to haskell-cafe... At 2001-01-18 05:16, Saswat Anand wrote: >> fun 3 --gives error in Hugs >> fun (3::Integer) -- OK >> >> I am a building an embedded language, so don't want user to cast. Is >> there a solution? On Thu, Jan 18, 2001 at 03:38:10PM -0800, Ashley Yakeley wrote: > 3 is not always an Integer. It's of type "(Num a) => a". > I couldn't find a way to say that every Num is a C. I didn't try to say every Num is C, but I found a way to make his example work: class C a where fun :: a -> Integer instance Integral a => C a where fun = toInteger . succ One has no trouble whatsoever with evaluating fun 3 with this instance defined instead of the original. I'm not sure as to the details, as I'm fuzzy on the typing derivations making heavy use of qualified types. Is this the monomorphism restriction biting us again? Cheers, Bill -- <nrut> how does one decide if something is undecidable? <Galois> carefully --

1 0

Re: O'Haskell OOP Polymorphic Functions
by Ashley Yakeley 18 Jan '01

18 Jan '01

At 2001-01-17 16:07, Johan Nordlander wrote: >Ashley Yakeley wrote: >> >> OK, I've figured it out. In this O'Haskell statement, >> >> > struct Derived < Base = >> > value :: Int >> >> ...Derived is not, in fact, a subtype of Base. Derived and Base are >> disjoint types, but an implicit map of type "Derived -> Base" has been >> defined. >> >> -- >> Ashley Yakeley, Seattle WA > >Well, they are actually subtypes, as far as no implicit mapping needs to be >defined. But since Derived and Base also are two distinct type constructors, >the overloading system treats them as completely unrelated types (which is >fine, in general). All O'Haskell treats them as completely unrelated types. In fact, this O'Haskell... > struct Base = > b1 :: Int > b2 :: Char > > struct Derived < Base = > d1 :: Int ...is a kind of syntactic sugar for this Haskell... > data Base = Base (Int,Char) > dotb1 (Base (x,_)) = x > dotb2 (Base (_,x)) = x > > data Derived = Derived (Int,Char,Int) > dotd1 (Derived (_,_,x)) = x > > implicitMap (Derived (b1,b2,d1)) = Base (b1,b2) This seems to be stretching the concept of 'subtype'. Sorry if I sound so bitter and disappointed. I was hoping for a Haskell extended with real dynamic subtyping... -- Ashley Yakeley, Seattle WA

2 1

Boolean Primes Map (continued)
by Shlomi Fish 18 Jan '01

18 Jan '01

Well, after some thought, I decided to try re-writing the boolean primes map program only using a list instead of an array. I came up with this program: primes :: Int -> [Int] primes how_much = (iterate 2 initial_map) where initial_map :: [Bool] initial_map = (map (\x -> True) [ 0 .. how_much]) iterate :: Int -> [Bool] -> [Int] iterate p (a:as) | p > mybound = process_map p (a:as) | a = p:(iterate (p+1) (mymark (p+1) step (2*p) as)) | (not a) = (iterate (p+1) as) where step :: Int step = if p == 2 then p else 2*p mymark :: Int -> Int -> Int -> [Bool] -> [Bool] mymark cur_pos step next_pos [] = [] mymark cur_pos step next_pos (a:as) = if (cur_pos == next_pos) then False:(mymark (cur_pos+1) step (cur_pos+step) as) else a:(mymark (cur_pos+1) step next_pos as) mybound :: Int mybound = ceiling(sqrt(fromIntegral(how_much))) process_map :: Int -> [Bool] -> [Int] process_map cur_pos [] = [] process_map cur_pos (a:as) | a = cur_pos:(process_map (cur_pos+1) as) | (not a) = (process_map (cur_pos+1) as) I don't know too much about Haskell yet, so it is possible this program can be further optimized using some Haskell built-ins. Now, this program can scale to 100,000 and beyond, as opposed to the array version which only got until 30,000 or 40,000. It's a pity Haskell doesn't handle arrays very well, but I guess every language has its faults. Regards, Shlomi Fish ---------------------------------------------------------------------- Shlomi Fish shlomif(a)vipe.technion.ac.il Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: shlomif(a)techie.com The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one.

2 1

Re: O'Haskell OOP Polymorphic Functions
by Johan Nordlander 18 Jan '01

18 Jan '01

Ashley Yakeley wrote: > > OK, I've figured it out. In this O'Haskell statement, > > > struct Derived < Base = > > value :: Int > > ...Derived is not, in fact, a subtype of Base. Derived and Base are > disjoint types, but an implicit map of type "Derived -> Base" has been > defined. > > -- > Ashley Yakeley, Seattle WA Well, they are actually subtypes, as far as no implicit mapping needs to be defined. But since Derived and Base also are two distinct type constructors, the overloading system treats them as completely unrelated types (which is fine, in general). To this the upcoming O'Hugs release adds the capability of using an instance defined for a (unique, smallest) supertype of the inferred type, in case an instance for the inferred type is missing. This all makes a system that is very similar to the overlapping instances extension that Tom mentioned. -- Johan

1 0

RE: GHCi, Hugs (was: Mixture ...)
by Simon Peyton-Jones 18 Jan '01

18 Jan '01

| It'd be good if left-behind tools were using a BSD(-like) licence, in | the event that anybody - commercial or otherwise - who wanted to pick | them up again, were free to do so. GHC does indeed have a BSD-like license. Simon

2 1