Pointers in Haskell??
I am totally new to Haskell, so maybe this is a stupid question. Various languages have pointers (or references), for good reason. Haskell can at least partly do without them (they are only existing internally somehow). My question is: Does Haskell principally not need pointers (i.e. in case of 2 data structures needing to reference an other very large data structure) or is this a design flaw or have a overlooked something? -- HAYES TECHNOLOGIES Software Speed Optimization Bryan Hayes Managing Director Mannheimer Str. 8 D-67098 Bad Dürkheim Deutschland / Germany Tel. +49 / (0)6322 / 94 950 - 68 Fax +49 / (0)6322 / 94 950 - 69 Mobile Tel. +49 / (0)163 / 6111867 E-Mail: mailto:[EMAIL PROTECTED] Web-Site: http://www.hayestechnologies.com ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
Hello, Bryan == Bryan Hayes (Hayes Technologies) [EMAIL PROTECTED] writes: Bryan My question is: Bryan Does Haskell principally not need pointers (i.e. in case of 2 Bryan data structures needing to reference an other very large data Bryan structure) or is this a design flaw or have a overlooked Bryan something? if you hold two variables to a data structure, the structure is represented only once. This is established by a graph structure of data, instead of just a tree structure. If you modify one copy, only the reachable parts between the handle (variable) and the position where the change has been made, are copied. All common substructures that are not affected by the change remain shared. Memory is allocated and released automatically. However, if you prefer a more state-based way of programming, you can deal with pointers in a so-called monad, but if you need pointers for no other reason than efficiency, you should first try to use efficient programming techniques and data structures in Haskell. Programming in Haskell is completely different from imperative programming but it'll be worth it from the perspective of programming productivity. Just finding a way to fit imperative style in the syntax of Haskell will not give you the benefit you may expect from Haskell. Have a look at the book by Simon Thompson: Haskell: The Craft of Functional Programming. It explains the methodology of programming in Haskell very well. Cheers -- Christoph Herrmann ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
Jan Kort [EMAIL PROTECTED] writes: Simon Peyton-Jones. The implementation of functional programming languages. Prentice-Hall, 1987 is this book could be made available online ? cos on amazon it seems out of print. Jan ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe -- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. ** Get Free. Be Smart. Simply use Linux and Free Software. ** ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
All Haskell compilers use pointers internally. The idea is that because Haskell is referentially transparent and side effect free, you can overwrite a function application with its result. For example, let x = [1..1000] in foo (A x) (B x) Will internally have x pointing to the function application [1..1000], when this function application is evaluated it will overwrite the memory cell x points to with the result. So eventually it will look like this: +---+---+ +---+---+ | A | x | | B | x | +---+---+ +---+---+ | | +---+---+ | V +---+---+--+ | : | 1 | tail |--- The list 2..1000 +---+---+--+ Where each block is a memory cell and each arrow is a pointer. What does it mean to have a letter (A, x, or a number or tail, etc) inside a box? A book that describes this a lot better is: Simon Peyton-Jones. The implementation of functional programming languages. Prentice-Hall, 1987 Are they always implemented that way these days? -- J ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
In my previous example, t = [0..] b = 3 : t c = 5 : t lists b and c share t, but in x = 3 : [0..] y = 5 : [0..] lists x and y share nothing. Extensionally, they have the same values as b and c, but each has its own copy of [0..]. Unless, that is, the compiler is clever enough to recognize the subexpression [0..] which x and y have in common. I don't know whether any Haskell compilers look for common subexpressions, but it's certainly an option. So the question of whether names are *the* (only) way to obtain sharing isn't really a language question-- it's more of a compiler question. Thanks to Haskell's referential transparency, whether or not structures --or the expressions that define them-- are shared doesn't affect Haskell programs' semantics; it affects only their efficiency. That only is not intended to depreciate the significance of efficiency. It's just that one of the benefits of referential transparency is that it allows an unusually clean separation of concerns between efficiency and correctness. The absence of any update operation means that it's impossible to write a program that can detect whether a structure is being shared, so sharing is extremely common. And indeed, in the typical implementation values are nearly always implemented by pointers. In a function call, for instance, all occurrences of a parameter in the function's definition point to the same argument, thereby sharing it (another example in which sharing involves names). If the argument is an expression not in normal form, it's never evaluated more than once: On the first evaluation, the value replaces the argument, and all occurrences of the parameter share that value. --Ham At 11:07 AM -0600 12/7/01, Jeff Dalton wrote: The answers are making this question seem trickier than I'd thought it was, because so far they (both) make it sound like structure-sharing is tied very closely to names / variables. For instance: In Haskell, you can arrange for a large data structure to be shared by giving it a name, and then using the name wherever you'd use a pointer in some other language. The idea here seems to be that you have a name that refers specifically to the struccture you wish to share (as opposed to needing only an expression whose value is that structure), and then there are two possible interpretations: One possible interpretation is: this is *a* way to get sharing, to show that it's possible to have shared structures. The other possible interpretation is: this is *the* (only) way to do it. What I'd expected was that it would suffice to have an expression (and indeed that implementationally it would be much like Lisp or Java so that values were always (except in exceptional cases) secretly pointers to.) -- Jeff -- Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer Mail Code C0500 512-471-9525 The University of Texas at Austin Taylor Hall 5.138Austin, Texas 78712-1188 [EMAIL PROTECTED][EMAIL PROTECTED] -- ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: instance declarations
(sorry to mess up mail threading, but I couldn't properly reply to the message the way I'm using email right now--broken mail clients) Recently, however, there has been some interest in using named instance declarations in other ways, so perhaps we will see features like this creeping into future versions of the language. In what kinds of ways? Sounds interesting. [Of course, there is a way of naming instance declarations with the current Haskell syntax, although it is a little verbose, and would require more work on the implementers part than simple matching of strings. The syntax I'm thinking of would look something like the following: module M(C(..), instance C Int, instance C a = C [a]) where ... This is the sort of thing I was thinking too. But I would probably want to extend that to classes and types. For instance module M (class Eq a=C a (...), type A, instance C A, instance C a = C [a]) where ... If I am not mistaken, this would allow separation of the type namespace from the typeclass namespace, and would make it obvious whether the thing being exported is a type or a class. It could also potentially allow the context(s) for class and instance declarations to be more restrictive in the header or in imports than in the module body. The latter could perhaps allow resolution of overlapping instances at import time, by restricting the instances to the point of non-overlap. I'm not sure that the former would actually be useful. Hmmm speaking of overlapping instances... Would there be a practical way to add negation (of classes and possibly even types) to the context syntax? This would let you say instance (Integral a) = C (T a) where ... instance (not Integral a, Real a) = C (T a) where ... instance (not Num a) = C (T a) where ... It would also seem nice to be able to say instance (Integral a, not a Int) = C a where and instance C Int where . but this seems even more questionable. ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
cond and match
I'm wondering why Haskell doesn't support Scheme-like cond statements or a pattern matching predicate. cond c1-v1 c2-v2 or possibly cond | c1 - v1 | c2 - v2 ... would translate as case () of _ | c1 - v1 | c2 - v2 | also, it seems that a match predicate could occasionally be useful match p v would mean case v of p - True _ - False ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Pointers in Haskell??
At 12:29 PM -0600 12/7/01, Jeff Dalton wrote: In-Reply-To: Hamilton Richards's message of Fri, 7 Dec 2001 12:11:23 -0600 ... But suppose in Java I have Object x = new Whatever(); and that new object has some large substructures. I can get one of those substructures to be shared, rather than copied, without having a variable whose value is that substructure. For instance, the substructure might be shared in Object[] anArray = new Object[](x.getSubstructure(), x.getSubstructure()); provided that x.getSubstructure() returns the very same substructure (not a copy) each time. As far as the semantics of Haskell programs is concerned, there's no distinction between *same* and *equivalent*. An efficient implementation will exploit this by using identity to implement equivalence. For example, in x = [zero,one,two,three] y = [x!!2, x!!2] -- (!!) is list indexing the components of y would most likely be implemented by pointers to the same string two in memory, but it would also be correct (although less efficient) for y's two components to be separate copies of two. ... So the question of whether names are *the* (only) way to obtain sharing isn't really a language question-- it's more of a compiler question. Are they the only way that's guaranteed to result in sharing, or is even that not the case? Depends on what you mean by guaranteed. Since in Haskell sharing vs. not sharing is not a semantic issue, you can't very well say that if sharing doesn't occur under such-and-such circumstances, the language specification is violated. This is very different from languages like Java, where Object[] x = new Object[](...) Object[] y = x; means that x and y refer to the same array (not merely equivalent arrays), and if they don't, it's not Java. And what's crucial is that you can write a Java program that detects whether x and y refer to the same array, by updating the array via x and observing the effect via y. In Haskell, no such program can be written, because there's no update operation. Hence an implementation is free to share or not, and neither choice violates the language definition. To determine under what circumstances a given Haskell implementation exploits sharing, you really have to look at the implementation's source code. Or you can make some time and space measurements of Haskell programs, and derive educated guesses. Cheers, --Ham -- Hamilton Richards, PhD Department of Computer Sciences Senior Lecturer Mail Code C0500 512-471-9525 The University of Texas at Austin Taylor Hall 5.138Austin, Texas 78712-1188 [EMAIL PROTECTED][EMAIL PROTECTED] -- ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: Pointers in Haskell??
| Simon Peyton-Jones. The implementation of functional | programming languages. Prentice-Hall, 1987 | | is this book could be made available online ? cos on amazon it seems | out of print. | | This book is already on-line at | | http://research.microsoft.com/Users/simonpj/Papers/student.ps.gz | | (It was noted on the Books and Tutorials link from haskell.org, which | is usually the best place to start looking for something Haskell.) That's a useful resource too, but it's not the book that the first poster mentioned. The earlier book was more advanced, more research-oriented, and (in most respects) covered more material than the later one (which was intended as an executable tutorial). Personally, I honestly don't think I would have been able to put Gofer together without many hours poring over Simon's 1987 book. (Noting that I'm getting quite old (:-), perhaps I should explain that Gofer was the predecessor of Hugs ...) I'll have to take extra special care of my well-worn copy now that the book is out of print! All the best, Mark ___ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe