let vs. case
Hi. I have a data type data Ok_Err s a = Ok s a and a case expression case ok_err' of ~(Ok s' a) - ... which involved in a loop (i.e. the ... contains a tail call back to the function containing the case expression). This takes a lot of space. Specifically the space complexity seems proportional to the number of loop iterations. Now if I change the case expression to let ~(Ok s' a) = ok_err' in ... then the space requirements become constant and small. So what's going on? The Haskell standard says that the dynamic sematics is the same in both cases. I don't want to use the let, because, really I'd like to exend the data type to be a sum and the case expression to make a decision. What I really want is a state monad that supports emergency stops. The case expression is in the implementation of =. BTW I am using NHC 1.3. Cheers, Theo Norvell Dr. Theodore Norvell [EMAIL PROTECTED] Electrical and Computer Engineeringhttp://www.engr.mun.ca/~theo Engineering and Applied Science Phone: (709) 737-8962 Memorial University of Newfoundland Fax: (709) 737-4042 St. John's, NF, Canada, A1B 3X5
Re: Monads in plain engllish (Was: Re: Licenses and Libraries)
On Mon, 23 Aug 1999, felix wrote: P.S. If somebody could explain Monads in plain english it might not hurt either. Someone already has: http://www.dcs.gla.ac.uk/~nww/Monad.html --KW 8-) Yes, that text is not bad, but I think it still has a problem (one I found in two or three other introductory texts of monads): it stops right before getting really interesting! Along the same lines and subject to many of the same criticisms is http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm. Any comments on improving it would be welcome. Cheers, Theo Norvell
RE: Again: Referential Equality
On Tue, 27 Jul 1999, Andreas C. Doering wrote: let x=[1..] in x==x would not terminate in the first case but succeed in the second. But, much worse let x = (a,b) in x `req` x = True but (a,b) `req` (a,b) = False So referential transparency is lost. This is a high price to pay. You are right that *something* is needed; but I don't yet know what. One solution is nondeterminism. req x y is False when x and y are not 'equal' req x y is True | False when x and y are 'equal' where 'equal' means the same as the built-in == operator for the type, or structural equality for user-defined types and where a | b means a nondeterministic choice between a and b. Now let x=[1..] in x == x can not be proved to terminate with Andreas's optimized definition of List == (although it also can not be proved not to terminate). It is valid to optimize (a,b) `req` (a,b) to let x = (a,b) in x `req` x . However, the inverse transformation increases nondeterminism and thus would not be valid. So if you define referential transparency as the saying that E[ x / F] and let x = F in E are equivalent, then referential transparency is still 'lost'. But when nondeterminism is involved, this equivalence is usually already an inequivalence. In 'good' implementations, there would be a pragmatic understanding that req x y will be True when x and y are the same reference. Cheers, Theo Dr. Theodore Norvell, Assistant Professor [EMAIL PROTECTED] Memorial University of Newfoundlandhttp://www.engr.mun.ca/~theo Vox: (709) 737-8962 Fax: (709) 737-4042
RE: strict data field
On a related topic, is there a good way to have strict strings. Should I just create my own type or is there something already in the library. Here is my situation: I have a state monad. It seems to me that if states are built out of lazy types, then there may be many states all live at the same time, thus blowing up the space. But deep in my state data types, I have strings. Also some monad operations return strings. So I need strict strings. In case I haven't made this clear, here is an example: example = do some_string - a_function_of_state modify_the_state modify_the_state_some_more do_something_with_a_string some_string Now if I run example on a state s0, then s0 will be live throughout the execution of example, whereas, if "a_function_of_state" returned a completely evaluated data structure and a completely updated the state, then the parts of s0 that are not shared should be collectable. Cheers, Theo Norvell Dr. Theodore Norvell, Assistant Professor [EMAIL PROTECTED] Memorial University of Newfoundlandhttp://www.engr.mun.ca/~theo
Re: Ackermann's function
On Thu, 18 Nov 1999, Wayne Young wrote: I'm still getting the syntax correct (playing with simple functions, etc) and was wondering how I would define Ackermann's function in Haskell. See http://www.engr.mun.ca/~theo/Publications/indExamp.lgs for three versions. The simplest is just p 0 n = n+1 p (m+1) 0 = p m 1 p (m+1) (n+1) = p m (p (m+1) n) The other two illustrate how to do it using combinators rather than explicit recursion. I'm curious to see how Haskell (using Hugs) will outperform C and Pascal for this beast. If you are comparing speed, I doubt Hugs will outperform a compiled C or Pascal program, as Hugs is an interpreter. It might be interesting to compare compiled Haskell to C or Pascal. Cheers, Theo Norvell Dr. Theodore Norvell [EMAIL PROTECTED] Electrical and Computer Engineeringhttp://www.engr.mun.ca/~theo Engineering and Applied Science Phone: (709) 737-8962 Memorial University of Newfoundland Fax: (709) 737-4042 St. John's, NF, Canada, A1B 3X5