[Haskell-cafe] Strange subtract operator behavior - and lazy naturals

[John Meacham]

On Wed, Oct 17, 2007 at 12:41:54PM +0200, Yitzchak Gale wrote:
> John Meacham wrote:
> > if anyone is interested, Although I bet this has been implemented a
> > hundred times over, I have attached my lazy naturals module below just
> > for larks.
> 
> Nice, lots of fun!
> 
> Wouldn't it be more convenient to allow them
> to be signed? True, you can't have laziness in
> certain cases, and certain calculations would
> be non-convergent. But you already have
> things like that, e.g subtraction, and natEven.

Well, a couple reasons. One is that Natural numbers are a pretty useful
type in and of themselves, often times when used with lazy evaluation.
The other is that it is unclear what semantics lazy signed numbers would
have, if the sign were at the beginning, then addition and subtraction
would be strict, because you can't figure out the sign of the result
without running through to the end of the number. Another possibility
which would preserve full lazyness is
to just allow negative numbers in Sum. which has other issues, such as
you no longer have the property that

Sum x (Sum _ _) > Sum x Zero

so you couldn't short circuit comparison operations.

All in all, it wasn't clear what the correct tradeoffs would be and I
wanted numbers restricted to naturals as much as I wanted lazy numbers. 

> > Anyone have any comments on my lazy multiplication algorithm?
> 
> Looks fine to me. It introduces left-bias, but you have
> to do it one way or the other.

Yeah, It was fairly subtle, I tried various permutations of making it
strict or lazy and removing the bias. I can't say I fully understand why
this form is the best. something odd is that If I don't rebuild the
second argument (y + ry) but use the original second value placed in, it
drastically slows things down.

> > since (+) is lazy, we can still get a good lazy result without
> > evaluating the tails when multiplying... that is nice.
> 
> Yes.
> 
> > n `mod` 0 should be?
> 
> It's negative infinity if n > 0, but you don't
> allow negative numbers. I suppose it should
> be Zero - in your implementation, Zero does
> not exactly have the semantics of 0. Instead,
> it means "either 0 or negative".

yes. something like that, I read a paper somewhere that defined negative 



> > If anyone wants me to clean this up and package it as a real module, I
> > would be happy to do so.
> 
> Please at least post it to the wiki.

okay, I will clean it up some and add more documentation as to the
strictness. In general, I tried to make everything 'head-strict' in both
arguments, but symmetrically 'tail-lazy'. if that makes sense at all. I
need to come up with some better terminology.

also, div is tail-lazy, but mod is tail-strict.

I have found assymetric addition to be useful actually and will export
it as a separate function, where instead of 'zipping' the two lazy
numbers together, it appends the second to the first, making it fully
lazy in the second argument. It is mainly useful for tying the knot to
make infinite numbers, but can sometimes affect 

hmm.. is there any established terminology for this sort of thing? my
thought is something like:

lazy - fully lazy, _|_ and Infinity can be passed in.

tail-lazy - can produce results without traversing the whole number,
such as division, addition, and multiplication, Infinity can safely be passed in.

head-strict - you can't pass in _|_, but you may or may not be able to pass in
Infinity

fully strict - you can't pass in _|_ or Infinity and expect a result.
'mod' is an example. 

        John

-- 
John Meacham - ⑆repetae.net⑆john⑈