Re: Lazy evaluation alternative
On Fri, Jan 24, 2003 at 03:07:48PM +0100, Thomas Johnsson wrote:
Yes I am. But the + should be in CPS form anyways to be perfectly correct, so: natural n c = (+) n 1 (\m -> c n : (natural m))
I think Jerzy (in his usual polite manner :-) refers to the
every group has it's moshez (don't ask :)
cons operator, the :, which in a strongly typed language the right argument, the tail, is required to be a list. The function is declared as natural n c = ..., so (natural m) must be a funcion.
Well, let's pretend I made my own datatype then that supports the right type class interfaces, and has a function as a tail :) But also, this brings me to another idea! Data structures should be built from lambdas and CPS! For example, a list of integers: 1 : 2 : 3 list = \c -> c 1 (\c -> c 2 nil) now: natural n c = c n (natural n+1) full blown CPS: natural n c = (+) n 1 (\m -> c n (natural m)) so, here (nautral m) _is_ a list just like the above list!
Might I guess that you come from the lisp / scheme world?
No. :)
Regards, -- Thomas
"Chris" == Chris Clearwater <chris@sharkzone.com> writes:
Chris> But also, this brings me to another idea! Data structures Chris> should be built from lambdas and CPS! For example, a list Chris> of integers: 1 : 2 : 3 Chris> list = \c -> c 1 (\c -> c 2 nil) How about just: cons hd tl = \ c -> c hd tl then we could write the usual accessors: head xs = xs (\ hd tl -> hd) tail xs = xs (\ hd tl -> tl) This is a very, very old idea. -- Kevin S. Millikin Architecture Technology Corporation Research Scientist Specialists in Computer Architecture (952)829-5864 x. 162 http://www.atcorp.com
Chris Clearwater wrote: On Fri, Jan 24, 2003 at 01:51:57PM +0100, Jerzy Karczmarczuk wrote:
Hey, Maestro, why don't you check before posting, hm? What is the type of ones? I am afraid you will get a nasty surprise...
Check what, the type? Or are you refering to the double posting?... It seems the type would recursive? Is it that a problem? Enlighten me? :) Whatever some gentlemen impute about my politeness (as below), I don't react to double postings, because such things happen to everybody. Of course I commented the fact that you sent a a Haskell expression to a quite wide audience before attempting to ask :t Hugs or GHCi. Here you are their answers. If: ones c = c (1:ones) then the answers are, GHCi, then Hugs: claz.hs:1: Couldn't match `[a]' against `(t1 -> t2) -> t' Expected type: [a] Inferred type: (t1 -> t2) -> t In the second argument of `(:)', namely `ones' In the first argument of `c', namely `(1 : ones)' ********************************************************** Type checking ERROR claz.hs:1 - Type error in function binding *** Term : ones *** Type : ([a] -> b) -> b *** Does not match : [a] Now, simply: it costs really nothing to check that, and BTW the result is almost obvious when you look at (1:ones). (Note that Ghci and Hugs give slightly different answers...) You might construct a tree, or just for testing replace (1:ones) by (1,ones), but I suspect that then you will get the infinite recursion in type definition. CPS is delicate... Next posting:
On Fri, Jan 24, 2003 at 03:07:48PM +0100, Thomas Johnsson wrote: ...
I think Jerzy (in his usual polite manner :-) refers to the
every group has it's moshez (don't ask :)
cons operator, the :, which in a strongly typed language the right argument, the tail, is required to be a list.
...
Well, let's pretend I made my own datatype then that supports the right type class interfaces, and has a function as a tail :)
I must confess that I don't know what moshez are, but I won't ask. Thanks to both of you for a new English word I learned. I suspect that the infinite type unification gets in the way anyhow. You can define your 'ones' in, say, Scheme, but this is clumsy, much less transparent than using macros (delay, cons-stream, etc.), or just the lambda-ification, as proposed by Kevin Millikin. It is not even clear *to what* you should apply your continuation. However, Kevin S Millikin is too pessimistic about
So your trick *is* used to implement lazy evaluation in other languages. It's not very pleasant if you write a lot of lazy code, because you have to explicitly suspend evaluation of values using delay and explicitly demand evaluation using force.
because if macros are there, all the administrative chores can be hidden. Hm. By the way, the fact that Haskell has no macros was a conscious decision, or by default, because nobody needed them? On the other hand, there are languages where the construction and processing of objects representing lazy streams is different, uses *generators* (Smalltalk, Icon, Python); they are not functions, but 'objects' with an internal updateable state and a 'method' "next" or equivalent. They can also be simulated in Haskell. === I suppose that it would be better to move this thread to haskell-café. Jerzy Karczmarczuk
participants (3)
-
Chris Clearwater -
Jerzy Karczmarczuk -
Kevin S. Millikin