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
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