[Haskell-cafe] List comparisons and permutation group code

[Nicolas Frisby]

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 <tomasz.zielonka at gmail.com> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>