Re: partition and lifted products
> | Can we have extensional products and functions (or at least the means > | to define them) please? > Language issues > ~~~ > A significant difficulty is that seq is essentially un-implementable > for unlifted products (requires parallelism). Well, all you need is an evaluation with a limited time resource (a counter) which returns a thunk when the time resource was insufficient to perform the computation. One could implement it as a monad :-). seq would just keep evaluating both components using this method as long as it only gets thunks back (for both). With this method available one can implement 'parallel or' and also a proper equality, i.e. one that treats (1,[4..])==(2,[4..]) and ([4..],1)==([4..],2) equally. > Implementation issues > ~ > If your program has no seqs then unlifted products effectively > means 'add a twiddle to every pattern match'. This is rather > easy to implement. That's essentially the way Miranda does it. In Miranda, undef and (undef,undef) are indistinguishable - except when you use seq: seq (hd [undef,(5,4)]) 3 is undefined while: seq (hd [(undef,undef),(5,4)]) 3 is 3. Stefan Kahrs
RE: partition and lifted products
| Can we have extensional products and functions (or at least the means | to define them) please? Does anyone want to come up with a concrete language proposal? Language issues ~~~ A significant difficulty is that seq is essentially un-implementable for unlifted products (requires parallelism). Ditto functions. Whether or not you think it was a mistake to make seq polymorphic, that's the way H98 is. Implementation issues ~ If your program has no seqs then unlifted products effectively means 'add a twiddle to every pattern match'. This is rather easy to implement. For functions, it means treating bottom a bit differently. For example, eta reduction is always valid for a unlifted function but not necessarily valid for a lifted one. It wouldn't be that easy to make GHC have two function types, since they pervade the compiler. Simon
Re: partition and lifted products
Ross Paterson wrote: > > On Wed, Jan 19, 2000 at 03:18:34PM -0700, Joe Fasel wrote: > > *Sigh* And the language named in honor of Haskell Curry > > for which Currying is not a valid transformation strikes > > again! > > Worse, not only are the built-in product and function types lifted, > but one can't define the unlifted ones. Before Haskell 1.3, even though > the built-in product was lifted, one could define pairs as an abstract > type exporting functions to make pairs and extract their components, > which would then behave as true products. But then seq was introduced > (and in Haskell 98 extended to type variables) so everything is lifted. > > Can we have extensional products and functions (or at least the means > to define them) please? Just to add my vote: Yes, please give us these! I'm working on a program transformation system for a subset of Haskell. But it's not really a subset of Haskell, it has true products and functions. This is because to do without them means either that I have to jettison lots of laws and equivalences or that I have to transform using "partial correctness" ---equivalence modulo termination---rather than "total correctness": yuck). Most people I've talked to consider lifted products a mistake. (This may not mean that most consider it a mistake, maybe only that those who have disagreed have not bothered to tell me so.) Numerous others are unaware that products are lifted in Haskell! A while back, I asked John Peterson about the history of lifted products in Haskell. He told me that the decision was based on pragmatics (not semantics or efficiency): that it was simpler for implementations to represent an n-tuple as an n-ary constructor than to add an extra construct to the language (am I quoting you correctly, John?). - Mark Tullsen
Re: partition and lifted products
On Wed, Jan 19, 2000 at 03:18:34PM -0700, Joe Fasel wrote: > *Sigh* And the language named in honor of Haskell Curry > for which Currying is not a valid transformation strikes > again! Worse, not only are the built-in product and function types lifted, but one can't define the unlifted ones. Before Haskell 1.3, even though the built-in product was lifted, one could define pairs as an abstract type exporting functions to make pairs and extract their components, which would then behave as true products. But then seq was introduced (and in Haskell 98 extended to type variables) so everything is lifted. Can we have extensional products and functions (or at least the means to define them) please?
partition and lifted products
Folks, I claimed that these are different functions: > partition1 p xs = (filter p xs, filter (not . p) xs) > partition2 p = foldr (\x (ys, zs) -> if p x then (x:ys,zs) else (ys,x:zs)) > ([],[]) I was correct, but not for the reason I thought. Nota bene: partition1 p bottom = (bottom, bottom) partition2 p bottom = bottom *Sigh* And the language named in honor of Haskell Curry for which Currying is not a valid transformation strikes again! Cheers, --Joe Joseph H. Fasel, Ph.D. email: [EMAIL PROTECTED] Technology Modeling and Analysisphone: +1 505 667 7158 University of Californiafax:+1 505 667 2960 Los Alamos National Laboratory postal: TSA-7 MS F609 Los Alamos, NM 87545