It's nice to have that pointed out; I'm always forgeting that there's
a representation optimization going on when using Ints/Integers for
naturals.
This Peano approach makes the length check no longer strict in the
spine of its input. xs is consumed lazily, [1..natLength xs] is
produced lazily, and thus isIdentity' works lazily. Of course
[1...natLength xs] would have to elaborate to some catamorphism on
Nat:
data Nat = Succ Nat | Zero
[1...nat] = cataPhi nat
cataPhi Zero = []
cataPhi (Succ n) = 1 : map (+1) (cataPhi n)
or a List-anamorphism with Nat's in the state-space
data List a = Cons a | Nil -- pretending built-in [] works like this
[1...nat] = ana psi (nat, 1)
where psi (Zero, _) = Nil
psi (Succ n, x) = Cons x (n, x+1)
Unfortunately Enum and Num are not granular enough to welcome Nat as
an instance, so the [1...Nat] syntax couldn't elaborate thusly today.
I'm sure I'm mentioning things (numeric type classes) here we've
already discussed... sorry if this is all old hat.
I think the cata/ana perspective may highlight the preservation of
laziness during composition issues. Composing particular
omega-morphisms has some theory--am I off in the woods to think it
might apply? It's a bit foggy still.
Thanks,
Nick
On 10/19/06, Tomasz Zielonka <[EMAIL PROTECTED]> wrote:
On Thu, Oct 19, 2006 at 01:37:16PM -0400, Cale Gibbard wrote:
> >Why is this so? I'd have thought that the equality function for lists
> >only forces evaluation of as many elements from its arguments as to
> >determine the answer.
>
> In order to determine if [1..length xs] has an element at all, you
> have to evaluate length xs, which involves forcing the entire spine of
> xs, because integers can't be partially evaluated. Computing lengths
> of lists is a great way to introduce strictness.
Right, so if Ints were represented as a datatype with Succ and Zero
constructors (so integers could be partially evaluated), then the
version with length would behave nicely on large and infinite lists :-)
Best regards
Tomasz
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
